algorithm - applications - computational geometry中文



如何計算多曲線的OBB? (1)

給定許多曲線(包括線段和圓弧),如何計算所有曲線的總OBB?

似乎各個曲線的每個OBB的並集都不正確,這不是最小覆蓋率。

查看這張圖片,如何計算紅色框?


您還應該以矢量形式添加輸入,以便我們可以對您的數據進行測試...我將採用以下方式:

  1. 找出軸對齊的中心bbox O(n)
  2. 計算每個角度的最大距離 O(n)

    只需創建足夠 m 角度的表即可(例如5度步長,因此 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 ++ 編寫此 代碼 作為概念證明,並使用您的圖像(按點集處理)作為輸入,因此這裡的結果是您可以比較的內容(用於調試)

灰色 是從圖像中檢測到的點, 綠色 矩形是與軸對齊的 BBox 紅色 矩形是 OBBox 。 在每個角度間隔中找到最大距離的 水色 點,在 +/-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[]; 相同 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部分,因為已經有數據了。





computational-geometry