How can I group an array of rectangles into "Islands" of connected regions?
- by Eric
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?
