JavaScript Merge Intersecting Rectangles

Question

I need a way to merge an array of rectangle objects (objects with x,y,w,h properties) only if they intersect. So for example:

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

would return: [{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}])

would return: [{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}])

would return: [{x:0, y:0, w:6, h:6}, {x:15, y:15, w:1, h:1}]

---

If two rectangles intersect, a minimum bounding rectangle should be replace the two rectangles. The list will need to be checked again after merging in case the new MBR causes intersection with other rectangles. For the life of me I can't figure it out.

Answer 1

In case somebody needs fully working example here is repl to play https://repl.it/@anjmao/merge-rectangles and code:

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

Answer 2

This can be solved by modelling the problem as a graph. The nodes are the rectangles, and whenever there is an intersection between any two of them, we consider that those two nodes are connected by an edge.

Our target is to divide the set of rectangles into groups that are connected, either directly or indirectly, with each other. This is basically a connected component of the graph. This can be found out using a breadth first search or a depth first search.

After all components are found, we just need to find the highest top left corner and the lowest bottom right corner of all the rectangles in each to find their bounding box.

Checking for intersection can be done using the function provided in @Marcus' answer.

The overall complexity of this procedure is O(n^2), where n is the number of rectangles.

Answer 3

I'm not sure if this will work but off the top of my head something like...

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