使用的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算法。整个算法可以用几十行代码进行编码，并且相对易于理解和调试。

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