如何高效查找所有相交矩形的连通链、对及单个矩形

问题描述 #

给定一个Rectangle数组，其中矩形存在三种关系：

• 部分矩形两两直接相交（形成矩形对）
• 部分矩形通过间接相交形成连通链（比如A和B相交，B和C相交，则A、B、C属于同一连通链）
• 部分矩形独立存在（不与任何其他矩形相交）

需要将这些矩形按连通关系分组，最终得到包含所有连通链、矩形对及单个矩形的分组列表，示例结果如下：

{ 
    { A, B, C, D, E }, // 连通链
    { F }, // 独立矩形
    { G }, // 独立矩形
    { H, J }, // 矩形对
    { K, L }, // 矩形对
    { M, N, O } // 连通链
}

现有方案的问题 #

原方案通过生成所有矩形的排列组合，再逐一验证是否能形成连通链，这种方法存在严重的效率问题：

• 排列组合的数量随矩形数量呈指数级增长（比如10个矩形的情况下，仅2元素到9元素的排列数就超过10000），绝大多数排列都是无效计算
• 验证连通性的逻辑重复且复杂，进一步降低了效率

高效实现思路 #

这个问题本质是图的连通分量求解问题：

1. 将每个矩形视为图的一个节点
2. 如果两个矩形直接相交（Rectangle.IntersectsWith返回true），则在这两个节点之间建立一条边
3. 通过**深度优先搜索（DFS）或广度优先搜索（BFS）**遍历图，找出所有连通分量——每个连通分量就是一组连通的矩形

这种方法的时间复杂度为O(n²)（n为矩形数量），相比原方案的O(n!)效率提升几个数量级。

C# 实现代码示例 #

using System;
using System.Collections.Generic;
using System.Drawing; // 若使用自定义Rectangle需调整相交判断逻辑
using System.Linq;

public class RectangleGrouping
{
    public static List<List<Rectangle>> GetConnectedRectangleGroups(Rectangle[] rectangles)
    {
        var groups = new List<List<Rectangle>>();
        var visited = new bool[rectangles.Length];

        for (int i = 0; i < rectangles.Length; i++)
        {
            if (!visited[i])
            {
                // 用BFS遍历当前矩形的所有连通节点
                var group = new List<Rectangle>();
                var queue = new Queue<int>();
                queue.Enqueue(i);
                visited[i] = true;

                while (queue.Count > 0)
                {
                    int currentIndex = queue.Dequeue();
                    group.Add(rectangles[currentIndex]);

                    // 遍历所有未访问矩形，检查是否与当前矩形相交
                    for (int j = 0; j < rectangles.Length; j++)
                    {
                        if (!visited[j] && rectangles[currentIndex].IntersectsWith(rectangles[j]))
                        {
                            visited[j] = true;
                            queue.Enqueue(j);
                        }
                    }
                }

                groups.Add(group);
            }
        }

        return groups;
    }

    // 测试示例
    public static void Main()
    {
        var rects = new Rectangle[]
        {
            new Rectangle(0,0,2,2), // A
            new Rectangle(1,1,2,2), // B（与A相交）
            new Rectangle(3,3,2,2), // C（与B相交）
            new Rectangle(6,6,2,2), // D（独立）
            new Rectangle(8,8,2,2), // E（独立）
            new Rectangle(10,10,2,2), // F
            new Rectangle(11,11,2,2)  // G（与F相交）
        };

        var result = GetConnectedRectangleGroups(rects);
        foreach (var group in result)
        {
            Console.WriteLine($"Group: {string.Join(", ", group.Select(r => $"({r.X},{r.Y},{r.Width},{r.Height})"))}");
        }
    }
}

关键说明 #

• 相交判断：使用Rectangle.IntersectsWith方法直接判断两个矩形是否相交，比计算Union面积更高效准确
• 连通性遍历：BFS/DFS确保能找到所有直接或间接相交的矩形，不会遗漏连通链中的任何元素
• 去重处理：通过visited数组标记已处理的矩形，避免重复分组

内容的提问来源于stack exchange，提问作者StafordDev