Looking for a non "brute force" algorithm to remove intersecting areas of a collection of Rects

Question

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:

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.

Answer 1

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.