在任意边界内填充任意多边形
我想知道是否有人可以向我指出适合我特定的多边形包装问题的最佳算法/启发式方法。我得到一个单一的多边形作为边界（凸面或凹面也可能包含孔）和一个单一的“填充”多边形（也可能是凸面或凹面，不包含孔），我需要用指定的数字填充边界多边形填充多边形。 （我正在二维工作）。
我发现的许多多边形填充启发法都假设边界和/或填充多边形将是矩形，并且填充多边形将具有不同的大小。就我而言，填充多边形可能不是矩形，但所有多边形都完全相同。
也许这是一种特殊类型的包装问题？如果有人对这种类型的多边形包装有定义，我会很乐意用谷歌搜索，但到目前为止我还没有找到任何足够相似的东西以发挥很大的作用。
谢谢。
I was wondering if anybody could point me to the best algorithm/heuristic which will fit my particular polygon packing problem. I am given a single polygon as a boundary (convex or concave may also contain holes) and a single "fill" polygon (may also be convex or concave, does not contain holes) and I need to fill the boundary polygon with a specified number of fill polygons. (I'm working in 2D).
Many of the polygon packing heuristics I've found assume that the boundary and/or filling polygons will be rectangular and also that the filling polygons will be of different sizes. In my case, the filling polygons may be non-rectangular, but all will be exactly the same.
Maybe this is a particular type of packing problem? If somebody has a definition for this type of polygon packing I'll gladly google away, but so far I've not found anything which is similar enough to be of great use.
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
你问的问题很难。为了正确地看待这一点，（更）简单的情况，即用不重叠的磁盘包装有界多边形的内部已经很困难，并且磁盘是最简单的“包装形状”（与您必须的任何其他形状）考虑方向以及尺寸和中心位置）。
事实上，我认为这是计算几何中的一个开放问题，以确定任意整数N和任意有界多边形区域（在欧几里德平面中），N 个内接非重叠圆盘的“最佳”封装（在覆盖多边形内部最大百分比的意义上）是多少，您可以自由选择每个圆盘的半径和中心位置。我确信“最佳”答案已知对于某些特殊的多边形形状（如矩形、圆形和三角形），但对于任意形状，您最好的“启发式”可能是：
我说“可能”是因为“最大的在先”并不总是将物品装入有限空间的最佳方式。您可以通过阅读装箱问题和背包问题。
编辑：第 2 步本身就很困难。一个合理的策略是选择多边形内部的任意点作为中心并“膨胀”圆盘，直到它接触边界或另一个圆盘（或两者），然后在继续膨胀的同时“滑动”圆盘使其保持在边界内，不与任何其他圆盘重叠，直到它被“捕获” - 与边界和/或其他圆盘至少有 2 个接触点。但将这种“滑动过程”形式化并不容易。即使你的滑动过程正确，这种策略也不能保证你会找到最大的“可写圆盘”——你的“局部最大”圆盘可能会被困在内部的“叶”中，该“叶”由一个将可用空间的“颈部”缩小到可以容纳较大磁盘的较大“波瓣”。
The question you ask is very hard. To put this in perspective, the (much) simpler case where you're packing the interior of your bounded polygon with non-overlapping disks is already hard, and disks are the simplest possible "packing shape" (with any other shape you have to consider orientation as well as size and center location).
In fact, I think it's an open problem in computational geometry to determine for an arbitrary integer N and arbitrary bounded polygonal region (in the Euclidean plane), what is the "optimal" (in the sense of covering the greatest percentage of the polygon interior) packing of N inscribed non-overlapping disks, where you are free to choose the radius and center location of each disk. I'm sure the "best" answer is known for certain special polygonal shapes (like rectangles, circles, and triangles), but for arbitrary shapes your best "heuristic" is probably:
I say "probably" because "largest first" isn't always the best way to pack things into a confined space. You can dig into that particular flavor of craziness by reading about the bin packing problem and knapsack problem.
EDIT: Step 2 by itself is hard. A reasonable strategy would be to pick an arbitrary point on the interior of the polygon as the center and "inflate" the disk until it touches either the boundary or another disk (or both), and then "slide" the disk while continuing to inflate it so that it remains inside the boundary without overlapping any other disks until it is "trapped" - with at least 2 points of contact with the boundary and/or other disks. But it isn't easy to formalize this "sliding process". And even if you get the sliding process right, this strategy doesn't guarantee that you'll find the biggest "inscribable disk" - your "locally maximal" disk could be trapped in a "lobe" of the interior which is connected by a narrow "neck" of free space to a larger "lobe" where a larger disk would fit.
感谢您的回复，我的要求是这样我能够通过不必处理方向来进一步简化问题，然后我只需真正担心填充元素的边界框即可进一步简化。通过这两种简化，问题变得更加容易，我使用了类似条带的填充算法和空间哈希网格（因为存在不允许我填充的现有元素）。
通过这种方法，我简单地将填充区域划分为条带，并创建一个空间哈希网格来注册填充区域内的现有元素。我创建了第二个空间哈希网格来注册填充区域（因为我的条纹不能保证在边界区域内，这使得检查我的填充元素是否在填充区域中更快一些，因为我可以查询网格，如果我要放置填充元素的所有网格都已满，我知道填充元素位于填充区域内）。之后，我迭代每个条带并在哈希网格允许的位置放置一个填充元素。这当然不是最佳解决方案，但它最终满足了我的特定情况所需的全部要求，而且速度也相当快。我从 此处。我从这篇文章中得到了用条纹填充的想法。
Thanks for the replies, my requirements were such that I was able to further simplify the problem by not having to deal with orientation and I then even further simplified by only really worrying about the bounding box of the fill element. With these two simplifications the problem became much easier and I used a stripe like filling algorithm in conjunction with a spatial hash grid (since there were existing elements I was not allowed to fill over).
With this approach I simply divided the fill area into stripes and created a spatial hash grid to register existing elements within the fill area. I created a second spatial hash grid to register the fill area (since my stripes were not guaranteed to be within the bounding area, this made checking if my fill element was in the fill area a little faster since I could just query the grid and if all grids where my fill element were to be placed, were full, I knew the fill element was inside the fill area). After that, I iterated over each stripe and placed a fill element where the hash grids would allow. This is certainly not an optimal solution, but it ended up being all that was required for my particular situation and pretty fast as well. I found the required information about creating a spatial hash grid from here. I got the idea for filling by stripes from this article.
这类问题在几何上求解起来非常复杂。
如果你能接受一个好的解决方案而不是100%最优的
那么你可以用栅格算法来解决它。
将边界多边形绘制（光栅化）到内存中
图像和填充多边形到另一个内存图像中。
然后，您可以更轻松地搜索填充多边形的位置
通过将两个图像叠加来拟合边界多边形
填充多边形的各种（X，Y）偏移并检查
像素值。
当您找到填充多边形适合的位置时，
您清除边界多边形中的像素并重复
直到不再有适合填充多边形的地方。
google搜索的关键词是：光栅化、覆盖、算法
This type of problem is very complex to solve geometrically.
If you can accept a good solution instead of the 100% optimal
solution then you can to solve it with a raster algorithm.
You draw (rasterize) the boundary polygon into one in-memory
image and the fill polygon into another in-memory image.
You can then more easily search for a place where the fill polygon will
fit in the boundary polygon by overlaying the two images with
various (X, Y) offsets for the fill polygon and checking
the pixel values.
When you find a place that the fill polygon fits,
you clear the pixels in the boundary polygon and repeat
until there are no more places where the fill polygon fits.
The keywords to google search for are: rasterization, overlay, algorithm
如果您的填充多边形是拼图块的形状，许多算法将错过互锁对齐。 （我不知道在这种情况下该建议什么）
当边界远大于边界时，解决一般问题的一种方法效果很好
填充碎片就是用碎片以最好的方式平铺一个无限的平面，然后在这个平面上寻找边界的最佳对齐方式。
If your fill polygon is the shape of a jigsaw piece, many algorithms will miss the interlocking alignment. (I don't know what to suggest in that case)
One approach to the general problem that works well when the boundary is much larger than
the fill pieces is to tile an infinite plane with the pieces in the best way you can, and then look for the optimum alignment of the boundary on this plane.