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

Posted by Eric on Stack Overflow See other posts from Stack Overflow or by Eric
Published on 2010-02-12T19:56:10Z Indexed on 2010/05/04 20:28 UTC
Read the original article Hit count: 270

Filed under:
|
|
|
|

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?

© Stack Overflow or respective owner

Related posts about java

Related posts about recursion