How can I group an array of rectangles into "Islands" of connected regions?

Question

The problem

I have an array of java.awt.Rectangles. For those who are not familiar with this class, the important piece of information is that they provide an .intersects(Rectangle b) function.

I would like to write a function that takes this array of Rectangles, and breaks it up into groups of connected rectangles.

Lets say for example, that these are my rectangles (constructor takes the arguments x, y, width,height):

Rectangle[] rects = new Rectangle[]
{
    new Rectangle(0, 0, 4, 2), //A
    new Rectangle(1, 1, 2, 4), //B
    new Rectangle(0, 4, 8, 2), //C
    new Rectangle(6, 0, 2, 2) //D
}

A quick drawing shows that A intersects B and B intersects C. D intersects nothing. A tediously drawn piece of ascii art does the job too:

┌───────┐   ╔═══╗
│A╔═══╗ │   ║ D ║
└─╫───╫─┘   ╚═══╝
  ║ B ║                 
┌─╫───╫─────────┐
│ ╚═══╝ C       │
└───────────────┘

Therefore, the output of my function should be:

new Rectangle[][]{
    new Rectangle[] {A,B,C},
    new Rectangle[] {D}
}

The failed code

This was my attempt at solving the problem:

public List<Rectangle> getIntersections(ArrayList<Rectangle> list, Rectangle r)
{
    List<Rectangle> intersections = new ArrayList<Rectangle>();
    for(Rectangle rect : list)
    {

        if(r.intersects(rect))
        {
            list.remove(rect);
            intersections.add(rect);
            intersections.addAll(getIntersections(list, rect));
        }
    }
    return intersections;
}

public List<List<Rectangle>> mergeIntersectingRects(Rectangle... rectArray)
{
    List<Rectangle> allRects = new ArrayList<Rectangle>(rectArray);
    List<List<Rectangle>> groups = new ArrayList<ArrayList<Rectangle>>();
    for(Rectangle rect : allRects)
    {
        allRects.remove(rect);
        ArrayList<Rectangle> group = getIntersections(allRects, rect);
        group.add(rect);
        groups.add(group);
    }
    return groups;
}

Unfortunately, there seems to be an infinite recursion loop going on here. My uneducated guess would be that java does not like me doing this:

for(Rectangle rect : allRects)
{
    allRects.remove(rect);
    //...
}

Can anyone shed some light on the issue?

Answer 1

What you want is to find connected components. That is, imagine a graph whose vertices correspond to rectangles, and where there is an edge between two vertices if the corresponding rectangles intersect. Then, you want to find and label the connected components of this graph.

Just finding the edges (determining, for each pair of rectangles, whether they intersect) takes O(n²) time, after which you can use either depth-first search or breadth-first search to find all the components in an additional O(E) time, where E < n².

In pseudocode (simple exercise to translate it to Java), it may look something like this:

# r is the list of rectangles
n = length of r (number of rectangles)

#Determine "neighbors" of each vertex
neighbors = (array of n lists, initially empty)
for i in 1 to n:
    for j in 1 to n:
        if i!=j and r[i].intersects(r[j]):
            neighbors[i].append(j)

#Now find the connected components
components = (empty list of lists)
done = (array of n "False"s)
for i in 1 to n:
    if done[i]: continue
    curComponent = (empty list)
    queue = (list containing just i)
    while queue not empty:
        r = pop(head of queue)
        for s in neighbors[r]:
            if not done[s]:
                done[s] = True
                queue.push(s)
                curComponent.push(s)
    #Everything connected to i has been found
    components.push(curComponent)

return components

I'm precomputing neighbors and using "done" labels to save the O(n) factor and make the whole thing O(n²). In fact, this algorithm is for general graphs, but because your graph is rather special — comes from rectangles — you can do even better: it is actually possible to solve the problem in O(n log n) time total, using segment trees.

Answer 2

Alright, I think I got it. This algorithm is rather inefficient, O(n^3) by wich's calculation, but it does seem to work.

I used Set instead of List in getIntersections() to keep from counting the same rectangle twice (although I don't think this is actually necessary). I guess your final result could even be a Set<Set<Rectangle>> but the algorithm should be about the same. I also used Lists everywhere instead of arrays because I think arrays are ugly, but it's easy enough to convert back if you need to. The set newRectanglesToBeAdded lets us decide whether we need to keep looping or not, and also keeps us from adding to a list while we're iterating over it (which is just as bad as trying to remove things from a list while we're iterating over it). I don't think it's the most elegant solution, but it seems to work (at least for the test data you provided).

  public static Set<Rectangle> getIntersections(List<Rectangle> list,
      Rectangle r) {
    Set<Rectangle> intersections = new HashSet<Rectangle>();
    intersections.add(r);

    Set<Rectangle> newIntersectionsToBeAdded = new HashSet<Rectangle>();

    do {
      newIntersectionsToBeAdded.clear();
      for (Rectangle r1 : list) {
        for (Rectangle r2 : intersections) {
          if (!intersections.contains(r1) && r2.intersects(r1)) {
            newIntersectionsToBeAdded.add(r1);
          }
        }
      }
      intersections.addAll(newIntersectionsToBeAdded);
    } while (!newIntersectionsToBeAdded.isEmpty());
    return intersections;
  }

  public static List<Set<Rectangle>> mergeIntersectingRects(List<Rectangle> allRects) {
    List<Set<Rectangle>> grouped = new ArrayList<Set<Rectangle>>();
    while (!allRects.isEmpty()) {
      Set<Rectangle> intersections = getIntersections(allRects, allRects.get(0));
      grouped.add(intersections);
      allRects.removeAll(intersections);
    }
    return grouped;
  }