0
\$\begingroup\$

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: Two rectangles With one bounding rectangle

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ This is a simple issue, and a simple solution like this is ideal. No need to implement any unnecessary complexity. Finding the min/max extents of both axis is all that you need. \$\endgroup\$ – Evan Jun 18 '14 at 13:46
  • \$\begingroup\$ +1, simple answer concentrating on the central point of the question, the math. I would add that it could be easier to store rects as min max completely. \$\endgroup\$ – Kronos Jun 18 '14 at 13:48
  • \$\begingroup\$ I agree, storing min max for rectangles tends to be more efficient in most situations, though it is of course context sensitive. \$\endgroup\$ – Evan Jun 18 '14 at 13:53
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.