我正在寻找一种打包算法,该算法会将不规则的多边形减少为矩形和直角三角形.该算法应尝试使用尽可能少的这种形状,并且应相对容易实现(考虑到挑战的难度).在可能的情况下,还应优先选择矩形而不是三角形.
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
替代文字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:
我意识到有很多细节需要填写,但是我认为从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.
更多推荐
不规则多边形的高效打包算法
发布评论