gpt4 book ai didi

algorithm - 如何计算多条曲线的 OBB?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:20:06 26 4
gpt4 key购买 nike

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

似乎各个曲线的每个 OBB 的并集都不对,这不是最小覆盖。

查看这张图,红框是怎么计算的?

img

最佳答案

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

  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 度增量......围绕中心

    sketch

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

[编辑1]

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

example

灰色 是从您的图像中检测到的点,绿色 矩形是轴对齐的 BBox 红色 矩形被发现OBBoxaqua 点是每个角度间隔的最大距离,green 点是 +/-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 部分,因为您已经获得了数据。

我建议也看看我的:

关于algorithm - 如何计算多条曲线的 OBB?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42989829/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com