Comment calculer le cadre de sélection d'une ellipse aligné sur l'axe?
https://stackoverflow.com/questions/87734
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Si le grand axe de l'ellipse est vertical ou horizontal, il est facile de calculer le cadre de sélection, mais qu'en est-il de la rotation de l'ellipse?
Pour l’instant, la seule façon de penser est de calculer tous les points situés autour du périmètre et de trouver les valeurs max / min x et y. Il semble qu'il devrait y avoir un moyen plus simple.
S'il existe une fonction (au sens mathématique) décrivant une ellipse selon un angle arbitraire, je pourrais utiliser sa dérivée pour rechercher des points où la pente est nulle ou indéfinie, mais je n'arrive pas à en trouver une.
Éditer: pour clarifier, j'ai besoin du cadre de sélection aligné sur l'axe, c.-à-d. qu'elle ne doit pas être pivotée avec l'ellipse, mais reste alignée sur l'axe des x afin que la transformation du cadre de sélection ne fonctionne pas.
La solution
Vous pouvez essayer d'utiliser les équations paramétrées pour une ellipse tournée à un angle quelconque:
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]
... où l'ellipse a un centre (h, k) un demi-grand axe a et un demi-petit b, et est pivoté de l'angle phi.
Vous pouvez ensuite différencier et résoudre pour gradient = 0:
0 = dx/dt = -a*sin(t)*cos(phi) - b*cos(t)*sin(phi)
= >
tan(t) = -b*tan(phi)/a [3]
Ce qui devrait vous donner beaucoup de solutions pour t (deux dont vous êtes intéressé), branchez-le dans [1] pour obtenir votre max et min x.
Répéter pour [2]:
0 = dy/dt = b*cos(t)*cos(phi) - a*sin(t)*sin(phi)
= >
tan(t) = b*cot(phi)/a [4]
Essayons un exemple:
Considérons une ellipse située à (0,0) avec a = 2, b = 1, pivotée de 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
Nous sommes intéressés par t = -0.4636 et t = -3.6052
Nous obtenons donc:
x = 2*cos(-0.4636)*cos(PI/4) - sin(-0.4636)*sin(PI/4) = 1.5811
et
x = 2*cos(-3.6052)*cos(PI/4) - sin(-3.6052)*sin(PI/4) = -1.5811
Autres conseils
J'ai trouvé une formule simple à l'adresse http://www.iquilezles.org/. www / articles / ellipses / ellipses.htm (et ignore l'axe z).
Je l'ai implémenté à peu près comme ceci:
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);
C’est relativement simple mais un peu difficile à expliquer puisque vous ne nous avez pas expliqué comment vous représentez votre ellipse. Il y a tellement de façons de le faire ..
Quoi qu'il en soit, le principe général est le suivant: vous ne pouvez pas calculer directement la boîte de limite alignée sur l’axe. Vous pouvez toutefois calculer les extrema de l'ellipse dans x et y sous forme de points dans un espace 2D.
Pour cela, il suffit de prendre l'équation x (t) = ellipse_equation (t) et y (t) = ellipse_equation (t). Obtenez le dérivé du premier ordre et résolvez-le pour sa racine. Puisque nous avons affaire à des ellipses basées sur la trigonométrie, elles sont simples. Vous devriez vous retrouver avec une équation qui obtient les racines via atan, acos ou asin.
Conseil: pour vérifier votre code, essayez-le avec une ellipse non commentée: vous devriez obtenir les racines à 0, Pi / 2, Pi et 3 * Pi / 2.
Faites cela pour chaque axe (x et y). Vous obtiendrez au plus quatre racines (moins si votre ellipse est dégénérée, par exemple, l’un des rayons est égal à zéro). Évaluez les positions à la racine et vous obtenez tous les points extrêmes de l'ellipse.
Maintenant vous y êtes presque. Obtenir la boîte de frontière de l’ellipse est aussi simple que de scanner ces quatre points pour xmin, xmax, ymin et ymax.
Btw - si vous avez des difficultés à trouver l'équation de votre ellipse: essayez de la réduire au cas où vous auriez une ellipse alignée avec un centre, deux rayons et un angle de rotation autour du centre.
Si vous le faites, les équations deviennent:
// 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. J'ai transcrit votre code en c # - ellipseAngle sont maintenant en degrés:
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);
}
Je pense que la formule la plus utile est celle-ci. Un ellipses tourné d'un angle phi à partir de l'origine a pour équation:
où (h, k) est le centre, a et b la taille des axes majeur et mineur et t varie de -pi à pi.
À partir de là, vous devriez pouvoir en déduire pour lequel t dx / dt ou dy / dt va à 0.
Voici la formule pour le cas où l'ellipse est donnée par ses foyers et son excentricité (dans le cas où elle est donnée par des longueurs d'axe, un centre et un angle, voir par exemple la réponse donnée par l'utilisateur1789690) .
À savoir, si les foyers sont (x0, y0) et (x1, y1) et que l'excentricité est e, alors
bbox_halfwidth = sqrt(k2*dx2 + (k2-1)*dy2)/2
bbox_halfheight = sqrt((k2-1)*dx2 + k2*dy2)/2
où
dx = x1-x0
dy = y1-y0
dx2 = dx*dx
dy2 = dy*dy
k2 = 1.0/(e*e)
J'ai dérivé les formules de la réponse de user1789690 et de Johan Nilsson.
Si vous travaillez avec OpenCV / C ++ et utilisez la fonction cv :: fitEllipse (..) , vous aurez peut-être besoin du rectangle de délimitation de l'ellipse. Ici, j'ai fait une solution en utilisant la réponse 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;
}
Ce code est basé sur le code que l'utilisateur1789690 a contribué ci-dessus, mais implémenté dans Delphi. J'ai testé cela et autant que je sache, cela fonctionne parfaitement. J'ai passé une journée entière à rechercher un algorithme ou un code, à en tester quelques-uns qui ne fonctionnaient pas et j'étais très heureux de trouver enfin le code ci-dessus. J'espère que quelqu'un trouvera cela utile. Ce code calculera le cadre de sélection d'une ellipse tournée. Le cadre de sélection est aligné sur l’axe et NON pivoté avec l’ellipse. Les rayons correspondent à l'ellipse avant sa rotation.
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;
C’est ma fonction qui permet de trouver un rectangle parfaitement ajusté sur une ellipse avec une orientation quelconque
J'ai ouvert rect et point pour la mise en œuvre:
cg - centre de l'ellipse
taille - axe majeur et mineur de l'ellipse
angle - orientation de l'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;
}
