如何计算多曲线的OBB？ [英] How to Compute OBB of Multiple Curves?
问题描述
看起来，每个OBB的联合个人曲线不对，它不是最小的覆盖范围。
查看此图片，如何计算红色框？
你还应该添加矢量形式的输入，所以我们可以测试你的数据...我会这样做：
-
计算每次旋转的最大垂直距离<$ c $对于每个角度部分计算的值是：
$ b
$ bvalue [actual_section] = max（distance [i] * cos（section_angle [i] -section_angle [actual_section]））
其中
i涵盖+/- 90 deg围绕实际截面角度，所以现在您可以获得每个角度的最大垂直距离...... - 挑选最佳解决方案
O（m）
查看0到90度的所有旋转并记住最小<强> OBB 区域。为了确保 OBB 对齐到截面角度和轴线的大小，该角度的
值和所有90度增量...围绕中心
计算每个角度的最大距离
O（n） $ c> m 角度（比如5度角，所以 m = 360/5 ）其中对于每个角度部分，您只记得最大距离点距离。
这不会导致最佳解决方案，但非常接近它。为了提高精度，您可以使用更多的角度部分，甚至可以用更小和更小的角度步长递归搜索找到的解决方案（无需在第一次运行后计算其他角度区域）。
我试图在 C ++ 中编写这个代码作为概念验证并使用您的图像（作为点的集合）作为输入，所以在这里结果，所以你有东西可以比较（用于调试目的）
灰色是图像中的检测点，绿色矩形是轴对齐 BBox 找到 OBBox 。水色点是每个角度间隔的最大距离，绿色点是
+/- 90deg neighb或角度间隔。我用 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;返回这个; }
// _ pnt2D * operator =（const _pnt2D& a）{... copy ... return this; }
};
struct _ang
{
double ang; //部分的中心角度
double dis; // ang部分的最大距离
double pdis; // +/- 90deg section的最大垂直距离
// inline
_ang（）{}
_ang（_ang& a）{* this = a; }
〜_ang（）{}
_ang * operator =（const _ang * a）{* this = * a;返回这个; }
// _ ang * operator =（const _ang& a）{... copy ... return this; }
};
const int angs = 400; //必须可以被4
整除int angs4 = angs>> 2;
const double dang = 2.0 * M_PI / double（angs）;
const double dang2 = 0.5 * dang;
_ang ang [angs];
列表< _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; （q =（DWORD *）bmp-> ScanLine [int（py）]，px = 0; p.x< bmp->宽度; p.x ++）
if（（q [int（px）]& 255）< 20）
pnt.add（p）
删除bmp;
//轴对齐bbox
bbox [0] = pnt [0];
bbox [1] = pnt [0]; （bbox [0] .x> pp-> x）的
（pp = pnt.dat，i = 0; i< pnt.num; i ++，pp ++） 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 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 {
AA->昂= A;
aa-> DIS = 0.0;
aa-> pdis = 0.0;
}
// ang []。dis
for（pp = pnt.dat，i = 0; i
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; Ĵ％= angs;
a =（dx * dx）+（dy * dy）;
if（ang [j] .dis }
;对于（bb = ang，j = 0; j
// ang [] .adis
; j ++，bb ++）
{
a = fabs（aa> ang-bb-> ang）; （a> M_PI）a =（2.0 * M_PI）-a;
; （a <= 0.5 * M_PI）
{
a = bb-> dis * cos（a）;
。
if（aa-> pdis< a）aa-> pdis = a; （b = 0，j = 0，i = 0;
）
}
//找到最佳方向的bbox（最佳角度为ang [j] .ang） 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;如果（（b> a）||（i == 0））{b = a; J =; }
}
//计算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部分，因为您已经获得了您的数据。
Given a number of curves，include line segments and circular arcs, how to compute the total OBB of all curves?
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:
- find center of axis aligned bbox
O(n) compute max distance in each angle
O(n)just create table for enough
mangles (like 5 deg step som = 360/5) where for each angle section you remember max distant point distance only.compute max perpendicular distance for each rotation
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]))where
icovers+/- 90 degaround actual section angle so now you got max perpendicular distances for each angle...pick best solution
O(m)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
valueof 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.
[Edit1]
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)
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 ...
Here C++ source:
//---------------------------------------------------------------------------
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:
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
You can ignore the // convert bmp -> pnt[] VCL part as you got your data already.
这篇关于如何计算多曲线的OBB？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
