正多边形的高效打包算法
我正在寻找一种打包算法，它将正多边形减少为矩形和直角三角形。该算法应该尝试使用尽可能少的此类形状，并且应该相对容易实现（考虑到挑战的难度）。
如果可能的话，这个问题的答案应该解释建议算法中使用的一般启发法。
I'm looking for a packing algorithm which will reduce a regular polygon into rectangles and right triangles. The algorithm should attempt to use as few such shapes as possible and should be relatively easy to implement (given the difficulty of the challenge).
If possible, the answer to this question should explain the general heuristics used in the suggested algorithm.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
我认为对于规则多边形来说，答案相当简单。
找到对称轴，并在每个顶点与其镜像之间画一条线。这将多边形分成梯形。每个梯形都可以变成一个长方形和两个直角三角形。
I think the answer is fairly simple for regular polygons.
Find an axis of symmetry, and draw a line between each vertex and its mirror. This divides the polygon into trapezoids. Each trapezoid can be turned into a rectangle and two right triangles.
它不是专门的矩形 + 直角三角形，但研究镶嵌多边形的一个很好的研究点是 Voronoi 图和 Delaunay 三角剖分 和此处 和此处。
事实上，如果“直角三角形”足够好，这些保证可以为您进行三角测量，并且如果您确实需要的话，您总是可以将任何三角形分成两个直角三角形。或者，您可以砍掉三角形的“尖端”，以制作更多的直角三角形，并从直角三角形中制作一些矩形。
您还可以尝试剪耳，方法是径向扫动，如果您知道自己有相当规则的多边形，或者通过“剪掉最大的凸块”来实现。然后，将剩余的每个三角形分成两个以创建直角三角形。
（来源：eruciform.com）
您可以尝试通过以一种方式扫掠，然后以另一种方式扫掠以形成梯形并以不同的方式分割它，可以减少中断，但是您必须进行检查以确保您的扫掠线没有与另一条线相交。你总是可以夹住耳朵，即使是一些实际上是分形的东西。
然而，这有时会产生非常细小的三角形。您可以执行启发式方法，例如“取最大的”，而不是沿着边缘连续裁剪，但这需要更多时间，接近 O(n^2)。在大多数情况下，Delaunay/Vornoi 会做得更快，并且使用更少的细三角形。
It's not specifically rectangles + right triangles, but a good research point for looking into tesselating polygons is Voronoi Diagrams and Delaunay Triangulations and here and here.
In fact, if "just right triangles" is good enough, these are guaranteed to triangulate for you, and you can always split any triangle into two right triangles, if you really need those. Or you can chop off "tips" of triangles to make more right triangles and some rectangles out of the right-triangles.
You can also try ear-clipping, either by sweeping radially, if you know you have fairly regular polygons, or by "clipping the biggest convex chunk" off. Then, split each remaining triangle into two to create right triangles.
(source: eruciform.com)
You could try to make less breaks by sweeping one way and then the other to make a trapezoid and split it differently, but you then have to do a check to make sure that your sweep-line hasn't crossed another line someplace. You can always ear-clip, even with something practically fractal.
However, this sometimes creates very slim triangles. You can perform heuristics, like "take the biggest", instead of clipping continuously along the edge, but that takes more time, approaching O(n^2). Delaunay/Vornoi will do it more quickly in most cases, with less slim triangles.
您可以尝试“剪出”可以容纳的最大矩形多边形，留下一些剩余物。继续在剩下的东西上重复切割矩形，直到最终得到三角形的碎片。然后，如果需要，您可以将它们分成两个直角三角形。我不知道这是否总是会产生能够为您提供最少数量的矩形和直角三角形的解决方案。
You can try "cuting out" the largest rectangle that can fit in the polygon, leaving behind some leftovers. Keep repeating the cutting out of rectangles on the leftovers, until you end up with triangular pieces. Then, you can split them into two right triangles if necessary. I do not know if this will always yield solutions that will give you the least amount rectangles and right triangles.