在任意边界内填充任意多边形

Question

请问是否有人能够指出适用于我的多边形填充问题的最佳算法/启发式方法。给定一个单一的边界多边形（凸多边形或凹多边形，也可能包含孔），以及一个单一的“填充”多边形（也可能是凸多边形或凹多边形，不包含孔），我需要用指定数量的填充多边形填充边界多边形。（我正在处理2D问题）。

我找到的许多多边形填充启发式方法都假设边界和/或填充多边形是矩形的，并且填充多边形大小不同。在我的情况下，填充多边形可能是非矩形的，但所有填充多边形将完全相同。

也许这是一种特定类型的填充问题？如果有人对这种类型的多边形填充有定义，我会很乐意搜索，但到目前为止，我还没有找到任何与之相似并且有很大用处的东西。

谢谢。

- Craig

---

不，这看起来不像是装箱问题的某个著名特例。任何适用于不同形状的算法也应该轻松适用于相同形状。如果您有一个适用于矩形边界的算法，可以尝试将其调整为适用于任意边界。修改它，以便您可以在翻转操作之前使用一些不能移动或删除的形状（例如，只有一种放置方式）。解决矩形边界，预先填充一些仅留下原始边界未填充的形状。并非所有算法都可以像这样进行调整。 - n. m.

只有一种填充多边形的情况肯定是不同填充多边形的一般情况的特殊情况。我认为解决这种切割/包装问题的大多数启发式方法都使用非适配多边形，因此在谷歌搜索“非适配不规则包装”之类的东西可能是一个好的开始。 - Anders Forsgren

我认为你应该在 Stack Overflow 的理论计算机科学版本中询问这个问题。 - Ira Baxter

对于算法来说，这通常被称为"嵌套"，意思是将不规则、潜在非凸的二维/三维形状装入某个被切割的"原料"中。事物不一定要字面上进行嵌套，但也可以这样做。 - Christoph Rackwitz

Answer 1

你提出的问题非常困难。为了让这更容易理解，即使是在有界多边形内使用不重叠的圆盘填充的情况下，也已经很难了，而圆盘是最简单的“填充形状”（对于任何其他形状，您必须考虑方向以及大小和中心位置）。

事实上，我认为在计算几何学中，对于任意整数N和任意有界多边形区域（在欧几里得平面中），确定N个内切的不重叠圆盘的“最佳”（覆盖多边形内部百分比最大的意义上）排列方式是一个未解决的问题，您可以自由选择每个圆盘的半径和中心位置。我确信对于某些特殊的多边形形状（如矩形、圆形和三角形），已知最佳答案，但对于任意形状，您最好的“启发式”方法可能是：

1. 将您的形状计数器设置为N。
2. 添加最大的“填充形状”，使其完全适合多边形边界内部而不重叠任何其他填充形状。
3. 减少您的形状计数器。
4. 如果您的形状计数器> 0，请返回步骤2。

我说“可能”是因为“先放最大的”并不总是将物品装入有限空间的最佳方法。你可以通过阅读装箱问题和背包问题来了解这种特殊的疯狂方式。 编辑：仅进行第二步就很困难。一个合理的策略是选择多边形内部的任意点作为圆心，并“膨胀”圆盘，直到它触及边界或另一个圆盘（或两者皆有），然后在继续膨胀圆盘的同时“滑动”圆盘，使其保持在边界内而不与其他圆盘重叠，直到它被“困住”——至少与边界和/或其他圆盘有两个接触点。但是，这种“滑动过程”很难形式化。即使你掌握了滑动过程，这种策略也不能保证你会找到最大的“内切圆”——你的“局部极大”圆可能被困在内部的一个“叶片”中，该叶片通过一条狭窄的“颈部”自由空间连接到一个更大的“叶片”，更大的圆可以适合其中。

- Peter

Answer 2

感谢回复，我的要求是不需要考虑方向，只需关注填充元素的边界框，因此问题得以简化。结合空间哈希网格（因为有现有元素不能覆盖），我使用了类似条纹的填充算法。通过这种方法，我将填充区域划分为条纹，并创建了一个空间哈希网格来注册填充区域内的现有元素。我创建了第二个空间哈希网格来注册填充区域（因为我的条纹不保证在边界区域内，所以这样做可以更快地检查我的填充元素是否在填充区域内）。之后，我迭代每个条纹，并根据哈希网格的允许情况放置填充元素。虽然这并不是最优解，但对于我的特定情况来说已经足够，并且速度也很快。我从这里获得了有关创建空间哈希网格的所需信息，从这篇文章中得到了条纹填充的思路。

- Craig

---

很抱歉接受自己的答案，但其他答案都不够接近我实际解决问题的方法，所以我不能说它们会起作用。不过还是感谢大家的帮助。 - Craig

Answer 3

这种类型的问题在几何上解决起来非常复杂。

如果您可以接受一个好的解决方案而不是100%最优解，则可以使用光栅算法来解决它。

您将边界多边形绘制（光栅化）到一个内存图像中，将填充多边形绘制到另一个内存图像中。

然后，您可以更轻松地通过叠加两个图像并使用各种（X，Y）偏移量为填充多边形检查像素值，以搜索填充多边形适合边界多边形的位置。

当您找到填充多边形适合的位置时，清除边界多边形中的像素并重复此过程，直到没有更多的填充多边形适合的位置。

要搜索的关键字是：光栅化、叠加、算法。

- Simon C

Answer 4

如果您的填充多边形是拼图形状，许多算法将错过嵌套对齐。在这种情况下，我不知道该建议什么。

解决一般问题的一种方法是，当边界比填充块大得多时，在无限平面上以最佳方式铺设块，然后寻找边界在此平面上的最佳对齐方式。

- Jasen