如何计算多条曲线的OBB？

Question

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

似乎每个OBB的各个曲线的联合不正确，这不是最小的覆盖范围。

检查此照片，如何计算红色框？

Answer 1

你还应该添加矢量形式输入，所以我们可以对数据进行测试...我将接近这样的：

1. 发现轴的中心对齐BBOX O(n)

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

   只需创建足够的表格m角度（如5 deg step m = 360/5）对于每个角度区域，您只记得最大远距离点距离。

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

   因此每个角部分的计算值是：

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

   其中i占地面积+/- 90 deg各地的实际节角所以现在你得到了最大垂直每个角度的距离...

4. 挑最好的解决办法O(m)

   所以看所有旋转从0到90度，记得有最小OBB区域之一。只是要确保OBB对准部分的角度和轴系的大小是角度的value和所有的90度增量...围绕中心

   

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

[EDIT1]

我试着在C++实现代码作为概念验证和使用您的图像（如设定点的处理）作为输入，所以这里的结果，所以你得到的东西来比较（用于调试）

灰色检测到来自你的形象加分，绿色重ctangle轴对齐BBox红色矩形发现OBBox。 aqua点被发现每个角度间隔的最大距离和绿色点是最大垂直距离+/-90deg相邻角度间隔。我用400角度，你可以看到结果是相当接近... 360/400 deg准确性所以这种方法效果很好...

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

我用我的动态列表模板所以：

List<double> xxx;相同double xxx[];
xxx.add(5);增加5结束列表的
xxx[7]访问数组元素（安全）
xxx.dat[7]访问数组元素（不安全的，但快速直达）
xxx.num是数组
xxx.reset()的实际使用的大小将清除阵列，并设置xxx.num=0
xxx.allocate(100)为100项目预分配的空间

您可以忽略// convert bmp -> pnt[] VCL部分，因为您已经获得了您的数据。