3

本质上，我正在做的是将一堆随机宽度/高度矩形放在网格上（靠近它的中心），然后将它们全部推开，直到它们都不重叠。我有另一个版本，我在将它们放在网格上之前检查碰撞，但这不是我在这个版本中想要的。

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

到目前为止，我尝试过的类似于：

让 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 */ )

随机只是因为我会遇到某个矩形被来回推动并且永远不会自由并导致无限循环的时候。然而，这种方式效率极低。

4

1 回答 1

0

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

于 2014-01-18T04:14:38.367 回答