¿Cómo se calcula el cuadro delimitador alineado con el eje de una elipse?
https://stackoverflow.com/questions/87734
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Si el eje mayor de la elipse es vertical u horizontal, es fácil calcular el cuadro delimitador, pero ¿qué pasa cuando se gira la elipse?
La única forma que se me ocurre hasta ahora es calcular todos los puntos alrededor del perímetro y encontrar los valores máximo/mínimo de xey.Parece que debería haber una forma más sencilla.
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 es cero o no está definida, pero parece que no puedo encontrar ninguna.
Editar:Para aclarar, necesito el cuadro delimitador alineado con el eje, es decir,no debe rotarse con la elipse, sino permanecer alineado con el eje x, por lo que transformar el cuadro delimitador no funcionará.
Solución
Podrías 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 centro (h, k), semieje mayor a y semieje menor b, y gira un ángulo phi.
Luego puedes 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 que debería brindarle muchas soluciones para t (dos de las cuales le interesan), conéctelas nuevamente 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]
Probemos un ejemplo:
Considere una elipse en (0,0) con a=2, b=1, rotada 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
Nos interesa t = -0,4636 y t = -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
Otros consejos
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 tantas maneras de hacerlo...
De todos modos, el principio general es el siguiente:No se puede calcular directamente el cuadro de límite alineado con el eje.Sin embargo, puedes calcular los extremos de la elipse en xey como puntos en el espacio 2D.
Para esto es suficiente tomar la ecuación x(t) = elipse_equation(t) e y(t) = elipse_equation(t).Obtenga su derivada de primer orden y resuélvala para encontrar su raíz.Dado que estamos tratando con elipses que se basan en trigonometría, es sencillo.Deberías terminar con una ecuación que obtenga las raíces mediante atan, acos o asin.
Pista:Para verificar su código, pruébelo con una elipse sin girar:Deberías obtener raíces en 0, Pi/2, Pi y 3*Pi/2.
Haga eso para cada eje (x e y).Obtendrá como máximo cuatro raíces (menos si su elipse está degenerada, p. ej.uno de los radios es cero).Evalúe las posiciones en las raíces y obtendrá todos los puntos extremos de la elipse.
Ahora ya casi has llegado.Obtener el cuadro límite de la elipse es tan simple como escanear estos cuatro puntos en busca de xmin, xmax, ymin e ymax.
Por cierto, si tienes problemas para encontrar la ecuación de tu elipse:intente reducirlo al caso de que tenga una elipse alineada con un eje con un centro, dos radios y un ángulo de rotación alrededor del centro.
Si lo haces las ecuaciones quedan:
// 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 su código a C#; los ellipseAngle ahora están 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 ésta.Una elipsis rotada desde un ángulo phi desde el origen tiene como ecuación:
donde (h,k) es el centro, a y b el tamaño de los ejes mayor y menor y t varía de -pi a pi.
A partir de eso, debería poder derivar para qué t dx/dt o dy/dt llega a 0.
Aquí está la fórmula para el caso si la elipse está dada por su focos y excentricidad (para el caso en el que viene dado por las longitudes de los ejes, el centro y el ángulo, consulte e.gramo.la respuesta del usuario1789690).
Es decir, 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 del usuario1789690 y Johan Nilsson.
Si trabaja con OpenCV/C++ y usa cv::fitEllipse(..) función, es posible que necesite un rectángulo delimitador de 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_<float> 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 que el usuario1789690 contribuyó anteriormente, pero implementado en Delphi.Lo he probado y por lo que puedo decir funciona perfectamente.Pasé un día entero buscando un algoritmo o algún código, probé algunos que no funcionaban y estuve muy feliz de finalmente encontrar el código anterior.Espero que alguien encuentre esto útil.Este código calculará el cuadro delimitador de una elipse rotada.El cuadro delimitador está alineado con el eje y NO gira con la elipse.Los radios son para la elipse antes de girarla.
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 a una elipse con orientación arbitraria
Tengo opencv rect y punto de implementación:
cg - centro de la elipse
tamaño: eje mayor y menor de la elipse
ángulo - orientación de la 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;
}
