算法佈局矩形窗口在2D顯示

Question

我在尋找一種算法來佈局矩形窗口，要求是象下面這樣：

1. 所有的窗戶是佈局可以看出 小矩形。
2. 所有窗口必須在矩形2D顯示中佈局，並給出顯示寬度和高度。
3. 有幾十個窗口需要佈局。每個窗口都有一個初始位置（x，y）和大小（寬度，高度）
4. 佈局算法將嘗試分離窗口以避免在窗口中重疊，以便用戶更容易看到所有窗口

5. 全局約束（max_x_offset，max_y_offset）給出了使每個窗口（一個new_x，new_y）的搬遷新位置滿足約束：

   abs(new_x - x) <= max_x_offset and abs(new_y - y) <= max_y_offset 
   

6. 全局約束是硬 約束，這意味着如果有 沒有這樣的佈局可以同時滿足4 和5，我們mu st滿足全局約束條件，並讓某個窗口 重疊。

7. 該算法可能無法得到最好的 可能的結果，但它應該快速運行 。我們將在實時使用此 算法渲染 應用

我搜索谷歌和維基百科和一些研究論文，但仍然未能找到這個任務的合適的算法。有什麼建議麼？謝謝！

更新：是的，我明白這是一個二維揹包問題，它是NP難。我想要的是一個快速的算法來獲得足夠好的結果。

Answer 1

您可以創建一個類似物理的模型，在這個模型中，窗口之間相互排斥，而力量取決於它們之間的距離。在每個時間步驟中，強制您的絕對位置約束。如果您在某個時間步驟內沒有找到無重疊解決方案，請中止算法並給出此時找到的候選解決方案。

當然，如果存在的話，這並不總能找到解決方案。但我認爲，總的來說，這是非常困難的，甚至是不可能的。