Given a bunch of rectangles, find an enclosing rectangle.

Given below are a bunch of rectangles whose dimensions are listed in (x, y, w, h) format. Where, x, y are coordinates of left top corner of the rectangle while w and h are width and height respectively. What is the algorithm to calculate the coordinates of the left-top corner and the width and height of an enclosing rectangle that encloses all the rectangles.

32, 375, 182, 65

150, 146, 60, 60

180, 212, 60, 60

632, 117, 60, 60

644, 210, 60, 60

304, 344, 60, 60

718, 374, 60, 60

442, 183, 60, 60

466, 299, 60, 60

492, 548, 60, 60

569, 548, 60, 60

333, 548, 60, 60

252, 548, 60, 60

414, 548, 60, 60

645, 548, 60, 60

-

Wouldn't left corner $\min(x), \min(y)$, right corner $\max(x+w),\max(y+h)$ work for both corners, and then width and height are simple subtraction of these?

-
Thankyou, yes it will, 20 years of math education and I couldn't solve this. It is a sad day ... – ShaggyInjun Jul 25 '13 at 21:45

Hint:

• When you have a bunch of intervals on the real line $[a_1,b_1],\ldots,[a_n,b_n]$, then the enclosing interval is $[\min_i a_i, \max_j b_j]$.
• When dealing with rectangles with sides parallel to axes, the $x$-coordinates and $y$-coordinates are rather independent, i.e. you can solve the problem for all the $x$-es and all the $y$-s separately.

I hope this helps $\ddot\smile$

-