使用的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中的列表進行分組。