在没有重叠和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约束的边界内安排矩形

回答

相关问题