如何计算椭圆的轴对齐边界框？

如果椭圆的长轴是垂直的或水平的,那么很容易计算边界框,但是当椭圆旋转时呢？

到目前为止,我能想到的唯一方法是计算周边的所有点并找到最大/最小x和y值.似乎应该有一个更简单的方法.

如果有一个函数(在数学意义上)描述一个任意角度的椭圆,那么我可以用它的导数来找到斜率为零或未定义的点,但我似乎找不到一个.

编辑:为了澄清,我需要轴对齐的边界框,即它不应该与椭圆一起旋转,但保持与x轴对齐,因此转换边界框将不起作用.

1> Mike Tunnicl..：

---

您可以尝试将参数化方程用于以任意角度旋转的椭圆:

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,并且通过角度phi旋转.

然后,您可以区分并求解gradient = 0:

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

=>

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

哪个应该给你很多t(你感兴趣的两个)的解决方案,将其插回[1]以获得你的最大和最小x.

重复[2]:

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

=>

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

让我们试试一个例子:

考虑(0,0)处的椭圆,a = 2,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

我们对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

---

这是python实现https://gist.github.com/smidm/b398312a13f60c24449a2c7533877dc0。

2> 小智..：

---

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

3> Nils Pipenbr..：

---

这是相对简单的,但有点难以解释,因为你没有给我们你代表椭圆的方式.有很多方法可以做到这一点..

无论如何,一般原则是这样的:你不能直接计算轴对齐的边界框.但是,您可以将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)执行此操作.您将获得最多四个根(如果您的椭圆退化,则更少,例如,其中一个半径为零).评估根部的位置,得到椭圆的所有极值点.

现在你快到了.获取椭圆的边界框就像扫描这四个点的xmin,xmax,ymin和ymax一样简单.

顺便说一句 - 如果你在找到椭圆方程时遇到问题:尝试将它缩小到一个轴对齐的椭圆,中心有两个半径和一个旋转角度.

如果这样做,方程式变为:

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