11

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

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

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

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

应用于解决方案的第一个启发式将确定多边形是规则的还是不规则的。对于正多边形，我们将使用我在关于正多边形的类似文章中概述的方法：正多边形的高效打包算法

替代文字 http://img401.imageshack.us/img401/6551/samplebj.jpg

4

2 回答 2

8

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

  1. 计算给定多边形的 Delaunay 三角剖分。有一些标准算法可以在 100 个或更少的顶点上非常快速地运行（例如，请参阅此处的这个库。）使用 Delaunay 三角剖分应该确保您没有太多又长又细的三角形。
  2. 通过将高度从最大角度下降到相对侧，将任何非直角三角形分成两个直角三角形。
  3. 搜索可以组合成矩形的三角形：任何两个共享斜边的全等直角三角形（不是镜像）。我怀疑在一般情况下不会有太多这些，除非你的不规则多边形一开始就有很多直角。

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

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

于 2010-07-22T21:42:28.537 回答
7

我希望我有时间玩这个，因为这听起来是一个非常有趣的问题！

我的第一个想法（从上面的图表中）是寻找两个相邻的直角转向相同的方向。我敢肯定，这不会捕捉到矩形会有所帮助的所有情况，但从用户的角度来看，这是一个明显的情况（外面的方角 = 这应该是一个矩形）。

一旦你找到了一对相邻的直角，取短腿的长度，就会有一个矩形。从左边的多边形中减去这个，然后重复。当没有更明显的外部矩形要删除时，然后在上面做你正常的平铺事情（彼得的回答听起来很棒）。

免责声明：我不是这方面的专家，我什至没有尝试过......

于 2010-07-22T22:19:07.313 回答