如何找到所有相交矩形的链？

Question

我有一个矩形数组。其中一些可能会相交，组成一对：

虽然其他的可能会相交，形成一个链：

当然，其中一些可能是单独的。

我想要形成一个列表，其中包括所有的链、对和单个矩形。例如，如果我们有一个看起来像这样的矩形数组：

我想获取以下列表：

    { { A, B, C, D, E },
    { F },
    { G },
    { H, J },
    { K, L },
    { M, N, O } }

其中A、B、C、D、E等均为相应的矩形。

到目前为止，我尝试使用以下代码生成所有可能的排列：

var rectangles = new Rectangle[] { ..., ..., ... }; // my rectangles
var rectanglePermutations = new IEnumerable<IEnumerable<Rectangle>>();
// make all permutations with 2, 3, 4 (and so on) elements
for (var i = 2; i < rectangles.Length; i++)
{
    rectanglePermutations.AddRange(GetPermutations(rectangles, i));
}

IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> items, int count)
{
    var i = 0;
    foreach (var item in items)
    {
        if (count == 1)
        {
            yield return new T[] { item };
        }
        else
        {
            foreach (var result in GetPermutations(items.Skip(i + 1), count - 1))
            {
                yield return new T[] { item }.Concat(result);
            }
        }

        i++;
    }
}

然后我试图找出每个可枚举对象中的所有矩形是否可以形成链：

var result = new List<List<Rectangle>>();
foreach (var permutations in rectanglePermutations)
{
    var chain = new List<Rectangle>(permutations);
    var canFormNewRectangles = true;
    
    do
    {
        var newlyFormedRectanglesCount = 0;
        // get all possible pairs
        var pairs = GetPermutations(chain.Distinct(), 2);
        chain.Clear();
        
        foreach (var pair in pairs)
        {
            // if rectangles in pair intersect
            var union = Rectangle.Union(pair.First(), pair.Last());
            if (union.Width * union.Height > 0)
            {
                // replace them with a new rectangle
                chain.Add(new Rectangle(pair.Min(r => r.Left), pair.Min(r => r.Top), pair.Max(r => r.Right) - pair.Min(r => r.Left), pair.Min(r => r.Top) - pair.Max(r => r.Bottom)));
                newlyFormedRectanglesCount++;
            }
        }
        
        // if we can't make any more new rectangles
        if (newlyFormedRectanglesCount == 0)
        {
            canFormNewRectangles = false;
        }
    }
    while (canFormNewRectangles);
    
    // if all rectangles made a single chain
    if (chain.Count == 1)
    {
        result.Add(permutation.ToList());
    }
}

// add single rectangles to result that are not used in any chains
var usedRectangles = chains.SelectMany(chain => chain).Distinct();
result.AddRange(rectangles.Except(usedRectangles).ToList());

问题在于上面的代码是无效和缓慢的。例如，如果我们有一个由5个矩形组成的链、一个由3个矩形组成的链和2个单独的矩形（总共10个），我们将从第一部分代码得到1013个可能的排列，从第二部分代码至少得到11160次迭代（实际上，对于给定的示例，我们将得到两倍的结果）。使用这种方法来找到仅2个合适的组合是低效的。我相信有更好的方法，需要一些帮助。

- StafordDev

---

矩形是图形的节点，每对矩形通过Rectangle.IntersectsWith返回真（true）形成图中的一条边。然后检测链是连通组件标记的特殊情况。不确定为什么要使用Rectangle.Union来检测重叠。 - Wyck

我觉得了解你想要对形成分支或循环的连通分量做什么是很重要的。任意矩形组可以以比简单链条更有趣的方式重叠。一个矩形可以与超过两个其他矩形重叠，形成图中与3个或更多其他节点相邻的节点。 - Wyck

您的问题有点令人困惑。在您的最后一个图像中，您展示了5个（未标记的）矩形，然后说您想要一个包含6个数组的结果，每个数组包含1到5个矩形，总共有14个不同的矩形。能否请您澄清一下问题？ - Rufus L

在看了你的代码之前，我以为我理解了这个问题。Rectangle.Union返回一个包含两个源矩形的单个矩形。我不明白这与矩形重叠或创建“链”有什么关系。你能否通过编辑问题（而不是在评论中）澄清你想做什么？ - Rufus L

我觉得你缺少使用案例。我可以想到几种方法在现有示例上绘制更多矩形，这些矩形将与2个或更多现有矩形相交 - 如果它们被视为“链”，则会创建循环引用。 - Matt Johnson-Pint

一旦您找到了这些链，我认为值得一提的是，生成链的所有子链是一个单独的、无关的（而且非常简单的）问题。 - Wyck

Answer 1

解决这个问题的第一步应该是找出哪些矩形相交。我认为快速解决方案应该是使用R-Tree，但只要三角形数量有限，详尽检查也足够好。为了存储所有的交点，我们可以使用Microsoft.Collections.Extensions.MultiValueDictionary，另一个选择是矩阵。

var rectangles = new Rectangle[]{...};
var graph = new MultiValueDictionary<int, int>();
for (int i = 0; i < rectangles.Length; i++)
{
    for (int j = i+1; j < rectangles.Length; j++)
    {
        if (rectangles[i].IntersectsWith(rectangles[j]))
        {
            graph.Add(i, j);
            graph.Add(j, i);
        }
    }
}

我们可以将所有的矩形视为一个图形，因此要找出与一个矩形相连的所有矩形，我们需要一种遍历这个图形的方法，例如使用深度优先迭代。我喜欢使用通用的迭代器块来实现，但有些人更喜欢递归解决方案：

public static IEnumerable<T> IterateDepthFirst<T>(T self, Func<T, IEnumerable<T>> selector, HashSet<T> visited)
{
    var stack = new Stack<T>();
    stack.Push(self);
    while (stack.Count > 0)
    {
        var current = stack.Pop();
        if(!visited.Add(current)) continue;
        yield return current;
        foreach (var child in selector(current))
        {
            if (!visited.Contains(child))
            {
                stack.Push(child);
            }
        }
    }
}

visited 集合确保矩形只被返回一次，即使图中存在循环。要找到所有的矩形组，我们只需要重复调用这个方法：

public static IEnumerable<T[]> Segment<T>(
    IEnumerable<T> nodes,
    Func<T, IEnumerable<T>> selector)
{
    var visited = new HashSet<T>(EqualityComparer<T>.Default);
    foreach (T currentNode in nodes)
    {
        if (!visited.Contains(currentNode))
        {
            yield return IterateDepthFirst(currentNode, selector, visited).ToArray();
        }        
    }
}

请注意，我们保持相同的访问集，这样我们就不必担心两次包含一个矩形。

然后可以像这样调用。

var rectangleGroups = Segment(Enumerable.Range(0, rectangles.Length), i => graph[i]);

- JonasH

---

三角形？DYM矩形？ - Wyck

Answer 2

一种获取所有“矩形链”（即相互交叉的所有矩形组）的基本方法是创建一个List<List<Rectangle>>，其中每个内部列表都是一个“链”。然后循环遍历原始的List<Rectangle>，对于每个项目，查看该项目是否与我们已经发现的任何链中的任何项目相交。如果是，则将其添加到该链中。如果不是，则添加一个仅包含此项的新链。

例如：

static List<List<Rectangle>> GetChains(List<Rectangle> rectangles)
{
    if (rectangles == null) return null;
    if (rectangles.Count < 2) return new List<List<Rectangle>> { { rectangles } };

    var chains = new List<List<Rectangle>>();

    foreach(var rectangle in rectangles)
    {
        var chained = false;

        foreach(var chain in chains)
        {
            if (chain.Any(r => r.IntersectsWith(rectangle)))
            {
                chain.Add(rectangle);
                chained = true;
                break;
            }
        }

        if (!chained)
        {
            chains.Add(new List<Rectangle> { rectangle });
        }
    }

    return chains;
}

- Rufus L

---

我认为这个可以构建树形结构（以及链表）。 - Wyck

它返回所有连接矩形的列表。老实说，基于他的示例，我不确定我完全理解这个问题。 - Rufus L

这很公平。也许值得注意的是，这并没有将属于“链”中的矩形按任何特定顺序排列。 - Wyck

Answer 3

矩形是图中的一个节点。如果一个矩形与另一个矩形重叠，则我们将在该图中定义相应的无向边。让我们定义以下关于我们的链的规则：（记得度是一个节点拥有的邻居数）

• 任何度为0的节点都是微不足道的链。
• 任何度为1的节点都可能是链的起点/终点。
• 任何度为2的节点都可能是链的中间链接。
• 任何度为3或更高的节点都不是链的一部分。

我们可以通过定位所有度为1的节点并开始深度优先搜索链的另一端（具有度为1的另一个节点）来找到非微不足道的链。在此过程中，我们仅允许具有度为2的节点。

这个实现的副作用是链是唯一排序的，使得链按其起始节点的索引顺序出现，并且每个链的节点按其起始节点具有比其结束节点更低的索引顺序。

此函数的输出是链的列表。每个链都是形成该链的矩形的索引列表。

public static List<List<int>> FindChains(Rectangle[] rectangles)
{
    List<List<int>> chains = new List<List<int>>();
            
    int N = rectangles.Length;
    List<int>[] neighbours = new List<int>[N];
    for (int i = 0; i < N; ++i) {
        neighbours[i] = new List<int>();
    }
            
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (rectangles[i].IntersectsWith(rectangles[j])) {
                neighbours[i].Add(j);
                neighbours[j].Add(i);
            }
        }
    }

    bool[] visited = new bool[N];
    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            int degree = neighbours[i].Count;
            if (degree == 0) {
                chains.Add(new List<int>() { i });
            } else if (degree == 1) {
                // start the chain
                List<int> chain = new List<int>() { i };
                int prev = i;
                int cur = neighbours[i][0];
                // Follow the chain
                while (neighbours[cur].Count == 2) {
                    chain.Add(cur);
                    int temp = cur;
                    // Get the "other" neighbour
                    cur = neighbours[cur][0] + neighbours[cur][1] - prev;
                    prev = temp;
                }
                // verify that we ended at a node with degree 1
                if (neighbours[cur].Count == 1) {
                    chain.Add(cur);
                    chains.Add(chain);
                    // Stop this end from being used as the start of the same chain but in reverse.
                    visited[cur] = true;
                }
            }
        }
    }

    return chains;
}

下面列出了一些有趣的测试案例。红线连接链式矩形的质心。非链式连接的矩形没有标记。

- Wyck

---

我确认这个实现在O(N^2)时间内构建邻居列表。 - Wyck

Answer 4

我建议将此问题分解为两个一维问题。

首先，考虑x轴。解析你的矩形并将每对x坐标放入一个数组中，注意每个坐标是左端点还是右端点，并且属于哪个矩形。

接下来，对该数组进行排序。

然后，按顺序解析该数组。跟踪当前范围内的矩形数量以及哪些特定矩形在范围内（范围内意味着您在数组中的当前位置位于它们的左端点和右端点之间）。

维护一个矩形ID => 潜在重叠矩形ID 的映射。

在解析数组时，每次遇到右端点时，使用与右端点相关联的矩形作为键更新映射，值为在范围内的矩形ID集合。反之亦然（每个范围内的矩形ID都是一个键，离开的矩形被添加到关联集合中）。

接下来，对y轴执行相同的操作，但这次遇到端点（在本例中为顶部端点）时，将当前范围内的ID与映射中的值取交集。这些是在两个轴上都在范围内的所有矩形，因此与之相交。

现在你有了所有相交的矩形对。

- Dave