javascript - 在没有重叠和 x 约束的边界内排列矩形

Question

我正在尝试排列未知数量的矩形，以使它们不会相互重叠。重新排列矩形时有许多限制：

• 只能沿正 y（向上）方向移动，但向上移动会将矩形推到容器边界之外的情况除外。
• 不能在 x（左或右）方向移动 我们应该在所有边的矩形之间获得一些合理的填充。
• 最上面的矩形应该是第一个矩形（由jsbin 链接中的标签表示）

我写了一个小东西，会在 jsbin产生主要问题。到目前为止，我唯一想到的是我来回遍历这些矩形的情况。我想知道是否有人可以提出一种方法或更好地指出现有的解决方案。

Answer 1

目前我唯一能想到的基本上就是分支定界搜索。从底部开始，通过向上推动一个或另一个矩形（分支）迭代地解决碰撞对。如果超出限制，则回溯到上一个分支。

如果解决这个问题是 NP-Complete，我不会感到惊讶。这是装箱问题的一个更受限制的版本。另一方面，过度约束问题往往会使它们变得非常容易，所以它可能不是 NP-Complete 的。我试图考虑减少几分钟，但没有提出任何建议。

Answer 2

您需要使用前面矩形的高度来计算每个矩形的垂直位置。检查问题是否有解决方案可能很有用。

// 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/FeepP/2/