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

Question

Si el eje principal de la elipse es vertical u horizontal, es fácil calcular el cuadro delimitador, pero ¿qué sucede 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á.

Answer 1

Usted podría tratar de usar las ecuaciones parametrizadas por una elipse rotada 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 elipse tiene el eje semiajor a central (h, k) y el eje semieje b, y se gira a través del ángulo phi.

continuación Puede diferenciar y resolver de gradiente = 0:

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

=>

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

que debe dar muchas soluciones para t (dos de los cuales le interesa), el enchufe eso de vuelta en [1] para obtener su max y min x.

Repetir para [2]:

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

=>

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

permite tratar un ejemplo:

considerar 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 y T = -3,6052

por lo que tenemos:

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 

Answer 2

Creo que la fórmula más útil es esta. Los puntos suspensivos girado desde un ángulo phi desde el origen tiene como ecuación:

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

partir de eso, usted debería ser capaz de derivar para los que t dx/dt o dy/dt va a 0.

Answer 3

Esto es relativamente sencillo, pero un poco difícil de explicar, ya que no nos ha dado la forma de representar a su 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 al eje. 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) y 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 comprobar el código, inténtelo con una elipse no girada: debe 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, 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.

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

BTW: 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 hace 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; 

Answer 4

He encontrado una fórmula simple en http://www.iquilezles.org/www/articles/ellipses/ellipses.htm (e ignorado el eje z).

que la pusieran en práctica 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); 

Answer 5

Este código está basado en el código de user1789690 contribuido anterior, 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; 

Answer 6

Aquí es la fórmula para el caso si la elipse está dado por su focos y la excentricidad (para el caso en el que está dado por las longitudes de eje, el centro y ángulo, véase e. G. La respuesta por user1789690).

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 

donde

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

I derivan las fórmulas de la respuesta por user1789690 y Johan Nilsson.

Answer 7

Brilian Johan Nilsson. he transcrito su código para C# - ellipseAngle ahora son 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); 
} 

Answer 8

Ésta es mi función para encontrar ajuste apretado rectángulo para elipse con orientación arbitraria

tengo rect OpenCV y el punto de aplicación:

cg - centro de la elipse

tamaño - eje mayor, 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; 
} 

Answer 9

Si trabaja con OpenCV/C++ y utiliza cv::fitEllipse(..) función, es posible que tenga que limita rect de la 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; 
}