分离矩形Javascript

Question

基本上，我所做的是将一堆随机宽度/高度的矩形放置在网格上（靠近中心），然后把它们全部推开，直到它们不重叠。我有另一个版本，在将它们放置在网格上之前会检查碰撞，但这不是我在此版本中追求的目标。

我想知道是否有人可以解释一种更好的方法？

到目前为止，我尝试过类似于以下内容： let 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 */ )

加入随机数是为了避免某个矩形被反复推挤而无法解放，从而导致无限循环。然而，这种方法效率极低。

- Evan Ward

---

那么你的问题是什么？你是否正在寻找更有效的算法？你是否想知道为什么没有随机数会导致无限循环？目前还不清楚你在问什么。 - Ryan

是的，抱歉。不知道是否有人能够解释一种更好的方法来完成这个任务，或者引导我找到更好的解决方案。 - Evan Ward

简而言之，您需要将其最终呈现为“网格”，还是希望尽可能紧密地排列矩形？ - slebetman

后者紧密地排列它们，但不需要填充矩形之间的所有空间。 - Evan Ward

如果你想要最小化边界矩形，那么你的问题实际上是这个。或者你想要最小化的是边界圆？ - Andy Jones

您有重叠的矩形，并且通过您发布的代码，您正在检查和解决成对的任何矩形不相交。快速问题：网格与此有什么关系？您没有在任何地方使用网格的尺寸。 - Aditya

Answer 1

我相信你想要实现的是所谓的装箱问题http://en.wikipedia.org/wiki/Packing_problem。如果你在Stack Overflow上搜索“2D装箱”，你应该能够找到所有需要的内容，以便编写一个更高效的算法。

- Ethan Lynn