如何将矩形数组分组到连接区域的“岛屿”中？

algorithm java geometry recursion arraylist

2022-09-04 03:39:23

问题

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

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

例如，假设这些是我的矩形（构造函数采用参数，，，）：xywidthheight

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 不与任何相交。一件乏味的阿西伊艺术品也可以完成这项工作：

┌───────┐   ╔═══╗
│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);
    //...
}

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

答案 1

您需要的是查找连接的组件。也就是说，想象一个图形，其顶点对应于矩形，如果相应的矩形相交，则两个顶点之间有一条边。然后，您要查找并标记此图的已连接组件。

仅查找边（确定每对矩形是否相交）就需要 O（n²）时间，之后您可以使用深度优先搜索或广度优先搜索在额外的 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）时间总计的问题。

答案 2

好吧，我想我明白了。这个算法效率相当低下，根据它的计算，O（n^3），但它似乎确实有效。

我用而不是in来防止对同一个矩形进行两次计数（尽管我认为这实际上没有必要）。我想你的最终结果甚至可能是一个，但算法应该是大致相同的。我也在任何地方都使用s而不是数组，因为我认为数组很丑陋，但是如果需要，可以很容易地转换回来。该集合让我们决定是否需要继续循环，并且还可以防止我们在迭代列表时将其添加到列表中（这与在迭代列表时尝试从列表中删除内容一样糟糕）。我不认为这是最优雅的解决方案，但它似乎有效（至少对于您提供的测试数据）。SetListgetIntersections()Set<Set<Rectangle>>ListnewRectanglesToBeAdded

  public static Set<Rectangle> getIntersections(List<Rectangle> list,
      Rectangle r) {
    Set<Rectangle> intersections = new HashSet<Rectangle>();
    intersections.add(r);

    Set<Rectangle> newIntersectionsToBeAdded = new HashSet<Rectangle>();

    do {
      newIntersectionsToBeAdded.clear();
      for (Rectangle r1 : list) {
        for (Rectangle r2 : intersections) {
          if (!intersections.contains(r1) && r2.intersects(r1)) {
            newIntersectionsToBeAdded.add(r1);
          }
        }
      }
      intersections.addAll(newIntersectionsToBeAdded);
    } while (!newIntersectionsToBeAdded.isEmpty());
    return intersections;
  }

  public static List<Set<Rectangle>> mergeIntersectingRects(List<Rectangle> allRects) {
    List<Set<Rectangle>> grouped = new ArrayList<Set<Rectangle>>();
    while (!allRects.isEmpty()) {
      Set<Rectangle> intersections = getIntersections(allRects, allRects.get(0));
      grouped.add(intersections);
      allRects.removeAll(intersections);
    }
    return grouped;
  }