高效的矩形擬合算法

作爲一個輸入，我有一個「地圖」，這是一個多邊形。它的所有邊都與x軸或y軸平行（所有這些多邊形都由它們組成的矩形描述，所有多邊形的大小都是整數）。在這裏你可以看到一個正確和不良輸入的例子。高效的矩形擬合算法

第二輸入是一組矩形欲適合的。所有的矩形被通過他們的尺寸描述寬×高（每矩形可以有不同的整數大小）。

對於給定的輸入，我想知道是否可以將所有矩形放到地圖上。如果是這樣，我想獲得所有矩形的位置。而且，我可以在矩形的位置上有更多的條件。例如，我知道地圖中的兩個矩形A，B必須由一邊連接。

有沒有任何有效的算法來解決這個問題？我會說它可以轉化爲一些圖形問題，但我不知道如何表示它。謝謝你的幫助！

2017-06-27 P.N.

你允許翻轉或旋轉矩形嗎？此外，是僅由寬度*高度描述的矩形？如果是這樣，我們不能確定一個矩形。還是分別提供寬度和高度？ –

您可以將其轉換爲圖形問題，其中每個節點在添加一些矩形（一個包含已佔用的插槽的貼圖）以及已用矩形和空閒矩形的列表之後爲狀態。例如，您可以在該圖中運行DFS，在這種情況下，您應該將已達到並計算的狀態保存在內存中，以避免多次執行這些狀態。然而，由於該圖具有太多狀態和節點（高達'2^n_slots + 2^n_rectangles'狀態），所以這將是非常長的。 – gdelab

通過查找只能放在一個地方的矩形或查找只能由特定矩形填充的地方，可以減少可能性的數量。 – fafl

幾乎肯定沒有總是有效的算法，因爲這個問題是NP-hard。看到這一點，請注意您可以將NP難Partition Problem的任何實例減少你的問題的一個實例：

對於分區中的問題每個號碼X_I，創建一個1 * X_I矩形。
設置「第一個輸入矩形」大小爲2乘（0.5 * s），其中s是所有x_i的總和。

上述的問題的實例有一個解決方案，當且僅當原來的劃分問題實例有一個解決方案，因此，如果有解決你的問題的有效途徑，那麼你可以使用相同的算法來高效解決分區問題（並通過類似的減少，每隔一個NP難題）。

來源

2017-06-27 18:59:36

高效的矩形擬合算法

回答

相關問題