軸の楕円のバウンディングボックスをどのように計算しますか？

Question

楕円の長軸が垂直または水平の場合、バウンディングボックスを簡単に計算できますが、楕円を回転させるとどうなりますか？

私がこれまで考えることができる唯一の方法は、周囲のすべての点を計算し、最大/最小のxとyの値を見つけることです。よりシンプルな方法があるはずです。

任意の角度の楕円を記述する関数（数学的な意味で）がある場合、その派生関数を使って勾配がゼロまたは未定義の点を見つけることができますが、見つけられないようです。

編集：明確にするために、私は軸に揃えられたバウンディングボックスが必要です。つまり、楕円で回転してはいけませんが、境界ボックスを変形することはできません。

Answer 1

に行くあなたは楕円のためのパラメータ化方程式を使用して試みることができる任意の角度で回転さ：

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] 

（あなたが興味を持っているそのうちの2つ）、プラグをあなたの最大と最小のxを得るために[1]に戻ります。[2]用

繰り返し：

は（0,0）での楕円を考える= 2：

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

=>

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

例を試すことができます、b = 1、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 

我々はトンに興味がある= -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 

Answer 2

私は最も有用な式はこれだと思います。原点からの角度PHIから回転省略記号は、式として有している：（H、K）の中心、Aであり、長軸と短軸の大きさBと

tは-piからpiまで変化する。それから、

、あなたはトンDX/DTいる導き出すことができるはずですかDY/dtが0

Answer 3

これは相対シンプルですが、あなたは私たちにあなたの楕円を表す方法が与えられていないので、説明するのは少し難しいです。多くの方法があります。

とにかく、一般的な原則は次のようになります。軸合わせ境界ボックスを直接計算することはできません。ただし、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）に対してこれを行います。あなたは最大4つの根を得るでしょう（あなたの楕円が縮退している場合、例えば、半径の1つがゼロである場合は少なくなります）。根の位置を評価すると、楕円のすべての極点が得られます。

今ほとんどあなたはそうです。楕円の境界ボックスを取得するのは、xmin、xmax、ymin、ymaxの4つの点をスキャンするのと同じくらい簡単です。

Btw - 楕円の方程式を見つけるのに問題がある場合：軸を中心に楕円が整列し、半径が2つで回転角度が中心の場合に縮小してみてください。

その場合の方程式になる：

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

Answer 4

私はhttp://www.iquilezles.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); 

Answer 5

このコードは、上記寄与コード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; 

Answer 6

は場合の式である（それは軸の長さ、中心および角度によって与えられる場合について、E参照。G。user1789690による回答）。巣は（x0、y0）と（x1、y1）と偏心している場合

すなわち、その後、

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

が、私は答えから式を導出

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

Eでありますuser1789690とJohan Nilssonによって

Answer 7

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

Answer 8

これは私が実装のためのOpenCVの矩形とポイントを持っている任意の向き

の楕円にフィット矩形を見つけるための私の関数である。

CG - 楕円の中心

サイズ - 楕円の長、短軸

角度 - 楕円

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

Answer 9

の向きあなたがOpenCVの/ C++で動作し、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; 
}