사용 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의 목록별로 그룹화 할 수 있습니다.