不规则多边形的高效打包算法 [英] Efficient Packing Algorithm for Irregular Polygons

问题描述

我正在寻找一种打包算法，该算法会将不规则的多边形减少为矩形和直角三角形.该算法应尝试使用尽可能少的这种形状，并且应相对容易实现(考虑到挑战的难度).在可能的情况下，还应优先选择矩形而不是三角形.

I'm looking for a packing algorithm which will reduce an irregular 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). It should also prefer rectangles over triangles where possible.

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

If possible, the answer to this question should explain the general heuristics used in the suggested algorithm.

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

This should run in deterministic time for irregular polygons with less than 100 vertices.

目标是为外行制作不规则多边形的合理"分解.

The goal is to produce a "sensible" breakdown of the irregular polygon for a layman.

应用于求解的第一个试探法将确定多边形是规则的还是不规则的.对于常规多边形，我们将使用我在类似文章中概述的有关常规多边形的方法:

The first heuristic applied to the solution will determine if the polygon is regular or irregular. In the case of a regular polygon, we will use the approach outlined in my similar post about regular polys: Efficient Packing Algorithm for Regular Polygons

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

推荐答案

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

I don't know if this would give the optimal answer, but it would at least give an answer:

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

1. Compute a Delaunay triangulation for the given polygon. There are standard algorithms to do this which will run very quickly for 100 vertices or fewer (see, for example, this library here.) Using a Delaunay triangulation should ensure that you don't have too many long, thin triangles.
2. Divide any non-right triangles into two right triangles by dropping an altitude from the largest angle to the opposite side.
3. Search for triangles that you can combine into rectangles: any two congruent right triangles (not mirror images) which share a hypotenuse. I suspect there won't be too many of these in the general case unless your irregular polygon had a lot of right angles to begin with.

我意识到有很多细节需要填写，但是我认为从Delaunay三角剖分开始可能是可行的方法.平面中的Delaunay三角剖分可以有效地计算，并且通常看起来很自然".

I realize that's a lot of detail to fill in, but I think starting with a Delaunay triangulation is probably the way to go. Delaunay triangulations in the plane can be computed efficiently and they generally look quite "natural".

编辑后添加:由于我们处于临时启发式，除了其他答案中讨论的贪婪算法外，您还应该考虑某种分而治之的策略.如果形状不像您的示例那样是凸形的，则可以通过以尽可能接近等分反射角的方式从反射顶点重复切割到另一个顶点来将其划分为凸形.将形状分成凸形块之后，我将考虑接下来将凸形块分成具有良好底"的块，这些块的至少一侧在其末端具有两个锐角或直角.如果没有一块具有这样的基数"，您应该可以将其沿其直径分为两部分，并得到两个新的块，每片都有一个基数"(我认为).这样可以减少处理凸类多边形梯形的问题，并且从那里开始，贪婪算法应该可以很好地解决这个问题.我认为该算法将以一种相当自然的方式细分原始形状，直到您获得某种梯形的碎片为止.

EDITED TO ADD: since we're in ad-hoc heuristicville, in addition to the greedy algorithms being discussed in other answers you should also consider some kind of divide and conquer strategy. If the shape is non-convex like your example, divide it into convex shapes by repeatedly cutting from a reflex vertex to another vertex in a way that comes as close to bisecting the reflex angle as possible. Once you've divided the shape into convex pieces, I'd consider next dividing the convex pieces into pieces with nice "bases", pieces with at least one side having two acute or right angles at its ends. If any piece doesn't have such a "base" you should be able to divide it in two along a diameter of the piece, and get two new pieces which each have a "base" (I think). This should reduce the problem to dealing with convex polygons which are kinda-sorta trapezoidal, and from there a greedy algorithm should do well. I think this algorithm will subdivide the original shape in a fairly natural way until you get to the kinda-sorta trapezoidal pieces.

这篇关于不规则多边形的高效打包算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！