正则多边形的高效包装算法

我正在寻找一种包装算法，它会将正多边形缩减为矩形和直角三角形。该算法应该尝试尽可能少地使用这种形状，并且应该相对容易实施（鉴于挑战的难度）。正则多边形的高效包装算法

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

来源

2010-07-21 Steve

这是算法类还是计算机图形类？ – eruciform 2010-07-21 03:34:22

这不适合上课。我不在学校。 – Steve 2010-07-21 03:35:50

事实上，如果他们可以为iPhone，Mac桌面和.net编程，我可能愿意给一个能够很好地回答问题的人。 ;） – Steve 2010-07-21 03:38:21

我认为答案是相当简单的常规多边形。

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

来源

2010-07-21 05:05:05

通过证明这会产生最小数量的图块，您可以获得额外的功劳。 :) – Svante 2010-07-21 09:33:33

我现在认为这实际上是最佳的:-) – Mau 2010-07-21 12:48:23

不，它并不总是最佳的。以两边平行于x = 0轴的正六边形为例。然后这个算法产生2个矩形和4个直角三角形，但是1个矩形和4个三角形就足够了。尽管如此，解决方案可能足够好并且易于实施。 – abc 2010-07-21 13:19:31

它不是特别的矩形+直角三角形，但是研究镶嵌多边形的好研究点是Voronoi Diagrams and Delaunay Triangulations和here和here。实际上，如果“恰到好处的三角形”足够好，那么这些保证可以为您进行三角剖分，并且如果您真的需要这些三角形，您总是可以将任何三角形分成两个直角三角形。或者，您可以切掉三角形的“尖端”，以制作更多直角三角形和一些矩形。

您也可以尝试ear-clipping，或者通过径向扫掠，如果您知道自己有相当规则的多边形，或者“截断最大的凸块”。然后，将每个剩余的三角形分成两个以创建直角三角形。

polygon http://static.eruciform.com/images/polygon.png

您可以尝试通过扫描一个方式，然后将另一做出梯形，使更少的休息和不同的拆分它，但你必须做一个检查，以确保您的扫描线不是招在另一条线上划过一条线。即使实际上是分形的，你总是可以耳夹。

但是，这有时会创建非常纤细的三角形。你可以执行启发式操作，比如“最大化”，而不是沿着边缘连续剪裁，但是需要更多时间，接近O（n^2）。在大多数情况下，Delaunay/Vornoi会更快速地完成这项工作，而不需要很小的三角形。

来源

2010-07-21 03:38:20 eruciform

绝对必须是矩形和直角三角形。我知道这听起来很奇怪，但这是用户需求。 – Steve 2010-07-21 03:41:00

已更新。你可以很容易地将任何三角形变成直角三角形和矩形。 – eruciform 2010-07-21 03:44:08

Delaunay三角剖分在这里并不理想，因为它们在中间引入了额外的不必要的点。每个内部点都可以“拖动”到相邻的多边形顶点，并且剩下一小部分三角形。 – 2010-07-21 06:24:03

你可以尝试“切出”the largest rectangle that can fit in the polygon，留下一些剩菜。继续重复在剩余物上切出长方形，直到最后得到三角形碎片。然后，如有必要，可以将它们分成两个直角三角形。我不知道这是否总能产生能给你最少量的矩形和直角三角形的解决方案。

来源

2010-07-21 03:56:13

我认为这不是一个好主意：尽可能多地吃掉第一个矩形区域，然后不会留下“最简单”的形状。 – Mau 2010-07-21 12:30:28

不清楚他的要求是什么。最少的总体形状或大多数面积最小的形状...... – eruciform 2010-07-21 14:13:49

对于规则的多边形，它仍然会给你“很好”的形状。再次，我不知道这是否会给你“最优化”的解决方案。 – 2010-07-21 19:58:33

正则多边形的高效包装算法

回答

相关问题