Algorithm to take the union of rectangles and to see if the union is still a rectangle

Question

I have a problem in which I have to test whether the union of given set of rectangles forms a rectangle or not. I don't have much experience solving computational geometry problems. What my approach to the problem was that since I know the coordinates of all the rectangles, I can easily sort the points and then deduce the corner points of the largest rectangle possible. Then I could sweep a line and see if all the points on the line falls inside the rectangle. But, this approach is flawed and this would fail because the union may be in the form of a 'U'. I would be a great help if you could push me in the right direction.

Answer 1

Your own version does not take into account that the edges of the rectangles can be non-parallel to each other. Therefore, there might not be "largest rectangle possible".

I would try this general approach:

1) Find the convex hull. You can find convex hull calculation algorithms here http://en.wikipedia.org/wiki/Convex_hull_algorithms.

2) Check if the convex hull is a rectangle. You can do this by looping through all the points on convex hull and checking if they all form 180 or 90 degree angles. If they do not, union is not a rectangle.

3) Go through all points on the convex hull. For each point check if the middle point between ThisPoint and NextPoint lies on the edge of any initially given rectangle. If every middle point does, union is a rectangle. If it does not, union is not a rectangle.

Complexity would be O(n log h) for finding convex hull, O(h) for the second part and O(h*n) for third part, where h is number of points on the convex hull.

Edit: If the goal is to check if the resulting object is a filled rectangle, not only edges and corners rectangle then add step (4).

4) Find all line segments that are formed by intersecting or touching rectangles. Note - by definition all of these line segments are segments of edges of given rectangles. If a rectangle does not touch/intersect other rectangles, the line segments are it's edges.

For each line segment check if it's middle point is

• On the edge of the convex hull
• Inside one of given rectangles
• On the edge of two non-overlapping given rectangles.

If at least one of these is true for every line segment, resulting object is a filled rectangle.