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?
