我怎样才能组矩形阵列为＆QUOT;离岛＆QUOT;连接区域？ [英] How can I group an array of rectangles into "Islands" of connected regions?

问题描述

我有 java.awt.Rectangle中的数组的形式。对于那些谁不熟悉这个类，信息的重要的部分是，他们提供了一个 .intersects（矩形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.

我想编写一个函数，它接受矩形 21。这阵，并打破它变成矩形连接组。

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

让我们说，例如，这些是我的矩形（构造函数的参数 X ，是，宽度，高度）：

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
}

有一个快速的绘图显示，相交B和B相交C.Ð相交什么。一个不厌其烦地绘制一张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}
}

的失败code

这是我在尝试解决问题：

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

这篇关于我怎样才能组矩形阵列为＆QUOT;离岛＆QUOT;连接区域？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！