c# - 使用 GroupBy 通过重叠范围对集合进行分区

Question

考虑一个 Rectangle 类，它通过角定义一个区域:

public class Rectangle {
    public int X1 { get; set; }
    public int Y1 { get; set; }
    public int X2 { get; set; }
    public int Y2 { get; set; }
}

可以说两个 Rectangle 对象 Overlap 如果它们有任何共同的区域。下面是实现 Overlap 逻辑的简单方法:

public bool Overlaps(Rectangle other) {
    return (this.X1 < other.X2 && this.X2 > other.X1 &&
        this.Y1 < other.Y2 && this.Y2 > other.Y1);
}

现在我想将一组 Rectangle 对象分成重叠的矩形组。要注意的是，组中的某些矩形不一定与同一组中的其他矩形重叠，只要它们共享其他重叠的矩形即可。结果总是明确定义的，但没有从矩形到最终重叠组的直接映射。

直觉上似乎可以使用 GroupBy 来构建重叠矩形组。但是，没有定义矩形是否属于同一组的“键”；重要的是它们是否重叠。是否可以使用 GroupBy 解决此问题，即使这意味着递归分组直到所有适当的组组合在一起？

Answer 1

不，GroupBy 需要一个可以通过查看一个实例并仅查看一个实例来确定的属性。

但是，有一个相对简单的解决方案:您可以使用 Disjoint-Set Data Structure (这不仅仅是一个美化的链表)，及其相关的 union 算法。整个算法只需几十行代码，理解和调试都比较简单。

给你的矩形序号，并在每对矩形上运行你的交集算法。当您检测到重叠时，对相应的不相交集合结构执行集合并集。完成后，每个成员都将指向其集合的“根”编号。您可以使用这些根号在 LINQ 中按列表分组。