Geek Answers Handbook

JavaScript Merging Intersecting Rectangles

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

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

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

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

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

If two rectangles intersect, the minimum bounding rectangle should replace the two rectangles. The list should be checked again after merging if the new MBR causes intersection with other rectangles. For life, I can’t understand.

+6
javascript algorithm merge intersection
source share
3 answers

I'm not sure if this will work, but from 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) } }
+7
source share

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

Our goal is to divide the set of rectangles into groups that are directly or indirectly related to each other. This is basically a related graph component . This can be learned using the width of the first search or the depth of the first search .

After all the components are found, we just need to find the upper left upper corner and the lower right right corner of all the rectangles in each to find their bounding rectangle.

An intersection check can be performed using the function provided in @Marcus's answer.

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

+2
source share

In case someone needs a full-fledged working example, here you can reproduce https://repl.it/@anjmao/merge-rectangles and the 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}])
0
source share

More articles:


All Articles