How to find the total bounds rectangle around a list of rectangles

Question

How can I find the total bounds rectangle around a list of rectangles?

Rectangle object: a simple data structure of 4 floats (w,h,x,y). I have an array of 2 or more rectangles and want to create a rectangle that surrounds all of them:

The result rectangle, calculated from rectangles A and B: Rectangle T : ( Ht, Wt, Xt , Yt)

Answer 1

First, for every rectangle convert the values for x, y, width and height into xMin, yMin, xMax and yMax like so:

xMin = x
yMin = y
xMax = x + width
yMax = y + height

Then the xMin value of your surrounding rectangle is the minimum of all those xMin values. Similarly the xMax value of your surrounding rectangle is the maximum of all those xMax values. Same for yMin and yMax.

Now you can convert these values back like so:

x = xMin
y = yMin
width = xMax - xMin
height = yMax - yMin

This will be your surrounding rectangle.

Answer 2

When the mass of the list is first created, loop through them all and find the relevant values. Store these max values somewhere, and every time a new rectangle is added to the list, check if it any of it's components is larger/smaller than the stored rectangle. If so, replace it. When removing you might have to run through the entire list again and check the new bounds. However, you only have to do that when you remove a rectangle, which shouldn't be too often I'd assume.

This is the way I'd probably do it at first. If it's too slow for your needs, you might have to look into more complex data structures.

Answer 3

Create a new class, say RectangleCollection, that holds :
- a list of rectangles ( or BBox -bounding box-).
- a bounding rectangle such as any rect of the list is within this rect.

On creation of such an object, both the list and the bounding rect are empty.
When inserting the first rectangle, the bounding rect will be this only rect.
When inserting other rects, the bounding rect will be extended on its left/right/top/bottom if need be to still contain the new one.
When removing a rect, if the removed rect is fully within the bounding rect, nothing to do. if the removed rect is on an edge of the bouding rect, you have to compute again the bounding rect by computing min/max/min/max of x/x/y/y to get left/right/top/bottom, then compute left/top/width/height of the bounding rect.