Merging and splitting overlapping rectangles to produce non-overlapping ones

Question

I am looking for an algorithm as follows:

Given a set of possibly overlapping rectangles (All of which are "not rotated", can be uniformly represented as (left,top,right,bottom) tuplets, etc...), it returns a minimal set of (non-rotated) non-overlapping rectangles, that occupy the same area.

It seems simple enough at first glance, but prooves to be tricky (at least to be done efficiently).

Are there some known methods for this/ideas/pointers?

Methods for not necessarily minimal, but heuristicly small, sets, are interesting as well, so are methods that produce any valid output set at all.

Answer 1

Something based on a line-sweep algorithm would work, I think:

• Sort all of your rectangles' min and max x coordinates into an array, as "start-rectangle" and "end-rectangle" events
• Step through the array, adding each new rectangle encountered (start-event) into a current set
• Simultaneously, maintain a set of "non-overlapping rectangles" that will be your output set
• Any time you encounter a new rectangle you can check whether it's completely contained already in the current / output set (simple comparisons of y-coordinates will suffice)
• If it isn't, add a new rectangle to your output set, with y-coordinates set to the part of the new rectangle that isn't already covered.
• Any time you hit a rectangle end-event, stop any rectangles in your output set that aren't covering anything anymore.

I'm not completely sure this covers everything, but I think with some tweaking it should get the job done. Or at least give you some ideas... :)

Answer 2

So, if I were trying to do this, the first thing I'd do is come up with a unified grid space. Find all unique x and y coordinates, and create a mapping to an index space. So if you have x values { -1, 1.5, 3.1 } then map those to { 0, 1, 2 }, and likewise for y. Then every rectangle can be exactly represented with these packed integer coordinates.

Then I'd allocate a bitvector or something that covers the entire grid, and rasterize your rectangles in the grid. The nice thing about having a grid is that it's really easy to work with, and by limiting it to unique x and y coordinates it's minimal and exact.

One way to come up with a pretty quick solution is just dump every 'pixel' of your grid.. run them back through your mapping, and you're done. If you're looking for a more optimal number of rectangles, then you've got some sort of search problem on your hands.

Let's look at 4 neighboring pixels, a little 2x2 square. When I write algorithms like these, typically I think in terms of verts, edges, and faces. So, these are the faces around a vert. If 3 of them are on and 1 is off, then you've got a concave corner. This is the only invalid case. For example, if I don't have any concave corners, I just grab the extents and dump the whole thing as a single rectangle. For each concave corner, you need to decide whether to split horizontally, vertically, or both. I think of the splitting as marking edges not to cross when finding extents. You could also do it as coloring into sets, whatever is easier for you.

The concave corners and their split directions are your search space.. you can use whatever optimization algorithm you'd like. Branch/bound might work well. I bet you could find a simple heuristic that performs well (for example, if there's another concave corner directly across from the one you're considering, always split in that direction. Otherwise, split in the shorter direction). You could just go greedy. Or you could just split every concave vert in both directions, which would generally give you fewer rectangles than outputting every 'pixel' as a rect, and would be pretty simple.

Reading over this I realize that there may be areas that are unclear. Let me know if you want me to clarify anything.