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