如何计算椭圆的轴对齐边界框？-Java 学习之路

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

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

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

Edit: to clarify, I need the axis-aligned bounding box, i.e. it should not be rotated with the ellipse, but stay aligned with the x axis so transforming the bounding box won't work.

9 回答

0

我认为最有用的公式就是这个 . 从原点的角度phi旋转的省略号具有以下等式：

其中（h，k）是中心，a和b是长轴和短轴的大小，t是从-pi到pi的变化 .

从那里，您应该能够推导出哪个t dx / dt或dy / dt变为0 .

回复于 2024-04-26T13:36:58+08:00

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

回复于 2024-04-26T13:36:58+08:00

2
您可以尝试将参数化方程用于以任意角度旋转的椭圆：
```
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]
```
哪个应该为你提供很多解决方案（其中两个你感兴趣），将其插回[1]以获得你的最大和最小x .

重复[2]：
```
0 = dy/dt = b*cos(t)*cos(phi) - a*sin(t)*sin(phi)
```
=>
```
tan(t) = b*cot(phi)/a  [4]
```
Lets try an example:

考虑（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
```
回复于 2024-04-26T13:36:58+08:00

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

回复于 2024-04-26T13:36:58+08:00

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

无论如何，一般原理是这样的：你不能直接计算轴对齐的边界框 . 但是，您可以将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;
```
回复于 2024-04-26T13:36:58+08:00
0
如果椭圆由其 foci and eccentricity 给出，则给出该情况的公式（对于由轴长度，中心和角度给出的情况，参见例如用户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)
```
我从用户1789690和Johan Nilsson的答案中得出了公式 .
回复于 2024-04-26T13:36:58+08:00

如果使用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;
}

回复于 2024-04-26T13:36:58+08:00

此代码基于上面贡献的代码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;

回复于 2024-04-26T13:36:58+08:00

这是我的功能，用于找到任意方向的椭圆形紧密拟合矩形

我有opencv rect和实现点：

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

回复于 2024-04-26T13:36:58+08:00

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

9 回答

相关问题