如何将一组矩形分组到连接区域的"岛屿"中？

Question

问题

我有一系列的java.awt.Rectangles.对于那些不熟悉这门课程的人来说,重要的信息是它们提供了一种.intersects(Rectangle b)功能.

我想编写一个函数来获取这个Rectangles 数组,并将其分解为连接的矩形组.

比方说,例如,这些是我的矩形(构造函数采用的参数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相交B和B相交C.D不相交.一个繁琐的ascii艺术作品也完成了这项工作:

?????????   ?????
?A????? ?   ? D ?
?????????   ?????
  ? B ?                 
?????????????????
? ????? C       ?
?????????????????

因此,我的函数的输出应该是:

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

失败的代码

这是我尝试解决问题的方法:

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;
}

不幸的是,这里似乎有一个无限的递归循环.我没有受过教育的猜测是java不喜欢我这样做:

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

任何人都可以对这个问题有所了解吗？

Answer 1

这是我最终寻求的解决方案。有人能猜测一下它的效率吗？

包java.util；

import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.List;

public class RectGroup extends ArrayList<Rectangle> implements List<Rectangle>
{
    public RectGroup(Rectangle... rects)
    {
            super(rects);
    }

    public RectGroup()
    {
        super();
    }

    public boolean intersects(Rectangle rect)
    {
        for(Rectangle r : this)
            if(rect.intersects(r))
                return true;

        return false;
    }

    public List<RectGroup> getDistinctGroups()
    {
        List<RectGroup> groups = new ArrayList<RectGroup>();
        // Create a list of groups to hold grouped rectangles.

        for(Rectangle newRect : this)
        {
            List<RectGroup> newGroupings = new ArrayList<RectGroup>();
            // Create a list of groups that the current rectangle intersects.

            for(RectGroup group : groups)
                if(group.intersects(newRect))
                    newGroupings.add(group);
            // Find all intersecting groups

            RectGroup newGroup = new RectGroup(newRect);
            // Create a new group

            for(List<Rectangle> oldGroup : newGroupings)
            {
                groups.remove(oldGroup);
                newGroup.addAll(oldGroup);
            }
            // And merge all the intersecting groups into it

            groups.add(newGroup);
            // Add it to the original list of groups
        }
        return groups;
    }
}