java - 如何将矩形数组分组为 "Islands"的连接区域？

Question

问题

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

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

例如，假设这些是我的矩形(构造函数接受参数 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

你想要的是找到connected components .也就是说，想象一个图，其顶点对应于矩形，并且如果相应的矩形相交，则两个顶点之间有一条边。然后，您想找到并 label该图的连通分量。

仅仅找到边(确定每对矩形是否相交)需要 O(n²) 时间，之后您可以使用 depth-first search或 breadth-first search在额外的 O(E) 时间内找到所有组件，其中 E < n²。

在伪代码中(将其转换为 Java 的简单练习)，它可能看起来像这样:

# r is the list of rectangles
n = length of r (number of rectangles)

#Determine "neighbors" of each vertex
neighbors = (array of n lists, initially empty)
for i in 1 to n:
    for j in 1 to n:
        if i!=j and r[i].intersects(r[j]):
            neighbors[i].append(j)

#Now find the connected components
components = (empty list of lists)
done = (array of n "False"s)
for i in 1 to n:
    if done[i]: continue
    curComponent = (empty list)
    queue = (list containing just i)
    while queue not empty:
        r = pop(head of queue)
        for s in neighbors[r]:
            if not done[s]:
                done[s] = True
                queue.push(s)
                curComponent.push(s)
    #Everything connected to i has been found
    components.push(curComponent)

return components

我正在预先计算邻居并使用“完成”标签来保存 O(n) 因子并使整个事情成为 O(n²)。事实上，这个算法是针对一般图的，但是因为你的图很特别——来自矩形——你可以做得更好:实际上可以在 O(n log n) 时间内解决这个问题，使用 segment trees .