如何将矩形数组分组为“岛屿"?连接的区域? [英] How can I group an array of rectangles into "Islands" of connected regions?

问题描述

我有一个 java.awt.Rectangle 数组.对于那些不熟悉这个类的人来说，重要的信息是它们提供了一个 .intersects(Rectangle b) 函数.

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.

我想编写一个函数，该函数接受这个 Rectangle 数组，并将其分解为多组相连的矩形.

I would like to write a function that takes this array of Rectangles, and breaks it up into groups of connected rectangles.

例如，假设这些是我的矩形(构造函数采用参数 x、y、width、height):

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 与 B 相交，B 与 C 相交.D 不相交.一幅乏味的 ascii 艺术作品也可以完成这项工作:

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

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

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?

推荐答案

这是我最终想要的解决方案.谁能猜一下它的效率?

This is the solution I went for in the end. Can anyone take a guess to its efficiency?

包 java.util;

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

这篇关于如何将矩形数组分组为“岛屿"?连接的区域?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！