Bounding box of multiple overlapping rectangles
So I have laid out a approach, which should work for you. The summary of approach is below
- Start with a empty collision array
- Each element in collision array will store array of rectangles which collide with any of the rectangles
- Run through list of rectangles we have
- If rectangle doesn't collide with any element append it to collision
- If rectangle collides with exactly one element then append it to that element of collision array
- If rectangle collides with multiple elements in array then we merge all such elements into one and then remove rest of the elements
- Finally the collision array has only elements which are collision arrays
- Then you can compute bounding rectangle for each of these collisions, which is just a min/max problem
Now to the code
function doRectsCollide(a, b) {
return !(
((a.top + a.height) < (b.top)) ||
(a.top > (b.top + b.height)) ||
((a.left + a.width) < b.left) ||
(a.left > (b.left + b.width))
);
}
var collisions = [];
var rectangles = [
{left: 74, top: 66.89999389648438, width: 80.5, height: 71},
{left: 111.5, top: 95.89999389648438, width: 125, height: 84},
{left: 177, top: 120.89999389648438, width: 168.5, height: 90},
{left: 93, top: 258.8999938964844, width: 81.5, height: 81},
{left: 265.5, top: 320.8999938964844, width: 92, height: 83},
{left: 393, top: 210.89999389648438, width: 88.5, height: 95}
];
for (rectangle of rectangles) {
var collisions_indexes = [];
index = 0;
for (currentColission of collisions) {
for (rect of currentColission) {
if (doRectsCollide(rect, rectangle) === true) {
collisions_indexes.push(index)
break
}
}
index++;
}
if (collisions_indexes.length == 0) {
// this rectangle collides with none and should be appened to collisions array
collisions.push([rectangle])
} else if (collisions_indexes.length >= 1) {
// there is just one collision, we can merge the same
collisions[collisions_indexes[0]].push(rectangle)
// now we have got multiple collisions, so we need to merge all the collisions with the first one
// and remove the colission ones
for (var i = 1; i < collisions_indexes.length; i++) {
// we use - (i - 1) because we will remove the collision once we merge it
// so after each merge the collision index actually shift by -1
var new_index = collisions_indexes[i] - (i - 1);
// extend the first colliding array with the new collision match
collisions[collisions_indexes[0]].push(...collisions[new_index])
// now we remove the element from our collision since it is merged with some other
collisions.splice(new_index, 1);
}
}
}
console.log(JSON.stringify(collisions, null, 2));
//now we have a array of collision which will have all colliding ones
for (collision of collisions) {
// compute bounding rectangle from rectangles array in collision
}
Now the output of the same is
[
[
{"left":74,"top":66.89999389648438,"width":80.5,"height":71},
{"left":111.5,"top":95.89999389648438,"width":125,"height":84},
{"left":177,"top":120.89999389648438,"width":168.5,"height":90}
],
[{"left":93,"top":258.8999938964844,"width":81.5,"height":81}],
[{"left":265.5,"top":320.8999938964844,"width":92,"height":83}],
[{"left":393,"top":210.89999389648438,"width":88.5,"height":95}]
]
I don't know the name of a specific algorithm, but this can be reduced to 2D collision detection:
function combineRects (rect1, rect2) {
return a rectangle object representing the bounding box of the union of rect1 and rect2;
}
function doRectsCollide (rect1, rect2) {
return true if rect1 and rect2 intersect;
}
const rectangles = [ your rectangle objects ];
const boundingBoxes = rectangles.reduce((boxes, rect) => {
// Start with an empty array of bounding boxes.
// For each rectangle, find the bounding box it intersects.
const boundingBoxIndex = boxes.findIndex(doRectsCollide.bind(null, rect));
if (boundingBoxIndex === -1) {
// If there is none, push the rectangle into the bounding box array.
boxes.push(rect);
return boxes;
} else {
// Otherwise,
// replace the intersected bounding box with a new box that includes the rectangle.
boxes[boundingBoxIndex] = combineRects(boxes[boundingBoxIndex], rect);
return boxes;
}
}, []);
This is pretty efficient in your example (each rectangle is compared to a maximum of 3 others), but slows down to O(n^2) in the worst case, no overlapping rectangles. It can be improved by using something better than a raw array to store the bounding boxes.