Wie berechnen Sie die achsgerechte Bounding Box einer Ellipse?

Question

Wenn die Hauptachse der Ellipse vertikal oder horizontal ist, lässt sich die Begrenzungsbox leicht berechnen, aber was ist, wenn die Ellipse gedreht wird?

Der einzige Weg, an den ich bis jetzt denken kann, ist, alle Punkte um den Umkreis zu berechnen und die max/min x und y Werte zu finden. Es scheint, als sollte es einen einfacheren Weg geben.

Wenn es eine Funktion (im mathematischen Sinne) gibt, die eine Ellipse in einem beliebigen Winkel beschreibt, dann könnte ich ihre Ableitung verwenden, um Punkte zu finden, wo die Steigung null oder undefiniert ist, aber ich kann keine finden.

Bearbeiten: Um zu verdeutlichen, brauche ich die Achse ausgerichtet Bounding Box, d. H. Es sollte nicht mit der Ellipse gedreht werden, aber ausgerichtet mit der X-Achse, so dass die Umrandung nicht funktioniert.

Answer 1

Sie könnten versuchen, die parametrisierte Gleichungen für eine Ellipse in einem beliebigen Winkel gedreht:

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] 

... wo Ellipse Zentrum (h, k) Semimajor Achse a und Semiminor Achse b hat und durch Winkel phi gedreht wird.

Sie können dann differenzieren und für Gradient = 0 lösen:

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

=>

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

die Ihnen viele Lösungen für t geben sollte (zwei davon sind Sie interessiert), Stecker zurück in [1], um Max und Min x zu erhalten.

Wiederholen Sie für [2]:

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

=>

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

wir ein Beispiel versuchen:

eine Ellipse Betrachten wir bei (0,0) mit a = 2 , b = 1, gedreht um 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 

Wir interessieren uns für t = -0,4636 und t = -3,6052

So bekommen wir:

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

und

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

Answer 2

Ich denke, die nützlichste Formel ist diese. Eine Auslassung von einem Winkel phi von dem Ursprung gedreht hat als Gleichung:

wo (h, k) ist das Zentrum, a und b die Größe der Haupt- und Nebenachse und t variiert von -pi bis pi.

davon, sollten Sie in der Lage sein, für die abzuleiten t dx/dt oder dy/dt geht auf 0

Answer 3

Dies ist relativ einfach, aber ein bisschen schwer zu erklären, da Sie uns den Weg nicht gegeben haben Sie Ihre Ellipse darstellen. Es gibt so viele Möglichkeiten, es zu tun.

Wie auch immer, das allgemeine Prinzip geht so: Sie können nicht die Achse ausgerichtete Grenze Box direkt berechnen. Sie können jedoch die Extrema der Ellipse in x und y als Punkte im 2D-Raum berechnen.

Dafür genügt es, die Gleichung x (t) = ellipse_equation (t) und y (t) = ellipse_equation (t) zu nehmen. Holen Sie sich die erste Ableitung davon und lösen Sie es für seine Wurzel. Da wir es mit Ellipsen zu tun haben, die auf Trigonometrie basieren, ist das einfach. Sie sollten mit einer Gleichung enden, die entweder die Wurzeln über Atan, Acos oder Asin bekommt.

Tipp: Um Ihren Code zu überprüfen, versuchen Sie es mit einer nicht gedrehten Ellipse: Sie sollten Wurzeln bei 0, Pi/2, Pi und 3 * Pi/2 bekommen.

Machen Sie das für jede Achse (x und y). Sie erhalten höchstens vier Wurzeln (weniger, wenn Ihre Ellipse degeneriert ist, z. B. ist einer der Radien Null). Ermitteln Sie die Positionen an den Wurzeln und Sie erhalten alle Extrempunkte der Ellipse.

Jetzt sind Sie fast da. Das Abrufen der Begrenzungsbox der Ellipse ist so einfach wie das Scannen dieser vier Punkte nach xmin, xmax, ymin und ymax.

BTW - wenn Sie Probleme haben, die Gleichung Ihrer Ellipse zu finden: versuchen Sie, es auf den Fall zu reduzieren, dass Sie eine Achse ausgerichtete Ellipse mit einem Zentrum, zwei Radien und einem Rotationswinkel um das Zentrum haben.

Wenn Sie das tun, so ergibt sich folgende Gleichung:

// 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

ich eine einfache Formel zu http://www.iquilezles.org/www/articles/ellipses/ellipses.htm gefunden (und die z-Achse ignoriert).

Ich setzte es in etwa wie folgt aus:

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

Dieser Code basiert auf dem Code user1789690 oben beigetragen, aber in Delphi implementiert. Ich habe das getestet und soweit ich weiß, funktioniert es perfekt. Ich verbrachte einen ganzen Tag damit, nach einem Algorithmus oder Code zu suchen, testete einige, die nicht funktionierten, und ich war sehr glücklich, endlich den obigen Code zu finden. Ich hoffe, dass jemand das nützlich findet. Dieser Code berechnet die Begrenzungsbox einer gedrehten Ellipse. Der Begrenzungsrahmen ist achsversetzt und NICHT mit der Ellipse gedreht. Die Radien sind für die Ellipse, bevor sie gedreht wurde. Hier

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

ist die Formel für den Fall, wenn die Ellipse durch seine Foci und Exzentrizität gegeben wird (für den Fall, in dem es durch die Achsenlängen gegeben ist, in der Mitte und den Winkel, siehe e. G. Die Antwort von user1789690).

Wenn nämlich die Brennpunkte (x0, y0) und (x1, y1) und die Exzentrizität e, dann

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

wo

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

ich die Formeln aus der Antwort abgeleitet von user1789690 und Johan Nilsson.

Answer 7

Brilian Johan Nilsson. Ich habe Ihren Code C# transkribiert - ellipseAngle sind jetzt in Grad:

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

Dies ist meine Funktion festen Sitz Rechteck für die Suche mit beliebiger Orientierung Ellipse

I opencv rect und Punkt für die Umsetzung haben:

cg - Zentrum der Ellipse

Größe - Dur, Moll Achse Ellipse

Winkel - Ausrichtung der Ellipse

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

Wenn Sie mit OpenCV/C++ arbeiten und cv::fitEllipse(..) Funktion verwenden, können Sie rect der Ellipse begrenzen müssen. Hier habe ich eine Lösung mit Mikes Antwort:

// 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; 
}