我想知道是否有人可以指出适合我特定多边形打包问题的最佳算法/启发式算法。我得到一个多边形作为边界（凸面或凹面也可能包含孔）和一个“填充”多边形（也可能是凸面或凹面，不包含孔），我需要用指定的数字填充边界多边形填充多边形。（我在 2D 中工作）。
我发现的许多多边形打包启发式假设边界和/或填充多边形将是矩形，并且填充多边形将具有不同的大小。在我的情况下，填充多边形可能是非矩形的，但都将完全相同。
也许这是一种特殊类型的包装问题？如果有人对这种类型的多边形打包有一个定义，我会很乐意用谷歌搜索，但到目前为止，我还没有找到任何类似的东西非常有用。
谢谢。
你问的问题非常难。从这个角度来看，（更）简单的情况是，你用不重叠的圆盘填充有界多边形的内部已经很难了，而圆盘是最简单的“包装形状”（任何其他形状你必须考虑方向以及大小和中心位置）。
实际上，我认为确定任意整数 N 和任意有界多边形区域（在欧几里得平面中）是计算几何中的一个开放问题，什么是“最佳”（在覆盖多边形内部的最大百分比的意义上） ) N 个内接非重叠圆盘的包装，您可以自由选择每个圆盘的半径和中心位置。我确信“最佳”答案以某些特殊的多边形形状（如矩形、圆形和三角形）而闻名，但对于任意形状，您最好的“启发式”可能是：
我说“可能”是因为“最大优先”并不总是将物品装入密闭空间的最佳方式。您可以通过阅读有关垃圾箱包装问题和背包问题的信息来深入了解这种疯狂的特殊风味。
编辑：第 2 步本身很难。一个合理的策略是选择多边形内部的任意点作为中心并“膨胀”圆盘，直到它接触边界或另一个圆盘（或两者），然后在继续膨胀的同时“滑动”圆盘它使其保持在边界内而不与任何其他磁盘重叠，直到它被“困住”——至少有 2 个与边界和/或其他磁盘接触的点。但要正式化这种“滑动过程”并不容易。即使滑动过程正确，这种策略也不能保证你会找到最大的“可写圆盘”——你的“局部最大”圆盘可能会被困在内部的“叶”中，该“叶”由一个狭窄的“脖子”
感谢您的回复，我的要求是我能够通过不必处理方向来进一步简化问题，然后我什至通过只真正担心填充元素的边界框来进一步简化。通过这两种简化，问题变得容易多了，我使用了类似条纹的填充算法和空间散列网格（因为现有元素不允许我填充）。
通过这种方法，我简单地将填充区域划分为条带，并创建了一个空间散列网格来注册填充区域内的现有元素。我创建了第二个空间散列网格来注册填充区域（因为我的条纹不能保证在边界区域内，这使得检查我的填充元素是否在填充区域中更快一些，因为我可以查询网格，如果我的填充元素要放置的所有网格都已满，我知道填充元素在填充区域内）。之后，我遍历每个条带并在哈希网格允许的位置放置一个填充元素。这当然不是一个最佳解决方案，但它最终是我的特定情况所需要的，而且速度也很快。我从这里找到了有关创建空间哈希网格的所需信息. 我从这篇文章中得到了用条纹填充的想法。
这种类型的问题在几何上解决起来非常复杂。
如果您可以接受一个好的解决方案而不是 100% 的最佳解决方案，那么您可以使用栅格算法来解决它。
您将边界多边形绘制（栅格化）到一个内存图像中，并将填充多边形绘制（栅格化）到另一个内存图像中。
然后，您可以更轻松地搜索填充多边形适合边界多边形的位置，方法是使用填充多边形的各种（X，Y）偏移量覆盖两个图像并检查像素值。
当您找到填充多边形适合的位置时，您会清除边界多边形中的像素并重复，直到不再有填充多边形适合的位置。
google搜索的关键词有：光栅化、叠加、算法
如果您的填充多边形是拼图块的形状，许多算法将错过联锁对齐。（我不知道在这种情况下该建议什么）
当边界比填充块大得多时，解决一般问题的一种方法是用尽可能好的方式平铺一个无限平面，然后在这个平面上寻找边界的最佳对齐方式。