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.

Answer 2

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

Answer 3

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.