algorithm - 多边形包装 2D

Question

我有打包 2 个任意多边形的问题。 IE。我们有 2 个任意多边形。我们要找到这个多边形的这种放置(我们可以进行旋转和移动)，当外接这个多边形的矩形具有最小面积时。

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

Answer 1

参数空间似乎不大，测试也不错。如果固定一个多边形，则另一个多边形可以沿 x 轴移动 X，沿 y 轴移动 Y 并旋转 r。

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

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