1D를 사용하는 2D 간격 트리

Question

여기에서 C# 간격 트리 컬렉션 클래스 클래스를 사용하고 있습니다. http://intervaltree.codeplex.com/SourceControl/list/changesets -> 오른쪽에서 다운로드하십시오.

주어진 컬렉션과 겹치는 컬렉션의 간격을 가져와야합니다. 이것은 .Get(left, right)으로 쉽게 보입니다. 그러나 2D 간격이 필요합니다. 분명히 1D 것들로 시작하는 것이 어렵지 않습니다.

중첩으로 처리되는 것으로 들었습니다.

IntervalTree<IntervalTree<stored_type, float>, float> intervals; 

그러나이 경우에도 마찬가지입니다. 움직이는 간격이 다른 것에서 Appart는 비싸고 추가 할 곳을 찾는 것이 복잡해 보입니다.

IntervalTree<stored_type, float> intervals_x; 
IntervalTree<stored_type, float> intervals_y; 

그래도 수행 방법은 모르겠지만, 수행 방법은 Get(left, right, upper, lower)입니다. 아마도 stored_type의 인스턴스가 존재할 것이고 두 세트에 속할 것입니다.하지만 물건이 바뀌면 세트가 스스로 재설정되는 경우 문제가 발생합니까?

그러나 .Get(...)은 List<stored_type>을 반환합니다. 간격 목록에있는 것보다 훨씬 적지 만 처리가 빨리 필요한 항목 인 여전히 List의 많은 항목이 있지만 독립적으로 주문이 필요하지 않습니다. List을 LinkedList 또는 HashSet과 같은 다른 컬렉션으로 변환하여 트래버스하는 것보다 빠르게 트래버스 할 수 있습니까?

편집 :

다음과 같이 표시 될 수 있습니다. 거기에 더 to_HashSet는()입니다 그래서 두 세트가 교차하는 곳을 찾아 더블 루프를 사용하는 데 제외 것을

class interval_tree_2D 
{ 
    private IntervalTree<stored_type, float> x = 
     new IntervalTree<stored_type, float>(); 
    private IntervalTree<stored_type, float> y = 
     new IntervalTree<stored_type, float>(); 

    public void add(stored_type n, 
     float left, float right, float lower, float upper) 
    { 
     intervals_x.AddInterval(left, right, n); 
     intervals_y.AddInterval(upper, lower, n); 
    } 

    public HashSet<stored_type> get(
     float left, float right, float lower, float upper) 
    { 
     var i1 = x.Get(left, right); 
     var i2 = y.Get(lower, upper); 
     var i3 = i1.to_HashSet(); 
     var i4 = i2.to_HashSet(); 
     return i3.union(i4); 
    } 
} 

. 또한 각 요소의 x와 y는 하드 코딩되어 있습니다.

나는 정말 약간의 피드백을 원합니다. HashSet과 foreach를 사용하여 단계를 밟기 전에 각 요소를 비교하여 원하는 경계를 겹쳤습니다.

Answer 1

인터벌 트리가 아니라 KD- 트리 데이터 구조를 구현할 필요는 없습니다. KD 트리를 사용하면 올바르게 기억하면 낮은 차원에서 O (로그 N) 검색 시간을 사용할 수 있습니다.

빠른 결과는 예를 들어 http://www.codeproject.com/KB/architecture/KDTree.aspx과 같이 많은 결과를 나타 냈습니다. 사용자의 요구에 맞는지 확인하고 그렇지 않은 경우 다른 구현을 찾을 수 있습니다.