Como você calcular a caixa delimitadora alinhado ao eixo de uma elipse?
https://stackoverflow.com/questions/87734
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Se o eixo principal da elipse é vertical ou horizontal, é fácil calcular a caixa delimitadora, mas o que dizer quando a elipse é girada?
A única maneira que eu posso pensar até agora é calcular todos os pontos ao redor do perímetro e encontrar as max / min x e y valores. Parece que deve haver uma maneira mais simples.
Se há uma função (no sentido matemático) que descreve uma elipse em um ângulo arbitrário, então eu poderia usar sua derivada para encontrar pontos onde a inclinação é zero ou indefinido, mas eu não consigo encontrar um.
Editar: para esclarecer, eu preciso de caixa delimitadora alinhado ao eixo, ou seja, não deve ser girado com a elipse, mas estadia alinhado com o eixo X assim transformando a caixa delimitadora não funcionará
Solução
Você pode tentar usar as equações parametrizadas por uma elipse girada em um ângulo arbitrário:
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]
... onde elipse tem centro (h, k) semi-eixo maior e um eixo semiminor b, e é rodada através de um ângulo phi.
Você pode então diferenciar e resolver para gradiente = 0:
0 = dx/dt = -a*sin(t)*cos(phi) - b*cos(t)*sin(phi)
=>
tan(t) = -b*tan(phi)/a [3]
Que deve dar-lhe muitas soluções para t (dois dos quais você está interessado em), plugue que volta para [1] para obter o seu máximo e mínimo x.
Repita para [2]:
0 = dy/dt = b*cos(t)*cos(phi) - a*sin(t)*sin(phi)
=>
tan(t) = b*cot(phi)/a [4]
Vamos tentar um exemplo:
Considere uma elipse em (0,0) com a = 2, b = 1, rodado pela 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 interessados ??em t = -0,4636 e -3,6052 t =
Assim, temos:
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
Outras dicas
Eu encontrei uma fórmula simples em http://www.iquilezles.org/ www / artigos / elipses / ellipses.htm (e ignorado o eixo z).
Eu implementou mais ou menos assim:
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);
Este é relativamente simples, mas um pouco difícil de explicar, pois você não nos deram a maneira de representar a sua elipse. Há tantas maneiras de fazer isso ..
De qualquer forma, o princípio geral é assim: Você não pode calcular caixa de limite do eixo alinhado diretamente. No entanto, pode calcular os extremos da elipse em x e y como pontos no espaço 2D.
Para isso, é suficiente para tomar a equação x (t) = ellipse_equation (t) e y (t) = ellipse_equation (t). Obter o primeiro derivado fim do mesmo e resolvê-lo para a sua raiz. Como estamos lidando com elipses que são baseadas em trigonometria que é para a frente. Você deve acabar com uma equação que quer recebe as raízes via Atan, acos ou asin.
Dica: Para verificar o seu código de experimentá-lo com uma elipse unrotated: Você deve obter raízes em 0, Pi / 2, Pi e 3 * pi / 2
.Do que para cada eixo (x e y). Você vai ter, no máximo, quatro raízes (menos se sua elipse é degenerado, por exemplo, um dos raios é zero). Evalulate as posições nas raízes e você terá todos os pontos extremos da elipse.
Agora você está quase lá. Obtendo a caixa de limite da elipse é tão simples como a digitalização desses quatro pontos para xmin, xmax, ymin e ymax.
Btw - se você tiver problemas para encontrar a equação de sua elipse:. Tentar reduzi-lo para o caso de que você tem uma elipse alinhados eixo com um centro, dois raios e um ângulo de rotação em torno do centro
Se você fizer isso as equações tornam-se:
// 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. Eu transcrevi seu código para c # - ellipseAngle estão agora em graus:
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);
}
Eu acho que a fórmula mais útil é um presente. Uma elipse girada a partir de um ângulo phi da origem tem como equação:
em que (h, k) é o centro, a e b da dimensão do eixo maior e menor e t varia de -pi a pi.
A partir daí, você deve ser capaz de derivar para o qual t dx / dt ou dy / dt vai para 0.
Aqui é a fórmula para o caso se a elipse é dada pela sua
Ou seja, se os focos são (x0, y0) e (x1, y1) e a excentricidade é e, em seguida,
bbox_halfwidth = sqrt(k2*dx2 + (k2-1)*dy2)/2
bbox_halfheight = sqrt((k2-1)*dx2 + k2*dy2)/2
onde
dx = x1-x0
dy = y1-y0
dx2 = dx*dx
dy2 = dy*dy
k2 = 1.0/(e*e)
I derivadas das fórmulas da resposta por user1789690 e Johan Nilsson.
Se você trabalha com OpenCV / C ++ e use a função cv::fitEllipse(..), você pode precisar delimitadora rect da elipse. Aqui eu fiz uma solução usando a resposta 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;
}
Este código é baseado no user1789690 código contribuiu acima, mas implementado em Delphi. Eu testei isso e, tanto quanto eu posso dizer que funciona perfeitamente. Passei toda uma busca dia por um algoritmo ou algum código, testado alguns que não funcionou, e eu estava muito feliz de finalmente encontrar o código acima. Espero que alguém acha isso útil. Este código irá calcular a caixa delimitadora de uma elipse girada. A caixa delimitadora é eixo alinhado e não rodado com a elipse. Os raios são para a elipse antes de ser rodado.
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;
Esta é a minha função para encontrar o ajuste retângulo apertado para elipse com orientação arbitrária
Eu tenho rect opencv e ponto para a implementação:
cg - centro da elipse
tamanho - grande, eixo menor da elipse
ângulo - orientação da 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;
}
