不规则多边形的有效包装算法

Question

我正在寻找一种打包算法,它将不规则多边形缩小为矩形和直角三角形.该算法应该尝试使用尽可能少的这种形状,并且应该相对容易实现(考虑到挑战的难度).在可能的情况下,它还应该优先考虑三角形的矩形

如果可能,这个问题的答案应该解释建议算法中使用的一般启发式方法.

对于小于100个顶点的不规则多边形,这应该在确定的时间内运行.

目标是为外行人产生不规则多边形的"合理"分解.

应用于解决方案的第一个启发式算法将确定多边形是规则的还是不规则的.在正多边形的情况下,我们将使用我的类似文章中关于常规多边形的方法:正则多边形的有效填充算法

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

Answer 1

我不知道这是否会给出最佳答案,但它至少会给出一个答案:

1. 计算给定多边形的Delaunay三角剖分.有一些标准的算法可以很快地运行100个或更少的顶点(例如,参见这个库.)使用Delaunay三角测量应该确保你没有太多细长的三角形.
2. 通过将高度从最大角度降低到相对侧,将任何非右三角形划分为两个直角三角形.
3. 搜索可以组合成矩形的三角形:任何两个全等直角三角形(不是镜像)共享一个斜边.我怀疑在一般情况下不会有太多这些,除非你的不规则多边形有很多直角开始.

我意识到要填写很多细节,但我认为从Delaunay三角测量开始可能是要走的路.平面中的Delaunay三角剖分可以有效地计算,并且它们通常看起来非常"自然".

编辑添加:因为我们在ad-hoc heuristicville,除了在其他答案中讨论的贪婪算法,你还应该考虑某种分而治之的策略.如果形状像您的示例一样是非凸的,则通过反复切割从反射顶点到另一个顶点的方式将其划分为凸形,尽可能接近平分反射角.一旦你将形状分成凸片,我会考虑接下来将凸片分成具有漂亮"基部"的片,其中至少一侧的片在其末端具有两个锐角或直角.如果任何一件没有这样的"底座",你应该能够沿着一件直径将它分成两部分,然后得到两件新件,每件都有一个"底座"(我认为).这应该减少处理有点类梯形的凸多边形的问题,并且从那里贪婪算法应该做得很好.我认为这个算法会以相当自然的方式细分原始形状,直到你得到有点类型的梯形碎片.

Answer 2

我希望我有时间玩这个,因为这听起来像一个非常有趣的问题!

我的第一个想法(从上面的图表看)将是寻找相同方向的2个相邻的直角.我确信不会捕捉到矩形有用的所有情况,但从用户的角度来看,这是一个明显的例子(外侧的方角=这应该是一个矩形).

一旦找到相邻的一对直角,取短腿的长度,就有一个矩形.从左边的多边形中减去这个,然后重复.当没有更明显的外部矩形可以移除时,那就做你正常的平铺事情(彼得的回答听起来很棒).

免责声明:我不是这方面的专家,我甚至没有尝试过......