5

I have an n-sized collection of Rects, most of which intersect each other. I'd like to remove the intersections and reduce the intersecting Rects into smaller non-intersecting rects.

I could easily brute force a solution, but I'm looking for an efficient algorithm.

Here's a visualization:

Original:

original

Processed:

processed

Ideally the method signature would look like this:

public static List<RectF> resolveIntersection(List<RectF> rects);

the output would be greater or equal to the input, where the output resolves the above visual representation.

Michael Pardo
  • 2,590
  • 3
  • 24
  • 33
  • what is the thinking for the red rectangle claiming space that could have been claimed by the green or orange rectangles (making them longer...)? – cyber-monk Feb 16 '12 at 00:42
  • I arbitrarily split up that rectangle. – Michael Pardo Feb 16 '12 at 01:47
  • It turns out that this is really what I wanted: http://google-maps-utility-library-v3.googlecode.com/svn/trunk/routeboxer/docs/examples.html I probably should have asked for a solution to the actual problem instead of a solution to the problem I created in the middle of my implementation. – Michael Pardo Aug 06 '14 at 13:43

3 Answers3

6

Sweepline algoithms are good at processing intersections in 2D universes. I mean consider an horizontal line moving down from a rectangle edge to the next rectangle edge. The line hits a number of rectangles, forming the so-called active lists. The active list is kept updated at every move.

By studying the ranges of abscissas along the horizontal line, you can detect the overlaps.

A careful study of all configurations should allow you to split the rectangles the way you want in a single sweep, with lower complexity than brute force (closer to N^1.5 than to N^2).

  • This is probably marginally more efficient than brute forcing in the above example, but I think it's the best I'll be able to do. Thanks. – Michael Pardo Feb 16 '12 at 01:54
  • 1
    It is known that the rectangle intersection problem can be solved in optimal time O(N Log(N) + K), where K is the actual number of intersections, for example by using interval trees. Alternatively to line sweeping, divide & conquer algorithms have been published. –  Feb 16 '12 at 10:45
2

this is a problem I solved in the past. The first thing it to sort the rectangles using the x or y value of one of the edges. Lets say you order in the y-direction and use the top edge. The topmost rectangle in your example is first in sorted order. For each rectangle you know its size in the y-direction.

Now, for each entry (call it the the current entry, it corresponds to a rectangle)in the sorted list you search forward through the list until you reach an entry greater than the current entry + the corresponding rectangle size. (call it the stopping entry)

Any entries in the sorted list between the current entry and this stopping entry will be potential intersections. Simply check if the rectangles x-ranges intersect.

When choosing to sort in the x or y direction, it will be better to choose the dimension that is larger as this will imply fewer intersection on average so less checking.

Here is an example. Rectangles are defined as R(x1,x2,y1,y2) where x1 is the left side, x2 is right side, y1 is top and y2 is bottom

rectangle 1 (1,5,0,4) 
rectangle 2 (7,9,6,8)
rectangle 3 (2,4,2,3)
rectangle 4 (3,6,3,7)
rectangle 5 (3,6,9,15)

sort according to y1 to give 

#              y1  size
rectangle 1     0   4
rectangle 3     2   3
rectangle 4     3   4
rectangle 2     6   2
rectangle 5     9   6

so, rectangle 1 has y1 + size = 0 + 4 = 4 implying it will potentially intersect rectangle 3 (y1 value = 3 < 4) and rectangle 4 (y1 value = 3 < 4) but not rectangle 2 (y1 value = 6 > 4)...no need to check any rectangels in the list after 2

Rectangle 3 has y2 + size = 2 + 3 = 5 implying it will potentially intersect rectangle 4 (y1 value = 3 < 5) but not recatngle 2 (y1 value = 6 > 5) no need to check any rectangels in the list after 2

Rectangle 4 has y2 + size = 3 + 4 = 7 implying it will potentially intersect rectangle 2 (y1 value = 6 < 7) but not recatngle 5 (y1 value = 9 > 7)

Of course, with large numbers of rectangles you will generally only have to check a fraction of the possible pairs for intersection.

martino
  • 308
  • 7
  • 14
  • an improvement: to decide on which dimension to use for sorting you could look at the range of values in that dimension divided by the average rectangle size in that dimension. In the above example, the average y size is 19/5 while the average x size is 15/5 so you would expect (with no other knowledge) that these are more intersections in the y direction (rectangle y-sizes are larger on average than x-sizes so more chance they will intersect).This choice can make a big difference if you are looking at thousands of rectangles. – martino Feb 16 '12 at 15:17
-2

what you're descrbing is the packing problem, have a look at wikipedia

it refers to this article describing an algorithm for packing rectangles in rectangles

this is from the article:

This article describes a fast algorithm to pack a series of rectangles of varying widths and heights into a single enclosing rectangle, with no overlap and in a way that minimizes the amount of wasted space in the enclosing rectangle.

yurib
  • 8,043
  • 3
  • 30
  • 55
  • 3
    Are you sure? How do you break the overlapping rectangles into smaller non-overlapping by using rectangle packing? It seems to me, that the solution could be based on the sweep line algorithm instead: http://en.wikipedia.org/wiki/Sweep_line_algorithm . – Timo Feb 16 '12 at 00:20
  • @Timo its a variation of the packing problem, i've added the first few lines of the introduction. – yurib Feb 16 '12 at 00:28
  • @Timo although, i've never heard of the sweep line algorithm before, from what i've read it sounds interesting, it might also be a good approach. – yurib Feb 16 '12 at 00:30
  • 1
    This is not inside another rectangle, the enclosing bounds is made of the union of all rectangles. Sweep line seems closer. – Michael Pardo Feb 16 '12 at 01:48