Alex Rivera | Logout

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

Asked 2010-02-12T19:56:10.303
13

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>>();
  
Edit
Report

2 Answers

1

(this is too long for a comment)

A quick drawing does NOT show that A intersects B: A has an height of 4 while B start at an Y position of 5, how could they intersect!?

You can verify it with the following that prints out 'false':

System.out.println( new Rectangle(0, 0, 2, 4).intersects( new Rectangle(1, 5, 4, 2) ) );

Then your method signature are incomplete so is your code example.

If you clarify a bit your problem and give a working, correct, example, then I've got a very nice solution for you.

answered 2010-02-12T20:37:20.417
0

You cannot remove an object from a list your iterating through, iterator object or not, you will need to find another way

answered 2010-02-12T20:26:39.767

Your Answer