Wie berechnet man den achsenausgerichteten Begrenzungsrahmen einer Ellipse?
https://stackoverflow.com/questions/87734
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wenn die Hauptachse der Ellipse vertikal oder horizontal ist, ist es einfach, den Begrenzungsrahmen zu berechnen, aber was ist, wenn die Ellipse gedreht wird?
Die einzige Möglichkeit, die mir bisher einfällt, besteht darin, alle Punkte um den Umfang herum zu berechnen und die maximalen/minimalen x- und y-Werte zu ermitteln.Es scheint, als ob es einen einfacheren Weg geben sollte.
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, an denen die Steigung Null oder undefiniert ist, aber ich kann anscheinend keine finden.
Bearbeiten:Zur Verdeutlichung benötige ich den achsenausgerichteten Begrenzungsrahmen, d. h.Es sollte nicht mit der Ellipse gedreht werden, sondern an der x-Achse ausgerichtet bleiben, sodass eine Transformation des Begrenzungsrahmens nicht funktioniert.
Lösung
Sie könnten versuchen, die parametrisierte Gleichungen für eine Ellipse in einem beliebigen Winkel gedreht werden:
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 Ellipsenzentrum (h, k) große Halbachse a und kleine Halbachse b auf und werden durch den Winkel phi gedreht.
Sie können dann differenzieren und für Gradient lösen = 0:
0 = dx/dt = -a*sin(t)*cos(phi) - b*cos(t)*sin(phi)
=>
tan(t) = -b*tan(phi)/a [3]
Welche geben sollten Sie viele Lösungen für t (von denen zwei die Sie interessieren), stecken, dass wieder in [1] Ihre 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]
sie ein Beispiel versuchen:
Betrachten eine Ellipse 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 erhalten 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
Andere Tipps
Eine einfache Formel habe ich unter gefunden http://www.iquilezles.org/www/articles/ellipses/ellipses.htm (und ignorierte die z-Achse).
Ich habe es ungefähr so umgesetzt:
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);
Dies ist relativ einfach, aber ein bisschen schwer zu erklären, da Sie uns nicht gegeben haben, wie Sie Ihre Ellipse darstellen. Es gibt so viele Möglichkeiten, es zu tun ..
Wie auch immer, geht das allgemeine Prinzip wie folgt aus: Sie können nicht die Achse ausgerichtet Begrenzungskasten direkt berechnen. Sie können jedoch die Extrema der Ellipse in x und y als Punkte in 2D-Raum berechnen.
Dabei ist es ausreichend, die Gleichung x (t) = ellipse_equation (t) und y (t) = ellipse_equation (t) zu nehmen. Holen Sie sich das erste Bestellung Derivates davon und lösen sie es die Wurzel für. Da wir mit Ellipsen handelt, die auf Trigonometrie basieren, die gerade nach vorne ist. Sie sollten mit einer Gleichung am Ende, dass entweder die Wurzeln über atan, acos bekommt oder asin.
Hinweis: Ihr Code Um zu überprüfen, versuchen Sie es mit einer nicht gedrehten Ellipse: Sie Wurzeln bei 0, Pi / 2, Pi und 3 * Pi / 2 erhalten sollten
.Sie, dass für jede Achse (x und y). Sie werden höchstens vier Wurzeln (weniger, wenn die Ellipse degeneriert ist, beispielsweise einer der Radien ist Null) erhalten. Evalulate die Positionen an den Wurzeln und Sie erhalten alle Extrempunkte der Ellipse.
Jetzt sind Sie fast da. die Grenze Feld der Ellipse zu bekommen ist so einfach, diese vier Punkte als das Scannen für xmin, xmax, ymin und ymax.
Btw - wenn Sie Probleme zu finden, die Gleichung der Ellipse haben. Versuchen, es zu dem Fall zu verringern, dass Sie eine Achse ausgerichtet Ellipse mit einem Zentrum, zwei Radien und einen Drehwinkel um die Mitte
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;
Brilian Johan Nilsson. Ich habe Ihren Code c # transkribiert - ellipseAngle ist 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);
}
Ich denke, die nützlichsten Formel dieses ist. Eine Auslassung von einem Winkel phi vom Ursprung hat als Gleichung gedreht:
, wobei (h, k) ist das Zentrum, a und b die Größe der Haupt- und Nebenachse und t variiert von -pi bis pi.
Von diesem, sollten Sie in der Lage sein, für die abzuleiten t dx / dt oder dy / dt geht auf 0 zurück.
Hier ist die Formel für den Fall, wenn die Ellipse gegeben ist durch seine Brennpunkte und Exzentrizität (für den Fall, in dem es durch die Achsenlängen Zentrum und Winkel gegeben ist, siehe zum Beispiel 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
Dabei steht
dx = x1-x0
dy = y1-y0
dx2 = dx*dx
dy2 = dy*dy
k2 = 1.0/(e*e)
I abgeleitet, um die Formeln aus der Antwort von user1789690 und Johan Nilsson.
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 Mike Antwort mit:
// 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;
}
Dieser Code basiert auf dem Code user1789690 beigetragen oben, aber in Delphi implementiert. Ich habe dies getestet und soweit ich sagen kann, es funktioniert perfekt. Ich verbrachte einen ganzen Tag für einen Algorithmus der Suche oder einen Code, getestet einige, die nicht funktionierten, und ich war sehr glücklich, den Code oben, um schließlich zu finden. Ich hoffe, dass jemand dies nützlich findet. Dieser Code wird die Begrenzungsbox eines gedrehten Ellipse berechnen. Der Begrenzungsrahmen ist Achse ausgerichtet ist und nicht mit der Ellipse gedreht. Die Radien sind für die Ellipse, bevor er gedreht wurde.
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;
Das ist meine Funktion für die Suche nach festem Sitz Rechteck mit beliebiger Orientierung Ellipse
Ich habe opencv rect und Punkt für die Implementierung:
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;
}
