Bounding box of multiple overlapping rectangles

Question

How can I get the bounding boxes of multiple overlapping rectangles? There might be multiple bounding boxes if there are rectangles that don't overlap.

I have an array containing n objects representing the rectangles. Each object is representing a rectangle the following way: {left: 178, top: 67, width: 20, height: 14} They can be represented other ways as well like leftX, topY, rightX, bottomY; it can be converted easily.

I'm not looking for non-max surpression algorithm. Is there a specific algorithm in literature that can achieve this? I'll try to convert it after in JavaScript.

Edit: AuxTaco solution works as long as the rectangles are overlapping one after the other; if you draw the rectangles in the order specified like in the picture below you get 3 bounding areas.

Edit2: Maybe an interesting case would be the following:

Rectangle 1 and 2 overlap and their bounding box overlaps rectangle 3; however I'm not interested in this particular case and 3 could be treated as a separate rectangle.

Answer 1

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

Answer 2

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.