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 导致与其他矩形相交。对于我的一生，我无法弄清楚。

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)
          }
}

Answer 2

这可以通过将问题建模为图表来解决。节点是矩形，每当其中任何两个节点之间存在交集时，我们就认为这两个节点通过边连接。

我们的目标是将矩形集分成直接或间接相互连接的组。这基本上是图的连接组件。这可以使用 广度优先搜索 或 深度优先搜索。

找到所有组件后，我们只需找到每个组件中所有矩形的最高左上角和最低右下角即可找到它们的边界框。

可以使用@Marcus' 答案中提供的函数来检查交集。

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

Answer 3

如果有人需要完整的工作示例，这里是 repl 来玩 https://repl.it/@anjmao/合并矩形 和代码：

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}])