JavaScript Merge Intersecting Rectangles

7
votes

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.

3
javascriptalgorithmmergeintersection
This is not at all clear. You're passing it the same rectangle. What happens if you pass two different rectangles that intersect? e.g. {x:0, y:0, w:2, h:2}, {x:1, y:1, w:2, h:2} Do you want the smallest enclosing rectangle, the largest rectangle contained in the intersection, the first rectangle, the second rectangle? – aaronasterling
in this example, both objects are identical, hence there is actually no need to merge anything. What is your requirement? Should object b overwrite attributes in object a? vice versa? Or should it be more a binary AND, OR, XOR ? – jAndy
I'm an idiot. Updated. It should merge it by creating a minimum bounding rectangle. – Louis
Ok, much better but still some problems. You're taking the smallest enclosing rectangle. Doing this sequentially could create intersections where there were none before. What do you want to happen then? Something like {x:0, y:0, w:10, h:10}, {x:9, y:9, w: 11, h:11}, {x:11, y:0, h:2, w:20}. Should the last one be regarded as intersecting the first two? It doesn't to begin with but after you merge them into the enclosing rectangle, it intersects that. – aaronasterling
Ok will clear that up. It will need to parse the list again to see if there are any new intersections created and therefore merge those. – Louis

3 Answers

7
votes

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

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.

0
votes

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