4

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.

Jon Seigel
  • 12,251
  • 8
  • 58
  • 92
uj2
  • 1,391
  • 2
  • 15
  • 15
  • Do you mean take the union of the rectangles and split it out into rectangular regions? Or must the union of the original lines also be expressed in the output? In other words, if I have two 10x20 rectangles that abut, could I output a single 20x20 square? Or do I need to always have at least two outputs if I have two inputs? – tfinniga May 03 '10 at 16:10
  • The only requeirements from the (union of the) output set is to occupy the same area as the (union of the) input set, and to be composed of non-overlapping rectangles. It's desirable that it'll also be minimal: include as few rects as possible. So, yes, you'd better spit out a single rect in that case. – uj2 May 03 '10 at 20:03
  • What programming language are you using? – tfinniga May 06 '10 at 19:55
  • For anyone showing up in the future - https://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles-without is a duplicate of this with an optimal and efficient solution in the answers. – Julian Oct 03 '20 at 16:57
  • @Julian - That question is not a duplicate of this question, as that question explicitly does not have overlapping rectangles while this one explicitly does. The solution also seems to expect a different layout of input data. – Tustin2121 Jul 17 '22 at 15:36

2 Answers2

8

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... :)

tzaman
  • 46,925
  • 11
  • 90
  • 115
  • This comment has spurred some good ideas for me, I've gotten most of the way through an implementation but am having trouble with some edge cases. Can you elaborate on the end-event case? What does it mean for a rectangle to 'not be covering anything anymore'? – schellsan Apr 19 '12 at 01:25
  • @schellsan - imagine a vertical line sweeping "left to right" over the input set (-x to +x). When you hit the start of any input rectangle, you need to create a new output rectangle to cover it, unless it's already fully-covered by one of your existing output rectangles. When you reach the end of any input rectangle, if there are no other input rectangles in that space (of y-coords) you need to end some output rectangle (and perhaps create some new ones, depending on the input configuration). – tzaman Apr 19 '12 at 20:04
  • Yes, this is what I've figured. Thanks for you help! – schellsan Apr 20 '12 at 00:43
1

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.

tfinniga
  • 6,693
  • 3
  • 32
  • 37