在沒有重疊和x約束的邊界內安排矩形

我想安排未知數量的矩形，以便它們不會相互重疊。有許多約束的重新排列的矩形時：在沒有重疊和x約束的邊界內安排矩形

可以在正y只能移動（向上），不同之處方向的條件，其中向上移動將推動容器邊界之外的矩形。
不能在x（左或右）方向上移動我們應該在所有邊上的矩形之間得到一些合理的填充。
最上面的矩形應該是第一個矩形（由標籤在jsbin link表示）

我寫了一個小東西，將產生的主要問題here at jsbin。到目前爲止，唯一出現在我腦海中的是一個我通過這些矩形來回訪問的情況。我想知道是否有人可以提出一種方法或更好的方法，但指出現有的解決方案。

2013-05-11 Mohamed Shakir

你考慮過[treemap layout]（https://github.com/mbostock/d3/wiki/Treemap-Layout）嗎？通過正確設置尺寸，您應該能夠得到相當接近的東西。 – 2013-05-11 11:50:41

您需要使用前面矩形的高度來計算每個矩形的垂直位置。檢查問題是否有解決方案可能很有用。

// Generate random rectangles, with the vertical position set to zero 
var padding = 5; 
var num_rectangles = 10; 
var rectangles = []; 
for (var k = 0; k < num_rectangles; k += 1) { 
    rectangles.push({ 
     x: 50 * Math.random(), 
     y: padding, 
     width: Math.max(50 * Math.random(), 20), 
     height: Math.max(50 * Math.random(), 20) 
    }); 
} 

// Update the vertical position of the item j as the sum of the heigths 
// of the rectangles 0, ..., j - 1 
for (var j = 1; j < num_rectangles; j += 1) { 
    rectangles[j].y = rectangles[j - 1].y + rectangles[j - 1].height + padding; 
}

然後就像往常一樣畫矩形。我寫了一個小例子http://jsfiddle.net/FuepP/2/

來源

2013-05-11 17:51:30

我現在唯一能想到的基本上是分支和綁定搜索。從底部開始，通過按下一個或另一個矩形（分支）迭代地解決碰撞對。如果你超出限制，回溯到前一個分支。

如果解決這個問題是NP-Complete，我不會感到驚訝。這是bin packing problem更受限制的版本。另一方面，過度約束問題往往會使它們變得非常容易，所以也許它不是NP-Complete。我試着想了幾分鐘減少，但沒有提出任何事情。

來源

2013-05-12 01:50:01

在沒有重疊和x約束的邊界內安排矩形

回答

相關問題