Come si fa a calcolare l'asse allineato riquadro di delimitazione di un'ellisse?
https://stackoverflow.com/questions/87734
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Se l'asse maggiore dell'ellisse verticale o orizzontale, è facile calcolare il riquadro di delimitazione, ma che dire quando l'ellisse è ruotato?
L'unico modo che posso pensare è di calcolare tutti i punti lungo il perimetro e a trovare il max/min valori di x e y.Sembra che ci dovrebbe essere un modo più semplice.
Se c'è una funzione (in senso matematico) che descrive un'ellisse in un angolo arbitrario, quindi ho potuto usare la sua derivata per trovare i punti in cui la pendenza è zero o indefinito, ma non riesco a trovare uno.
Edit:per chiarire, non ho bisogno di asse-aligned bounding box, cioènon deve essere ruotata con l'ellisse, ma rimanere in linea con l'asse x in modo di trasformare il rettangolo di selezione non funziona.
Soluzione
Si potrebbe provare a utilizzare la parametrizzazione equazione di un'ellisse ruotato di un angolo 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]
...dove ellisse è il centro di (h,k) semimajor asse e semiminor asse b, ed è ruotata di angolo phi.
Si possono quindi distinguere e risolvere per pendenza = 0:
0 = dx/dt = -a*sin(t)*cos(phi) - b*cos(t)*sin(phi)
=>
tan(t) = -b*tan(phi)/a [3]
Che dovrebbero dare molte soluzioni per t (di cui due si sono interessati), tappo posteriore in [1] per ottenere il max e min x.
Ripetere l'operazione per [2]:
0 = dy/dt = b*cos(t)*cos(phi) - a*sin(t)*sin(phi)
=>
tan(t) = b*cot(phi)/a [4]
Vediamo un esempio:
In considerazione di un'ellisse (0, 0), con a=2, b=1, ruotato di 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
Siamo interessati a t = -0.4636 e t = -3.6052
Si ottiene così:
x = 2*cos(-0.4636)*cos(PI/4) - sin(-0.4636)*sin(PI/4) = 1.5811
e
x = 2*cos(-3.6052)*cos(PI/4) - sin(-3.6052)*sin(PI/4) = -1.5811
Altri suggerimenti
Ho trovato una semplice formula http://www.iquilezles.org/www/articles/ellipses/ellipses.htm (e ignorato l'asse z).
Ho implementato all'incirca come questo:
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);
Questo è relativo, semplice ma un po ' difficile da spiegare, dato che non hai dato il modo di rappresentare la tua ellisse.Ci sono tanti modi per farlo..
Comunque, il principio generale va come questa:Non è possibile calcolare l'asse allineato confine direttamente.Tuttavia, è possibile calcolare l'extrema dell'ellisse in x e y come punti nello spazio 2D.
Per questo è sufficiente prendere l'equazione x(t) = ellipse_equation(t) e y(t) = ellipse_equation(t).Ottenere il primo ordine derivato di esso e risolvere per il root.Dal momento che abbiamo a che fare con i puntini di sospensione che sono a base di trigonometria che è dritto in avanti.Si dovrebbe finire con un'equazione che si ottiene le radici via atan, acos o asin.
Suggerimento:Per controllare il codice di provare con una ruotata ellisse:Si dovrebbe ottenere radici a 0, Pi/2, Pi e 3*Pi/2.
Non che per ogni asse (x e y).Si arriva a più di quattro radici (meno se l'ellisse è degenerato, ad es.uno dei raggi è zero).Evalulate le posizioni, le loro radici e si ottengono tutti i punti estremi dell'ellisse.
Ora ci siamo quasi.Raggiungere il confine dell'ellisse è semplice come la scansione di questi quattro punti per xmin, xmax, ymin e ymax.
Btw se hai problemi a trovare l'equazione dell'ellissi:cercare di ridurre al caso in cui si dispone di un asse allineato ellisse con un centro, due raggi e un angolo di rotazione intorno al centro.
Se si fa in modo che le equazioni diventano:
// 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.Ho trascritto il codice c# - ellipseAngle ora sono in gradi:
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);
}
Penso che la cosa più utile formula è questa.I puntini di sospensione ruotato di un angolo phi dall'origine ha equazione:
dove (h,k) è il centro, a e b le dimensioni degli assi maggiore e minore e t varia da -pi di pi.
Da questo, si dovrebbe essere in grado di derivare per cui t dx/dt o dy/dt va a 0.
Ecco la formula per caso se l'ellisse è dato dalla sua foci ed eccentricità (per il caso in cui è dato da lunghezze degli assi, il centro e l'angolo, vedere e.g.la risposta da user1789690).
Cioè, se i fuochi sono (x0, y0) e (x1, y1) e l'eccentricità è e, quindi,
bbox_halfwidth = sqrt(k2*dx2 + (k2-1)*dy2)/2
bbox_halfheight = sqrt((k2-1)*dx2 + k2*dy2)/2
dove
dx = x1-x0
dy = y1-y0
dx2 = dx*dx
dy2 = dy*dy
k2 = 1.0/(e*e)
Ho ricavato le formule da la risposta da user1789690 e Johan Nilsson.
Se si lavora con OpenCV/C++ e l'uso cv::fitEllipse(..) funzione, potrebbe essere necessario rect delimitazione dell'ellisse.Qui ho fatto una soluzione con Mike per la risposta:
// 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;
}
Questo codice è basato sul codice user1789690 contribuito sopra, ma realizzati in Delphi.Ho testato questo e, per quanto posso dire che funziona perfettamente.Ho passato un intero giorno nella ricerca di un algoritmo o di un po 'di codice, provato un po' che non lavoro, e sono stato molto felice di trovare finalmente il codice di cui sopra.Spero che qualcuno lo trova utile.Questo codice serve per calcolare il riquadro di delimitazione di una ruotata ellisse.Il riquadro è asse allineato e NON ruotato con l'ellisse.I raggi sono per l'ellisse prima è stato ruotato.
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;
Questa è la mia funzione di stretta misura il rettangolo di ellisse con arbitraria orientamento
Ho opencv rect e punto per l'attuazione:
cg - centro dell'ellisse
la dimensione maggiore e asse minore dell'ellisse
angolo di orientamento di ellisse
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;
}
