佈置避免碰撞的矩形（算法幫助）

Question

我有一個（大）水平滾動視圖，以及一堆我想定位的矩形。每個矩形都有一個所需的水平位置，但如果需要，它可以從該位置變化達一定量（常數K）。矩形不能重疊。矩形的垂直位置是任意的（當然，限制在視圖的高度）。

理想情況下，我希望矩形的大小是可變的......我想如果這是不可能的，我可以使尺寸在一個維度上變化。

現在，在這個佈局中將不可能：由於只有一定量的垂直空間，並且它們只能將K個像素水平移動離開它們的理想，可能並不是所有的矩形都能被繪製。爲了解決這個問題，每個矩形都有一個優先級（P），優先級較低的矩形應該先被省略。 （你可以認爲這是非模糊的，你可以隨時分辨出哪個矩形具有更高的優先級。）

我在概念算法的東西之後，但是如果你需要細節，這將會運行在iPad上，將會有幾千（> 1000但是< 10,000）長方形考慮。理想情況下，我希望每次用戶更改縮放級別時都能夠快速重新運行，但如果這不容易，則可以緩存位置。這些物體是時間線上的照片，我希望在事件發生時讓它們大約接近 - 我要去近似以便在那裏獲得更多。

我見過像this這樣的算法，可以做非相交的技巧，但是對於每個項目只允許移動一定的數量並不存在相同的想法。很顯然，如果沒有後一種約束，您可以顯示所有項目，所以我還需要知道什麼時候沒有更多矩形可以顯示的方式。

如果解決所描述的問題太困難了，我很樂意提出一個更實用的想法。如果一切都失敗了，我總是可以按照優先順序進行一些操作，如果可以，則將每個項目放在所需位置，如果不是，則嘗試垂直移動它，如果仍然不是，則將其水平移動到允許的限制，然後再繼續下一個。優先順序意味着可能找到次優解決方案，但它將被加權到最重要的項目上。

Answer 1

這是我認爲可以完成的一種方法。

第1步是找出所有可以放置新黃色矩形的位置。不失一般性，我們可以將其存儲爲矩形左上角所有可能的X-Y位置的列表。當然，對於這樣一個巨大的起始區域，該列表將包含數百萬條目，爲了節省空間，我們以一組矩形區域的形式存儲該列表。例如，如果我們的屏幕的像素從X = 0到X = 2999（含），並且從Y = 0到Y = 999（含），並且我們的新矩形的寬度爲300像素，高度爲150像素，則左上角（X，Y）=（0,0）至（2699，849）（含）的任何位置。我們將其存儲爲四元組[0，0，2699，849]。

現在，當我們將每個現有（紅色）矩形放到屏幕上時，這些可能性中的一些會被排除，因爲它們會導致新的（黃色）矩形與它們重疊。例如，如果有一個紅色矩形[1100,200,1199,299]，那麼我們的黃色矩形在（X，Y）=（801,51）到（1199,299）的任何位置都不能有其左上角。包括的。

因此，用四個矩形區域代替[0,0,2699,849]，這四個矩形區域覆蓋相同區域但留下間隙。有很多方法可以做到這一點，但這裏是一個：[0,0,1199,50]，[1200,0,299,2699]，[0,51,800,849]，[801,300,2699,849 ]。

繼續添加更多的紅色矩形到屏幕上。每次添加時，從列表中減去更多的可能性（這通常會導致包含更多，更小的「安全區域」的列表）。 （如果您的屏幕上有1000多個長方形的全屏幕，這可能會非常耗時;如果您只從您提到的[XK，0，X + K，H]空間開始，那麼1000的相對較少+會重疊，計算速度會快得多）。這段代碼應該非常小心，並且需要一堆單元測試，因爲fencepost錯誤會比比皆是。

最終結果是屏幕上的可能位置的完整列表，其中可以放置新黃色矩形的左上角，以矩形區域列表的形式表示。

第2步：查看此列表並選擇最理想的位置。任何實際與理想垂直線相交的矩形區域都將優先。但有可能沒有。在這種情況下，您可以從落在左側的區域和落在理想線路右側的區域中選擇最優選的選項。作爲提示：每個區域只需要考慮一個角落的一個角落（右側區域的左上角，左側區域的右上角）。