多边形包装2D

Question

我有包装2任意多边形的问题。即我们有2个任意多边形。我们要找到这种多边形的放置（我们可以做旋转和移动），当矩形围绕这个多边形时，面积最小。

我知道，这是一个NP完全问题。我想选择一个有效的算法来解决这个问题。我在寻找No-Fit-Polygon方法。但是我找不到任何地方找到两个任意多边形的NFP的简单明了的算法。

Answer 1

如果它的NP完全，那么你需要启发式算法，而不是算法。我会尝试把每一对可能的双方放在一起，然后相互滑动，以尽量减少面积，如果它们是凹面的话，可能会有重叠。

Answer 2

参数空间似乎不太大，测试也不算太差。如果您修复一个多边形，另一个多边形可以沿X轴移动X，并沿Y轴移动Y并旋转r。

X和Y的感兴趣区域可以通过找到多边形的边界框来确定。 r当然是在360度之间。

那么你如何在X，Y和r的有趣范围内尝试一组等距的间隔。也许，一旦你发现了这些维度中的有趣点，你可以做更细粒度的搜索。