javascript - 分离矩形 Javascript

Question

本质上，我所做的是将一堆随机宽度/高度的矩形放置到一个网格上(靠近网格的中心)，然后将它们相互推开，直到它们都不重叠。我有另一个版本，我在将它们放置在网格上之前检查碰撞，但这不是我在此版本中的目的。

我想知道是否有人可以解释一个更好的方法来解决这个问题？

到目前为止我尝试过的是类似于:

让 r1/r2 = rect1/rect2

do {
    var ox = Math.max(0, Math.min(r1.x + r1.w, r2.x + r2.w) - Math.max(r1.x, r2.x)),
        oy = Math.max(0, Math.min(r1.y + r1.h, r2.y + r2.h) - Math.max(r1.y, r2.y)),
        dx = r2.x - r1.x,
        dy = r2.y - r1.y;
    if (ox > 0 && oy > 0) {
        if (ox >= oy) {
            if (r1.x >= r2.x && Math.random() > .1) {
                r1.x += ox;
                spaced = true;
                continue;
            } else {
                r1.x -= ox;
                spaced = true;
                continue;
            }
        } else {
            if (r1.y >= r2.y && Math.random() > .1) {
                r1.y += oy;
                spaced = true;
                continue;
            } else {
                r1.y -= oy;
                spaced = true;
                continue;
            }
        }
    }
} while ( /* stuff */ )

随机只是在那里，因为我会遇到某个 rect 被来回插入并且永远不会自由并导致无限循环的时候。然而，这种方式非常低效。

Answer 1

我相信您试图完成的是包装问题 http://en.wikipedia.org/wiki/Packing_problem .如果您只是在堆栈溢出中搜索“2d bin packing”，您应该能够找到滚动更高效算法所需的一切。