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.

Answer 2

You could deduce the he corner points of the largest rectangle possible, and then go over all the rectangle that share the border with the largest possible rectangle, for example the bottom, and make sure that the line is entirely contained in their borders. This will also fail if an empty space in the middle of the rectangle is a problem, however. I think the complexity will be O(n2).

Answer 3

I think you are on the right direction. After you get the coordinates of largest possible rectangle,

If the largest possible rectangle is a valid rectangle, then each side of it must be union of sides of original rectangles. You can scan the original rectangle set, find those rectangles that is a part of the largest side we are looking for (this can be done in O(n) by checking if X==largestRectangle.Top.X if you are looking at top side, etc.), lets call them S.

For each side s in S we can create an interval [from,to]. All we need to check is whether the union of all intervals matches the side of the largest Rectangle. This can be done in O(nlog(n)) by standard algorithms, or on average O(n) by some hash trick (see http://www.careercup.com/question?id=12523672 , see my last comment (of the last comment) there for the O(n) algorithm ).

For example, say we got two 1*1 rectangles in the first quadrant, there left bottom coordinates are (0,0) and (1,0). Largest rectangle is 2*1 with left bottom coordinate (0,0). Since [0,1] Union [1,2] is [0,2], top side and bottom side match the largest rectangle, similar for left and right side.

Now suppose we got an U shape. 3*1 at (0,0), 1*1 at (0,1), 1*1 at (2,1), we got largest rectangle 3*2 at (0,0). Since for the top side we got [0,1] Union [1,3] does not match [0,3], the algorithm will output the union of above rectangles is not a rectangle.

So you can do this in O(n) on average, or O(nlog(n)) at least if you don't want to mess with some complex hash bucket algorithm. Much better than O(n^4)!

Edit: We have a small problem if there exists empty space somewhere in the middle of all rectangles. Let me think about it....

Edit2: An easy way to detect empty space is for each corner of a rectangle which is not a point on the largest rectangle, we go outward a little bit for all four directions (diagonal) and check if we are still in any rectangle. This is O(n^2). (Which ruins my beautiful O(nlog(n))! Can anyone can come up a better idea?

Answer 4

Assuming your rectangles are aligned to the coordinate axis:

Given two rectangles A, B, you can make a function that subtracts B from A returning a set of sub-rectangles of A (that may be the empty set): Set = subtract_rectangle(A, B)

Then, given a set of rectangles R for which you want to know if their union is a rectangle:

1. Calculate a maximum rectangle Big that covers all the rectangles as ((min_x,min_y)-(max_x,max_y))

2. make the set S contain the rectangle Big: S = (Big)

3. for every rectangle B in R:

   1. S1 = ()

   2. for evey rectangle A in S:

      1. S1 = S1 + subtract_rectangle(A, B)

   3. S = S1

   4. if S is empty then the union of the rectangles is a rectangle.

4. End, S contains the parts of Big not covered by any rectangle from R

If the rectangles are not aligned to the coordinate axis you can use a similar algorithm but that employs triangles instead of rectangles. The only issues are that subtracting triangles is not so simple to implement and that handling numerical errors can be difficult.

Answer 5

I haven't looked at a similar problem in the past, so there maybe far more efficient ways of doing it. The key problem is that you cannot look at containment of one rectangle in another in isolation since they could be adjacent but still form a rectangle, or one rectangle could be contained within multiple.

You can't just look at the projection of each rectangle on to the edges of the bounding rectangle unless the problem allows you to leave holes in the middle of the rectangle, although that is probably a fast initial check that could be performed before the following exhaustive approach:

1. Running through the list once, calculating the minimum and maximum x and y coordinates and the area of each rectangle
2. Create an input list containing your input rectangles ordered by descending size.
3. Create a work list containing the bounding rectangle initially
4. While there are rectangles in the work list
   1. Take the largest rectangle in the input list R
   2. Create an empty list for fragments
   3. for each rectangle r in the work list, intersect r with R, splitting r into a rectangular portion contained within R (if any) and zero or more rectangles not within R. If r was split, discard the portion contained within R and add the remaining rectangles to the fragment list.
   4. add the contents of the fragment list to the work list

Answer 6

A simple approach just came to mind: If two rectangles share an edge[1], then together they form a rectangle which contains both - either the rectangles are adjacent [][ ] or one contains the other [[] ].

So if the list of rectangles forms a larger rectangle, then all you need it to repeatedly iterate over the rectangles, and "unify" pairs of them into a single larger one. If in one iteration you can unify none, then it is not possible to create any larger rectangle than you already have, with those pieces; otherwise, you will keep "unifying" rectangles until a single is left.

[1] Share, as in they have the same edge; it is not enough for one of them to have an edge included in one of the other's edges.

efficiency

Since efficiency seems to be a problem, you could probably speed it up by creating two indexes of rectangles, one with the larger edge size and another with the smaller edge size.

Then compare the edges with the same size, and if they are the same unify the two rectangles, remove them from the indexes and add the new rectangle to the indexes.

You can probably speed it up by not moving to the next iteration when you unify something, but to proceed to the end of the indexes before reiterating. (Stopping when one iteration does no unifications, or there is only one rectangle left.)

Additionally, the edges of a rectangle resulting from unification are by analysis always equal or larger than the edges of the original rectangles.
So if the indexes are ordered by ascending edge size, the new rectangle will be inserted in either the same position as you are checking or in positions yet to be checked, so each unification will not require an extra iteration cycle. (As the new rectangle will assuredly not unify with any rectangle previously checked in this iteration, since its edges are larger than all edges checked.)
For this to hold, in each step of a particular iteration you need to attempt unification on the next smaller edge from either of the indexes:

• If you're in index1=3 and index2=6, you check index1 and advance that index;
• If next edge on that index is 5, next iteration step will be in index1=5 and index2=6, so it will check index1 and advance that index;
• If next edge on that index is 7, next iteration step will be in index1=7 and index2=6, so it will check index2 and advance that index;
• If next edge on that index is 10, next iteration step will be in index1=7 and index2=10, so it will check index1 and advance that index;
• etc.

examples

[A  ][B   ]
[C ][D    ]

A can be unified with B, C with D, and then AB with CD. One left, ABCD, thus possible.

[A  ][B   ]

[C ][D     ]

A can be unified with B, C with D, but AB cannot be unified with CD. 2 left, AB and CD, thus not possible.

[A  ][B    ]
[C ][D  [E]]

A can be unified with B, C with D, CD with E, CDE with AB. 1 left, ABCDE, thus possible.

[A  ][B    ]
[C ][D     ][E]

A can be unified with B, C with D, CD with AB, but not E. 2 left, ABCD and E, thus not possible.

pitfall

If a rectangle is contained in another but does not share a border, this approach will not unify them.

A way to address this is, when one hits an iteration that does not unify anything and before concluding that it is not possible to unify the set of rectangles, to get the rectangle with the widest edge and discard from the indexes all others that are contained within this largest rectangle.

This still does not address two situations.

First, consider the situation where with this map:

A  B  C  D
E  F  G  H

we have rectangles ACGE and BDFH. These rectangles share no edge and are not contained, but form a larger rectangle.

Second, consider the situation where with this map:

A B C D
E F G H
I J K L

we have rectangles ABIJ, CDHG and EHLI. They do not share edges, are not contained within each-other, and no two of them can be unified into a single rectangle; but form a rectangle, in total.

---

With these pitfalls this method is not complete. But it can be used to greatly reduce the complexity of the problem and reduce the number of rectangles to analyse.

Answer 7

General case, thinking in images:

1. | outer_rect - union(inner rectangles) |
2. Check that result is zero

Answer 8

Maybe...

Gather up all the x-coordinates in a list, and sort them. From this list, create a sequence of adjacent intervals. Do the same thing for the y-coordinates. Now you've got two lists of intervals. For each pair of intervals (A=[x1,x2] from the x-list, B=[y1,y2] from the y-list), make their product rectangle A x B = (x1,y1)-(x2,y2)

If every single product rectangle is contained in at least one of your initial rectangles, then the union must be a rectangle.

Making this efficient (I think I've offered about an O(n⁴) algorithm) is a different question entirely.

Answer 9

As jva stated, "Your own version does not take into account that the edges of the rectangles can be non-parallel to each other." This answer also assumes "parallel" rectangles.

If you have a grid as opposed to needing infinite precision, depending on the number and sizes of the rectangles and the granularity of the grid, it might be feasible to brute-force it.

Just take your "largest rectangle possible" and test all its points to see whether each point is in at least one of the smaller rectangles.

Answer 10

I finally was able to find the impressive javascript project (thanks to github search :) !)

https://github.com/evanw/csg.js

Also have a look into my answer here with other interesting projects