您好，我有左邊這個爛攤子爛攤子，它幾乎與一些孔矩形陣列（標記爲紅色）。我正在尋找一種方法來將它們結合起來，以儘可能少的矩形結束，並且最好讓它們中的大部分儘可能接近正方形。看看右邊的圖像，這就是我想要完成的事情，只是稍微漂亮些，最好是自動化一點。
我需要這個遊戲，它不會在運行時完成，所以速度並不是真正的問題（除非它非常慢，因爲我必須在相當大的範圍內完成），但我從來沒有之前必須做這樣的事情，我真的不知道從哪裏開始。
我已經試過bruteforcing我的方式通過數組，從左上方的正方形和種類的合併開始，直到沒有任何合併剩餘，但它確實沒有那麼高效，因爲它不能考慮合併矩形3x2,4x3等。
如果你能指出我的任何算法，可以處理這種事情或有一個這樣可以完成的想法，將不勝感激。謝謝！
你可以試試貪心算法。當然，它不會是最優的（好吧，你沒有嚴格定義最優性標準）。但也許它會滿足您的需求。
所以，你可以嘗試：
如果你也關心導致矩形接近方可以儘量讓像a * totalArea + (1 - a) * (min_resulting_side/max_resulting_side)用合適的值f或0 < a < 1.
盲目合併2個矩形的問題在於，這個模塊可能會出現：http://i.imgur.com/4O1H1a6.png 如果偶然合併藍色的那個，那麼可以防止形成巨大的白色星團，這顯然會導致最終列表中的矩形更少，這是一個巨大的優先權 – Otopkin
@Otopkin在我的算法中，每一步都必須合併使**最大區域**的一對矩形。有了這個，你也可以找到一個不是最優的例子。我只是希望爲你的真實生活應用程序，這將是足夠好的。 – algrid
我可能會沿着這些路線做些事情，應該給出足夠好的基線，以便以後可以手動進行微調。我研究了幾種多邊形縮減算法，它們用於3D模型等，最壞的情況下，我可以將其轉換爲網格，在Blender中打開它並使用它們的rofl。 – Otopkin
我有一段時間後有點類似的問題：https：//stackoverflow.com/questions/11002205/find-all-rectangular-areas-with-certain-properties-in-a-矩陣然而，在我的情況下，產生的矩形可能會重疊。也許你可以調整它，找到所有重疊的最大尺寸的矩形，然後對於由多個矩形覆蓋的每個區域，將其恰好添加到那些矩形中的一個。 – HugoRune
只是所以我完全理解，是通過在一個大的矩形中繪製垂直/水平線，然後將一些隨機創建的矩形選爲「紅色」矩形創建的矩形？ –
不，我從一張只有紅色長方形的紙張開始，然後將整張紙片切成四周。 – Otopkin