¿Cómo se calcula el cuadro delimitador alineado con el eje de una elipse?

Si el eje mayor de la elipse es vertical u horizontal, es fácil calcular el cuadro delimitador, pero ¿qué ocurre cuando se gira la elipse?

La única forma en que puedo pensar hasta ahora es calcular todos los puntos alrededor del perímetro y encontrar los valores max / min xey. Parece que debería haber una manera más simple.

Si hay una función (en el sentido matemático) que describe una elipse en un ángulo arbitrario, entonces podría usar su derivada para encontrar puntos donde la pendiente sea cero o indefinida, pero parece que no puedo encontrarla.

Editar: para aclarar, necesito el cuadro delimitador alineado con el eje, es decir, no debe girarse con la elipse, sino permanecer alineado con el eje x, por lo que la transformación del cuadro delimitador no funcionará.

Podría intentar usar las ecuaciones parametrizadas para una elipse girada en un ángulo arbitrario:

x = h + a*cos(t)*cos(phi) - b*sin(t)*sin(phi) [1] y = k + b*sin(t)*cos(phi) + a*cos(t)*sin(phi) [2] 

… donde la elipse tiene el eje semiajor a central (h, k) y el eje semieje b, y se rota a través del ángulo phi.

A continuación, puede diferenciar y resolver para gradiente = 0:

 0 = dx/dt = -a*sin(t)*cos(phi) - b*cos(t)*sin(phi) 

=>

 tan(t) = -b*tan(phi)/a [3] 

Lo cual debería brindarle muchas soluciones para t (dos de las cuales le interesan), vuelva a conectarlo a [1] para obtener su máximo y mínimo x.

Repita para [2]:

 0 = dy/dt = b*cos(t)*cos(phi) - a*sin(t)*sin(phi) 

=>

 tan(t) = b*cot(phi)/a [4] 

Vamos a probar un ejemplo:

Considere una elipse en (0,0) con a = 2, b = 1, rotado por PI / 4:

[1] =>

 x = 2*cos(t)*cos(PI/4) - sin(t)*sin(PI/4) 

[3] =>

 tan(t) = -tan(PI/4)/2 = -1/2 

=>

 t = -0.4636 + n*PI 

Estamos interesados ​​en t = -0.4636 yt = -3.6052

Entonces obtenemos:

 x = 2*cos(-0.4636)*cos(PI/4) - sin(-0.4636)*sin(PI/4) = 1.5811 

y

 x = 2*cos(-3.6052)*cos(PI/4) - sin(-3.6052)*sin(PI/4) = -1.5811 

Encontré una fórmula simple en http://www.iquilezles.org/www/articles/ellipses/ellipses.htm (e ignoré el eje z).

Lo implementé más o menos así:

 num ux = ellipse.r1 * cos(ellipse.phi); num uy = ellipse.r1 * sin(ellipse.phi); num vx = ellipse.r2 * cos(ellipse.phi+PI/2); num vy = ellipse.r2 * sin(ellipse.phi+PI/2); num bbox_halfwidth = sqrt(ux*ux + vx*vx); num bbox_halfheight = sqrt(uy*uy + vy*vy); Point bbox_ul_corner = new Point(ellipse.center.x - bbox_halfwidth, ellipse.center.y - bbox_halfheight); Point bbox_br_corner = new Point(ellipse.center.x + bbox_halfwidth, ellipse.center.y + bbox_halfheight); 

Esto es relativamente simple pero un poco difícil de explicar ya que no nos has dado la forma en que representas tu elipse. Hay muchas maneras de hacerlo …

De todos modos, el principio general es el siguiente: no se puede calcular el cuadro de límite alineado al eje directamente. Sin embargo, puede calcular los extremos de la elipse en x e y como puntos en el espacio 2D.

Para esto, es suficiente tomar la ecuación x (t) = elipse_equation (t) e y (t) = ellipse_equation (t). Obtén la derivada de primer orden y resuélvela por su raíz. Ya que estamos lidiando con elipses que se basan en la trigonometría, es sencillo. Deberías terminar con una ecuación que obtiene las raíces a través de atan, acos o asin.

Sugerencia: para verificar su código, inténtelo con una elipse no girada: debe obtener raíces en 0, Pi / 2, Pi y 3 * Pi / 2.

Haz eso para cada eje (x e y). Obtendrá como máximo cuatro raíces (menos si su elipse está degenerada, por ejemplo, uno de los radios es cero). Evalúa las posiciones en las raíces y obtienes todos los puntos extremos de la elipse.

Ahora estás casi allí. Obtener el cuadro de límite de la elipse es tan simple como escanear estos cuatro puntos para xmin, xmax, ymin e ymax.

Por cierto, si tiene problemas para encontrar la ecuación de su elipse, intente reducirla al caso en que tenga una elipse alineada con el eje con un centro, dos radios y un ángulo de rotación alrededor del centro.

Si lo haces, las ecuaciones se convierten en:

  // the ellipse unrotated: temp_x (t) = radius.x * cos(t); temp_y (t) = radius.y = sin(t); // the ellipse with rotation applied: x(t) = temp_x(t) * cos(angle) - temp_y(t) * sin(angle) + center.x; y(t) = temp_x(t) * sin(angle) + temp_y(t) * cos(angle) + center.y; 

Brilian Johan Nilsson. He transcrito tu código a c # – ellipseAngle ahora está en grados:

 private static RectangleF EllipseBoundingBox(int ellipseCenterX, int ellipseCenterY, int ellipseRadiusX, int ellipseRadiusY, double ellipseAngle) { double angle = ellipseAngle * Math.PI / 180; double a = ellipseRadiusX * Math.Cos(angle); double b = ellipseRadiusY * Math.Sin(angle); double c = ellipseRadiusX * Math.Sin(angle); double d = ellipseRadiusY * Math.Cos(angle); double width = Math.Sqrt(Math.Pow(a, 2) + Math.Pow(b, 2)) * 2; double height = Math.Sqrt(Math.Pow(c, 2) + Math.Pow(d, 2)) * 2; var x= ellipseCenterX - width * 0.5; var y= ellipseCenterY + height * 0.5; return new Rectangle((int)x, (int)y, (int)width, (int)height); } 

Creo que la fórmula más útil es esta. Una elipsis girada desde un ángulo phi desde el origen tiene como ecuación:

texto alternativo

texto alternativo

donde (h, k) es el centro, a y b el tamaño del eje mayor y menor yt varía de -pi a pi.

A partir de eso, debería poder derivar para lo que t dx / dt o dy / dt va a 0.

Aquí está la fórmula para el caso si la elipse viene dada por sus focos y excentricidad (para el caso en que viene dada por longitudes de ejes, centro y ángulo, véase, por ejemplo, la respuesta del usuario1789690).

A saber, si los focos son (x0, y0) y (x1, y1) y la excentricidad es e, entonces

 bbox_halfwidth = sqrt(k2*dx2 + (k2-1)*dy2)/2 bbox_halfheight = sqrt((k2-1)*dx2 + k2*dy2)/2 

dónde

 dx = x1-x0 dy = y1-y0 dx2 = dx*dx dy2 = dy*dy k2 = 1.0/(e*e) 

Derivé las fórmulas de la respuesta por user1789690 y Johan Nilsson.

Si trabaja con OpenCV / C ++ y utiliza la función cv::fitEllipse(..) , puede que necesite delimitar elipse. Aquí hice una solución usando la respuesta de Mike:

 // tau = 2 * pi, see tau manifest const double TAU = 2 * std::acos(-1); cv::Rect calcEllipseBoundingBox(const cv::RotatedRect &anEllipse) { if (std::fmod(std::abs(anEllipse.angle), 90.0) < = 0.01) { return anEllipse.boundingRect(); } double phi = anEllipse.angle * TAU / 360; double major = anEllipse.size.width / 2.0; double minor = anEllipse.size.height / 2.0; if (minor > major) { std::swap(minor, major); phi += TAU / 4; } double cosPhi = std::cos(phi), sinPhi = std::sin(phi); double tanPhi = sinPhi / cosPhi; double tx = std::atan(-minor * tanPhi / major); cv::Vec2d eqx{ major * cosPhi, - minor * sinPhi }; double x1 = eqx.dot({ std::cos(tx), std::sin(tx) }); double x2 = eqx.dot({ std::cos(tx + TAU / 2), std::sin(tx + TAU / 2) }); double ty = std::atan(minor / (major * tanPhi)); cv::Vec2d eqy{ major * sinPhi, minor * cosPhi }; double y1 = eqy.dot({ std::cos(ty), std::sin(ty) }); double y2 = eqy.dot({ std::cos(ty + TAU / 2), std::sin(ty + TAU / 2) }); cv::Rect_ bb{ cv::Point2f(std::min(x1, x2), std::min(y1, y2)), cv::Point2f(std::max(x1, x2), std::max(y1, y2)) }; return bb + anEllipse.center; } 

Este código se basa en el código user1789690 aportado anteriormente, pero implementado en Delphi. Lo he probado y, por lo que puedo ver, funciona a la perfección. Pasé un día entero buscando un algoritmo o algún código, probé algunos que no funcionaron, y estuve muy contento de finalmente encontrar el código anterior. Espero que alguien encuentre esto útil. Este código calculará el cuadro delimitador de una elipse girada. El cuadro delimitador está alineado con el eje y NO se ha rotado con la elipse. Los radios son para la elipse antes de girar.

 type TSingleRect = record X: Single; Y: Single; Width: Single; Height: Single; end; function GetBoundingBoxForRotatedEllipse(EllipseCenterX, EllipseCenterY, EllipseRadiusX, EllipseRadiusY, EllipseAngle: Single): TSingleRect; var a: Single; b: Single; c: Single; d: Single; begin a := EllipseRadiusX * Cos(EllipseAngle); b := EllipseRadiusY * Sin(EllipseAngle); c := EllipseRadiusX * Sin(EllipseAngle); d := EllipseRadiusY * Cos(EllipseAngle); Result.Width := Hypot(a, b) * 2; Result.Height := Hypot(c, d) * 2; Result.X := EllipseCenterX - Result.Width * 0.5; Result.Y := EllipseCenterY - Result.Height * 0.5; end; 

Esta es mi función para encontrar un rectángulo ajustado para elipse con orientación arbitraria

Tengo opencv rect y apunto para la implementación:

cg – centro de la elipse

tamaño – eje mayor y menor de elipse

ángulo – orientación de elipse

 cv::Rect ellipse_bounding_box(const cv::Point2f &cg, const cv::Size2f &size, const float angle) { float a = size.width / 2; float b = size.height / 2; cv::Point pts[4]; float phi = angle * (CV_PI / 180); float tan_angle = tan(phi); float t = atan((-b*tan_angle) / a); float x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); float y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); pts[0] = cv::Point(cvRound(x), cvRound(y)); t = atan((b*(1 / tan(phi))) / a); x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); pts[1] = cv::Point(cvRound(x), cvRound(y)); phi += CV_PI; tan_angle = tan(phi); t = atan((-b*tan_angle) / a); x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); pts[2] = cv::Point(cvRound(x), cvRound(y)); t = atan((b*(1 / tan(phi))) / a); x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi); y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi); pts[3] = cv::Point(cvRound(x), cvRound(y)); long left = 0xfffffff, top = 0xfffffff, right = 0, bottom = 0; for (int i = 0; i < 4; i++) { left = left < pts[i].x ? left : pts[i].x; top = top < pts[i].y ? top : pts[i].y; right = right > pts[i].x ? right : pts[i].x; bottom = bottom > pts[i].y ? bottom : pts[i].y; } cv::Rect fit_rect(left, top, (right - left) + 1, (bottom - top) + 1); return fit_rect; }