algorithm - 多边形包装 2D

Question

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

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

Answer 1

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

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

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

Answer 2

如果它是 NP 完全的，那么你需要启发式算法，而不是算法。我会尝试将每对可能的边放在一起，然后将一个边滑动到另一边以最小化面积，如果它们当然是凹的，则受到可能重叠的限制。