algorithm - 正多边形的高效打包算法

Question

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

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

Answer 1

我认为对于正多边形来说答案相当简单。

找到一个对称轴，并在每个顶点和它的镜像之间画一条线。这将多边形划分为梯形。每个梯形可以变成一个矩形和两个直角三角形。

Answer 2

它不是具体的矩形 + 直角三角形，但是研究镶嵌多边形的一个很好的研究点是Voronoi Diagrams 和 Delaunay Triangulations以及here和here。

事实上，如果“恰到好处的三角形”足够好，这些保证可以为您进行三角剖分，如果您真的需要，您可以随时将任何三角形分成两个直角三角形。或者，您可以切掉三角形的“尖端”以制作更多直角三角形和一些直角三角形中的矩形。

如果你知道你有相当规则的多边形，你也可以尝试剪耳，或者通过径向扫过，或者通过“剪掉最大的凸块”。然后，将每个剩余的三角形分成两部分以创建直角三角形。

_{（来源：eruciform.com）}

您可以尝试通过一种方式扫过然后另一种方式来制作梯形并以不同方式分割它来减少中断，但是您必须进行检查以确保您的扫线没有在某个地方越过另一条线。你总是可以使用耳夹，即使是一些几乎是分形的东西。

然而，这有时会产生非常细的三角形。您可以执行启发式算法，例如“取最大”，而不是沿边缘连续裁剪，但这需要更多时间，接近 O(n^2)。在大多数情况下，Delaunay/Vornoi 会做得更快，三角形更少。

Answer 3

您可以尝试“切出”可以容纳在多边形中的最大矩形，留下一些剩余部分。继续在剩菜上重复切割矩形，直到你得到三角形的碎片。然后，如有必要，您可以将它们分成两个直角三角形。我不知道这是否总是会产生最少量的矩形和直角三角形的解决方案。