[Math] 타원의 축 정렬 경계 상자는 어떻게 계산합니까?


Answers

임의의 각도로 회전 된 타원에 대해 매개 변수화 된 방정식을 사용할 수 있습니다.

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]

... 타원은 중심 (h, k) 반경 a와 반 중간 b를 가지며 각도 φ를 통해 회전합니다.

그런 다음 그라디언트 = 0을 구별하고 해결할 수 있습니다.

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

=>

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

t (둘 중 관심이있는 것)에 대한 여러 솔루션을 제공하고, 최대 및 최소 x를 얻기 위해 다시 [1]에 연결하십시오.

[2]에 대해 반복하십시오.

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

=>

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

예를 들어 보겠습니다.

a = 2, b = 1, PI / 4만큼 회전 된 타원 (0,0)

[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

우리는 t = -0.4636 및 t = -3.6052에 관심이있다.

그래서 우리는 얻는다.

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

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

타원의 주축이 수직 또는 수평 인 경우 경계 상자를 쉽게 계산할 수 있지만 타원을 회전 할 때는 어떨까요?

지금까지 생각할 수있는 유일한 방법은 주변의 모든 점을 계산하고 최대 / 최소 x 및 y 값을 찾는 것입니다. 더 간단한 방법이 있어야하는 것처럼 보입니다.

임의의 각도에서 타원을 설명하는 함수가 있다면 (수학적으로), 그 미분을 사용하여 기울기가 0이거나 정의되지 않은 점을 찾을 수 있지만 찾을 수는 없습니다.

편집 : 명확히하기 위해 축 정렬 경계 상자가 필요합니다. 즉, 타원으로 회전하면 안되지만 경계 상자를 변형하면 x 축과 정렬되어 유지되지 않습니다.




Brilian Johan Nilsson. 귀하의 코드를 C #으로 복사했습니다 - ellipseAngle은 이제도 단위입니다 :

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



임의의 방향으로 타원에 꼭 맞는 직사각형을 찾는 내 함수입니다.

opencv rect 및 구현 지점 :

cg - 타원의 중심

size - 타원의 장축 단축

각도 - 타원의 방향

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



이 코드는 위에 제공된 user1789690 코드를 기반으로하지만, Delphi에서 구현됩니다. 나는 이것을 시험해 보았다. 그리고 내가 말할 수있는 한 그것은 완벽하게 작동한다. 나는 하루 종일 알고리즘이나 코드를 검색하고, 작동하지 않는 코드를 테스트했으며, 결국 위 코드를 찾은 것을 매우 기뻤습니다. 누군가가 이것을 유용하게 찾길 바랍니다. 이 코드는 회전 된 타원의 경계 상자를 계산합니다. 경계 상자는 축 정렬이며 타원과 회전하지 않습니다. 반경은 회전하기 전의 타원에 대한 반경입니다.

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;



나는 http://www.quilezles.org/www/articles/ellipses/ellipses.htm 에서 간단한 공식을 발견했다 . (그리고 z 축은 무시했다.)

나는 이것을 대략 다음과 같이 구현했다.

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);



이것은 상대적으로 간단하지만 타원을 나타내는 방식을 우리에게주지 않았기 때문에 설명하기가 약간 어렵습니다. 그것을 할 수있는 많은 방법이 있습니다 ..

어쨌든 일반적인 원칙은 다음과 같습니다. 축 정렬 경계 상자를 직접 계산할 수 없습니다. 그러나 x와 y의 타원 극한을 2D 공간의 점으로 계산할 수 있습니다.

이를 위해 방정식 x (t) = ellipse_equation (t)와 y (t) = ellipse_equation (t)을 취하면 충분합니다. 그것의 첫 번째 순서 파생물을 얻고 루트를 위해 그것을 해결하십시오. 우리는 삼각법을 기반으로하는 타원을 다루고 있기 때문에 앞으로 나아갈 수 있습니다. 당신은 atan, acos 또는 asin을 통해 뿌리를 얻는 방정식으로 끝나야합니다.

힌트 : 코드를 확인하려면 회전하지 않는 타원으로 시도하십시오. 0, Pi / 2, Pi 및 3 * Pi / 2에서 뿌리를 가져와야합니다.

각 축 (x 및 y)에 대해이를 수행하십시오. 최대 네 개의 뿌리를 얻을 수 있습니다 (타원형이 퇴화 된 경우, 예를 들어 반지름 중 하나가 0 인 경우). 뿌리에서의 위치를 ​​평가하고 타원의 모든 극점을 얻습니다.

이제 거의 다 왔어. 타원의 경계 상자를 얻는 것은 xmin, xmax, ymin 및 ymax에 대해이 네 점을 스캔하는 것만 큼 간단합니다.

Btw - 타원 방정식을 찾는 데 문제가있는 경우 : 중심, 두 반경 및 중심을 기준으로 한 회전 각도로 축이 정렬 된 축척으로 축소하십시오.

그렇게하면 방정식은 다음과 같이됩니다.

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



타원이 초점 및 편심 으로 주어지면 (예 : 축 길이, 중심 및 각도로 주어진 경우에 대해서는 사용자 1789690의 답 참조) 수식이 있습니다.

즉, 초점이 (x0, y0) 및 (x1, y1)이고 이심률이 e 인 경우,

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

어디에

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

나는 user1789690과 Johan Nilsson에 의해 해답을 추출했다.




나는 가장 유용한 공식이 이것이라고 생각합니다. 원점으로부터 각도 φ에서 회전 된 타원은 방정식과 같습니다.

여기서 (h, k)는 중심이며, a 및 b는 장축 및 단축의 크기이고 t는 -pi에서 pi까지 다양하다.

따라서 dx / dt 또는 dy / dt가 0이되는 값을 도출 할 수 있어야합니다.




OpenCV / C ++로 작업하고 cv::fitEllipse(..) 함수를 사용한다면, 타원의 경계 cv::fitEllipse(..) 이 필요할 수 있습니다. 여기에 마이크의 대답을 사용하여 해결책을 만들었습니다.

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