在任意边界内打包任意多边形

Question

我想知道是否有人能指出我最适合我特定多边形包装问题的算法/启发式算法.我给了一个多边形作为边界(凸面或凹面也可能包含孔)和一个"填充"多边形(也可能是凸面或凹面,不包含孔)我需要用指定的数字填充边界多边形填充多边形.(我在2D工作).

我发现的许多多边形填充启发式假设边界和/或填充多边形将是矩形的,并且填充多边形将具有不同的大小.在我的例子中,填充多边形可能是非矩形的,但都是完全相同的.

也许这是一种特殊类型的包装问题？如果有人对这种类型的多边形包装有一个定义,我很乐意google,但到目前为止,我还没有发现任何类似的东西都很有用.

谢谢.

Answer 1

感谢您的回复，我的要求是这样我能够通过不必处理方向来进一步简化问题，然后我只需真正担心填充元素的边界框即可进一步简化。通过这两种简化，问题变得更加容易，我使用了类似条带的填充算法与空间哈希网格结合使用（因为存在不允许我填充的现有元素）。

通过这种方法，我简单地将填充区域划分为条带，并创建一个空间哈希网格来注册填充区域内的现有元素。我创建了第二个空间哈希网格来注册填充区域（因为我的条纹不能保证在边界区域内，这使得检查我的填充元素是否在填充区域中更快一些，因为我可以查询网格，如果我要放置填充元素的所有网格都已满，我知道填充元素位于填充区域内）。之后，我迭代每个条带并在哈希网格允许的位置放置一个填充元素。这当然不是最佳解决方案，但它最终满足了我的特定情况所需的全部要求，而且速度也相当快。我从这里找到了有关创建空间哈希网格所需的信息。我从这篇文章中得到了用条纹填充的想法。