用於在某個區域擬合2D多邊形的算法？

說：我有10個不同大小的多邊形。我有一個特定大小的區域。

我想知道如何填充該區域中最多邊形以及它們如何安裝。

注意：根據限制設置可以旋轉多邊形。

2009-12-01 Atlas

您可以通過http試試你的運氣來看待：//mathoverflow.net – Graviton 2009-12-01 08:18:26

多邊形可以旋轉嗎？ – 2009-12-01 10:06:06

一個可能的名字是Packing Problem。它與Knapsack Problem有關。這些問題往往是NP難題，許多需要啓發式。如果您可以限制允許的多邊形和區域形式，則可能存在針對您的特殊情況的更有效的算法。

2009-12-01 08:19:44

如果所有的多邊形都是矩形，並且它們所適合的區域也是一個矩形，那麼這將被稱爲bin-packing，Google會用這些信息壓倒你。如果他們不是，那麼我想你正在尋找一個bin-packing的變體，而且我想你還有更多的問題是你正在進入一個NP問題，其中「嘗試和測試」就是圍繞着最好的算法。

2009-12-01 08:24:28

你可以看看在維基百科「舞蹈鏈」爲高德納的解決精確覆蓋問題 - 包括平鋪 - 你的問題可以作爲鋪磚問題

2009-12-01 08:30:13

回答