多邊形包裝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的有趣範圍內嘗試一組等距的間隔。也許，一旦你發現了這些維度中的有趣點，你可以做更細粒度的搜索。