從中心開始用較小的矩形填充大矩形的算法

Question

我有各種大小的矩形，我試圖將它們放到從中心開始的較大的矩形中。下面你會發現一個我創建的動畫，用於直觀地描述需要發生的事情。

我一直在努力想出一種方法來模擬這種行爲。有沒有類似於這個的東西？我只需要指出正確的方向。

下面是一個非常粗略的解釋：

初始化

• 開始n矩形
• 訂購密度（他們是真正的3D立方體鳥瞰圖）
在中心10
• 將第一個矩形

剩餘矩形（適合多達我可以） 嘗試組密度最高的中心向外移動

Dimensions = { width: 400, height: 300 } 
Boundries = { 
    WEST = 0, 
    EAST = Dimensions.width, 
    NORTH = 0, 
    SOUTH = Dimensions.height 
} 

// each rectangle has width, height, and other information 
rectArr = Array of {width:60, height:40} 

root = { x:EAST/2, y:SOUTH/2 } 

foreach rect in rectArr { 
    // I will always traverse from the root and try to go left and right. If I cannot, I move up and try the same thing. I then move down. The problem is if there are 5 or more rows. I will be starting from the root and going up, then down, then up-up, then down. It's like I have two parallel trees. 

    // Try to branch left or right 
    if rect.width <= (Boundries.EAST - ('rightmost rectangle'.x + 'rightmost rectangle'.width/2)) branch-right 
    if rect.width <= (('leftmost rectangle'.x + 'leftmost rectangle'.width/2) - Boundries.WEST) branch-left 
    // Try to branch up or down 
    if rect.height <= ((root.x + root.height/2) - Boundries.NORTH) branch-up 
    if rect.height <= (Boundries.SOUTH - (root.x + root.height/2)) branch-down 
} 

Answer 1

編輯：開始得寫這個早。該解決方案僅適用於儘可能多的小矩形填充較大的矩形，假設小矩形的位置是靜態的。

聽起來像一個動態編程解決方案將在這裏最好的工作;如果你還沒有研究過算法，我會建議尋找貪婪算法的定義，動態規劃算法的定義，每種類型的例子，以及你使用哪一種而不是另一種。

此問題與加權調度問題非常相似，但在2維中。在加權調度，我們給出的時間間隔和一組子區間，並要求以確定該組子區間，其總結的權重是最大的，其範圍不重疊：

|--------------------------| 
|{--a--}-------------------| 
|----{------b-------}------| 
|--------{----c----}-------| 
|--------------------{-d-}-| 

如果我們擴大這個到兩個維度，較大的區間將是邊界矩形的x/y長度，子區間將是較小矩形的x/y長度，子區間的權重是較小矩形的區域。

在貪心算法中，我們試圖用盡可能多的最大子矩形填充邊界矩形，然後嘗試適應第二大，然後第三大等等，直到無你的長方形適合。問題在於，當使用最大的子矩形中的一個時，最終可能會填充較小的邊界矩形，而不是使用第二個最大的矩形中的四個（假設我們有一個邊長爲6的邊界正方形，最大的亞平方的邊長爲5，而第二大的亞平方的邊長爲3）。看起來您的初始解決方案可能會遇到同樣的問題。

動態規劃解決方案將較大的問題分解爲重疊的子問題，然後基於子問題的結果構建解決方案。在矩形的情況下，您想針對您的集合中的每個矩形問相同的問題：包含它的結果會更好，或者當我沒有將其包含在我的解決方案中時結果會更好。基於這個問題的答案，您可以將矩形添加到您的解決方案集中，並刪除與其重疊的所有其他矩形，或者只刪除該矩形並繼續。我提出以下幾點建議psudeo代碼：

compute_opt (set of rectangles){ 
    if(set.size == 0) 
    return 0 
    return max (area of selected rectangle i + 
       compute_opt(rectangles that don't overlap with i) , 
       compute_opt(rectangles without rectangle i included)) 
} 

我在記憶化有點生疏，所以我不會去到這裏。但請參閱this princeton lecture on dynamic programming瞭解有關加權調度的更多信息。根據間隔問題的具體情況，您應該能夠計算出矩形問題的具體情況。