如何计算多条曲线的OBB? [英] How to Compute OBB of Multiple Curves?

问题描述

给定多条曲线，包括线段和圆弧，如何计算所有曲线的总OBB?

Given a number of curves，include line segments and circular arcs, how to compute the total OBB of all curves?

似乎各个曲线的每个OBB的并集不对，不是最小覆盖率.

It seems that the union of each OBB of the individual curves does not right, it's not the minimal coverage.

看这张图，红框怎么算?

Check this picture, how to compute the red box?

推荐答案

你还应该添加向量形式的输入，以便我们可以测试你的数据......我会这样处理:

you should also add the input in vector form so we can test on your data ... I would approach like this:

1. 找到轴对齐bbox的中心O(n)

2. 计算每个角度的最大距离O(n)

只需为足够的 m 角度(例如 5 度步长，所以 m = 360/5)创建表格，其中对于每个角度部分，您只记得最大远点距离.

just create table for enough m angles (like 5 deg step so m = 360/5) where for each angle section you remember max distant point distance only.

计算每次旋转的最大垂直距离O(m^2)

所以对于每个角截面计算值是:

so for each angle section compute value that is:

value[actual_section] = max(distance[i]*cos(section_angle[i]-section_angle[actual_section]))

其中 i 覆盖了实际截面角度周围的 +/- 90 度 所以现在你得到了每个角度的最大垂直距离...

where i covers +/- 90 deg around actual section angle so now you got max perpendicular distances for each angle...

选择最佳解决方案O(m)

所以查看从 0 到 90 度的所有旋转，并记住具有最小 OBB 区域的旋转.只是为了确保 OBB 与截面角度对齐，轴的大小是该角度的 value 和所有 90 度增量......围绕中心

so look all rotations from 0 to 90 degrees and remember the one that has minimal OBB area. Just to be sure the OBB is aligned to section angle and size of axises is the value of that angle and all the 90 deg increments... around center

这不会导致最佳解决方案，但非常接近.为了提高精度，您可以使用更多的角度部分，甚至可以用越来越小的角度步长递归搜索找到的解决方案(第一次运行后无需计算其他角度区域.

This will not result in optimal solution but very close to it. To improve precision you can use more angle sections or even recursively search around found solution with smaller and smaller angle step (no need to compute the other angle areas after first run.

我尝试在 C++ 中对此进行编码，作为概念证明，并使用您的图像(作为一组点处理)作为输入，因此这里是结果，以便您可以进行比较(用于调试目的)

I tried to code this in C++ as proof of concept and use your image (handled as set of points) as input so here the result so you got something to compare to (for debugging purposes)

灰色 是从您的图像中检测到的点，绿色 矩形是轴对齐的 BBox 找到 红色 矩形OBBox.aqua 点是每个角度间隔的最大距离，绿色 点是 +/-90deg 相邻角度间隔的最大垂直距离.我使用了 400 角度，你可以看到结果非常接近...... 360/400 deg 精度所以这种方法效果很好......

gray are detected points from your image, green rectangle is axis aligned BBox the red rectangle is found OBBox. The aqua points are found max distance per angle interval and green dots are max perpendicular distance for +/-90deg neighbor angle intervals. I used 400 angles and as you can see the result is pretty close ... 360/400 deg accuracy so this approach works well ...

这里是 C++ 源代码:

//---------------------------------------------------------------------------
struct _pnt2D
    {
    double x,y;
    // inline
    _pnt2D()    {}
    _pnt2D(_pnt2D& a)   { *this=a; }
    ~_pnt2D()   {}
    _pnt2D* operator = (const _pnt2D *a) { *this=*a; return this; }
    //_pnt2D* operator = (const _pnt2D &a) { ...copy... return this; }
    };
struct _ang
    {
    double  ang;    // center angle of section
    double  dis;    // max distance of ang section
    double pdis;    // max perpendicular distance of +/-90deg section
    // inline
    _ang()  {}
    _ang(_ang& a)   { *this=a; }
    ~_ang() {}
    _ang* operator = (const _ang *a) { *this=*a; return this; }
    //_ang* operator = (const _ang &a) { ...copy... return this; }
    };
const int    angs=400;  // must be divisible by 4
const int    angs4=angs>>2;
const double dang=2.0*M_PI/double(angs);
const double dang2=0.5*dang;
_ang ang[angs];
List<_pnt2D> pnt;
_pnt2D bbox[2],obb[4],center;
//---------------------------------------------------------------------------
void compute_OBB()
    {
    _pnt2D ppp[4];
    int i,j; double a,b,dx,dy;
    _ang *aa,*bb;
    _pnt2D p,*pp; DWORD *q;
    // convert bmp -> pnt[]
    pnt.num=0;
    Graphics::TBitmap *bmp=new Graphics::TBitmap;
    bmp->LoadFromFile("in.bmp");
    bmp->HandleType=bmDIB;
    bmp->PixelFormat=pf32bit;
    for (p.y=0;p.y<bmp->Height;p.y++)
     for (q=(DWORD*)bmp->ScanLine[int(p.y)],p.x=0;p.x<bmp->Width;p.x++)
      if ((q[int(p.x)]&255)<20)
       pnt.add(p);
    delete bmp;
    // axis aligned bbox
    bbox[0]=pnt[0];
    bbox[1]=pnt[0];
    for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++)
        {
        if (bbox[0].x>pp->x) bbox[0].x=pp->x;
        if (bbox[0].y>pp->y) bbox[0].y=pp->y;
        if (bbox[1].x<pp->x) bbox[1].x=pp->x;
        if (bbox[1].y<pp->y) bbox[1].y=pp->y;
        }
    center.x=(bbox[0].x+bbox[1].x)*0.5;
    center.y=(bbox[0].y+bbox[1].y)*0.5;
    // ang[] table init
    for (aa=ang,a=0.0,i=0;i<angs;i++,aa++,a+=dang)
        {
        aa->ang=a;
        aa-> dis=0.0;
        aa->pdis=0.0;
        }
    // ang[].dis
    for (pp=pnt.dat,i=0;i<pnt.num;i++,pp++)
        {
        dx=pp->x-center.x;
        dy=pp->y-center.y;
        a=atan2(dy,dx);
        j=floor((a/dang)+0.5); if (j<0) j+=angs; j%=angs;
        a=(dx*dx)+(dy*dy);
        if (ang[j].dis<a) ang[j].dis=a;
        }
    for (aa=ang,i=0;i<angs;i++,aa++) aa->dis=sqrt(aa->dis);
    // ang[].adis
    for (aa=ang,i=0;i<angs;i++,aa++)
     for (bb=ang,j=0;j<angs;j++,bb++)
        {
        a=fabs(aa->ang-bb->ang);
        if (a>M_PI) a=(2.0*M_PI)-a;
        if (a<=0.5*M_PI)
            {
            a=bb->dis*cos(a);
            if (aa->pdis<a) aa->pdis=a;
            }
        }
    // find best oriented bbox (the best angle is ang[j].ang)
    for (b=0,j=0,i=0;i<angs;i++)
        {
        dx =ang[i].pdis; i+=angs4; i%=angs;
        dy =ang[i].pdis; i+=angs4; i%=angs;
        dx+=ang[i].pdis; i+=angs4; i%=angs;
        dy+=ang[i].pdis; i+=angs4; i%=angs;
        a=dx*dy; if ((b>a)||(i==0)) { b=a; j=i; }
        }
    // compute endpoints for OBB
    i=j;
    ppp[0].x=ang[i].pdis*cos(ang[i].ang);
    ppp[0].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    ppp[1].x=ang[i].pdis*cos(ang[i].ang);
    ppp[1].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    ppp[2].x=ang[i].pdis*cos(ang[i].ang);
    ppp[2].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    ppp[3].x=ang[i].pdis*cos(ang[i].ang);
    ppp[3].y=ang[i].pdis*sin(ang[i].ang); i+=angs4; i%=angs;
    obb[0].x=center.x+ppp[0].x+ppp[3].x;
    obb[0].y=center.y+ppp[0].y+ppp[3].y;
    obb[1].x=center.x+ppp[1].x+ppp[0].x;
    obb[1].y=center.y+ppp[1].y+ppp[0].y;
    obb[2].x=center.x+ppp[2].x+ppp[1].x;
    obb[2].y=center.y+ppp[2].y+ppp[1].y;
    obb[3].x=center.x+ppp[3].x+ppp[2].x;
    obb[3].y=center.y+ppp[3].y+ppp[2].y;
    }
//---------------------------------------------------------------------------

我使用了我的动态列表模板，因此:

I used mine dynamic list template so:

Listxxx; 等同于 double xxx[];
xxx.add(5); 将 5 添加到列表末尾
xxx[7] 访问数组元素(安全)
xxx.dat[7] 访问数组元素(不安全但快速的直接访问)
xxx.num 是数组实际使用的大小
xxx.reset() 清空数组并设置xxx.num=0
xxx.allocate(100) 为 100 个项目预分配空间

List<double> xxx; is the same as double xxx[];
xxx.add(5); adds 5 to end of the list
xxx[7] access array element (safe)
xxx.dat[7] access array element (unsafe but fast direct access)
xxx.num is the actual used size of the array
xxx.reset() clears the array and set xxx.num=0
xxx.allocate(100) preallocate space for 100 items

你可以忽略//转换bmp ->pnt[] VCL 部分，因为您已经获得了数据.

You can ignore the // convert bmp -> pnt[] VCL part as you got your data already.

我建议也看看我的:

• 3D OBB 近似

这篇关于如何计算多条曲线的OBB?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！