JavaScript合并重叠矩形

Question

我需要一种方法来合并一个矩形对象数组（具有 x，y，w，h 属性的对象），仅当它们相交时才合并。例如： merge（[{x:0，y:0，w:5，h:5}，{x:1，y:1，w:5，h:5}]） 将返回：[{x:0，y:0，w:6，h:6}]

---

merge（[{x:0，y:0，w:1，h:1}，{x:5，y:5，w:1，h:1}]） 将返回：[{x:0，y:0，w:1，h:1}， {x:5，y:5，w:1，h:1}]

---

merge（[{x:0，y:0，w:5，h:5}，{x:1，y:1，w:5，h:5}，{x:15，y:15，w:1，h:1}]） 将返回：[{x:0，y:0，w:6，h:6}，{x:15，y:15，w:1，h:1}]

---

如果两个矩形相交，则应替换为最小外接矩形。在合并后，需要再次检查列表以防新的 MBR 与其他矩形相交。我想不出来怎么做。

- Louis

---

这不太清楚。你正在传递相同的矩形。如果您传递两个不同的相交矩形会发生什么？例如：{x:0, y:0, w:2, h:2}, {x:1, y:1, w:2, h:2} 您想要最小的包围矩形，最大的被包含在交集中的矩形，第一个矩形，还是第二个矩形？ - aaronasterling

在这个例子中，两个对象是相同的，因此实际上没有必要合并任何内容。你的需求是什么？对象 b 应该覆盖对象 a 中的属性吗？反之亦然？还是应该更多地采用二进制的 AND，OR，XOR ？ - jAndy

我是个白痴。已更新。它应该通过创建一个最小边界矩形来合并它。 - Louis

好的，进步很大但仍然存在一些问题。您正在获取最小的包围矩形。这样做可能会顺序地创建交叉点，而之前没有交叉点。那么您想发生什么？例如{x:0, y:0, w:10, h:10}, {x:9, y:9, w: 11, h:11}, {x:11, y:0, h:2, w:20}。最后一个是否应被视为与前两个相交？起初它并没有相交，但是在将它们合并到包围矩形中后，它会与其相交。 - aaronasterling

好的，我会澄清一下。它需要再次解析列表，以查看是否创建了任何新的交集，因此合并它们。 - Louis

Answer 1

我不确定这是否有效，但凭借我的经验，大概是这样的…

function mergeAll(array) {
  do {
     var newArr = [], didMerge = false, i = 0;

     while (i < array.length) {
        if (intersects(array[i], array[i+1]) {
          newArr.push(merge(array[i], array[i+1]));
          i++;
          didMerge = true;
        }
        i++;
     }
     array = newArr;
  } while (didMerge);
  return array;
}

function intersects(r1, r2) {
    return !( r2.x > r1.x+r1.w
           || r2.x+r2.w < r1.x
           || r2.y > r1.y+r1.h
           || r2.y+r2.h < r1.y
           );
}

function merge(r1, r2) {
   return { x: Math.min(r1.x, r2.x),
            y: Math.min(r1.y, r2.y),
            w: Math.max(r1.w, r2.w),
            h: Math.max(r1.h, r2.h)
          }
}

- Marcus Frödin

---

调整了一些，但是成功了！稍后会发布最终代码。干杯！ - Louis

最后一部分有问题吗？我认为r1.w/h和r2.w/h的最大值不会起作用。 - barney765

Answer 2

这可以通过将问题建模为图来解决。节点是矩形，每当两个矩形相交时，我们认为这两个节点被一条边连接。

我们的目标是将矩形集合分成彼此直接或间接连通的组。这基本上是图的连通分量。可以使用广度优先搜索或深度优先搜索来找到它们。

在找到所有分量后，我们只需要找到每个分量中所有矩形的最高左上角和最低右下角，以找到它们的包围盒。

使用@Marcus答案中提供的函数可以检查相交情况。

此过程的总复杂度为O(n^2)，其中n是矩形的数量。

- MAK

Answer 3

如果有人需要完全可用的示例，这里是可以玩的repl https://repl.it/@anjmao/merge-rectangles 和代码：

function mergeAll(array) {
    let newArr, didMerge, i;
    do {
        newArr = [];
        didMerge = false;
        i = 0;
        while (i < array.length) {
            const curr = array[i];
            const next = array[i + 1];
            if (intersects(curr, next)) {
                newArr.push(merge(curr, next));
                i++;
                didMerge = true;
            } else {
                newArr.push(curr);
            }
            i++;
        }
        if (newArr.length > 0) {
          array = newArr; 
        }
    } while (didMerge);
    return array;
}

function sort(array) {
    array.sort((r1, r2) => {
        if (r1.x === r2.x) {
            return r1.y - r2.y;
        }
        return r1.x - r2.x;
    });
}

function intersects(r1, r2) {
    if (!r2) {
        return false;
    }
    return !(r2.x > r1.x + r1.w
        || r2.x + r2.w < r1.x
        || r2.y > r1.y + r1.h
        || r2.y + r2.h < r1.y
    );
}

function merge(r1, r2) {
    const w = r1.w > r2.w ? r1.w : r2.w + (r2.x - r1.x);
    const h = r1.h > r2.h ? r1.h : r2.h + (r2.y - r1.y);
    return {
        x: Math.min(r1.x, r2.x),
        y: Math.min(r1.y, r2.y),
        w: w,
        h: h
    }
}

mergeAll([{x:0, y:0, w:5, h:5}, {x:1, y:1, w:5, h:5}, {x:15, y:15, w:1, h:1}])

- Andzej Maciusovic

---

多余的排序？ - jedierikb