algorithm - 不规则多边形的高效打包算法

Question

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

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

对于少于 100 个顶点的不规则多边形，这应该在确定性时间内运行。

目标是为外行生成不规则多边形的“合理”分解。

应用于解决方案的第一个试探法将确定多边形是规则的还是不规则的。对于正多边形，我们将使用我关于正多边形的类似帖子中概述的方法:Efficient Packing Algorithm for Regular Polygons

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

Answer 1

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

1. 计算给定多边形的 Delaunay 三角剖分。有执行此操作的标准算法，对于 100 个或更少的顶点(参见，例如，this library here.)运行速度非常快。使用 Delaunay 三角剖分应确保您没有太多又长又细的三角形。
2. 通过从最大角到对边降低一个高度，将任何非直角三角形分成两个直角三角形。
3. 搜索可以组合成矩形的三角形:共享一条斜边的任意两个全等直角三角形(不是镜像)。我怀疑在一般情况下不会有太多这样的情况，除非您的不规则多边形开始时有很多直角。

我意识到需要填写很多细节，但我认为从 Delaunay 三角剖分开始可能是可行的方法。可以高效地计算平面中的 Delaunay 三角剖分，它们通常看起来非常“自然”。

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