1Dのものを使用した2D間隔ツリー

Question

ここからhttp://intervaltree.codeplex.com/SourceControl/list/changesets - >右手側のダウンロードからC＃間隔ツリーコレクションクラスクラスを使用しています。

私は与えられたものと重なるコレクションから間隔を取る必要があります。これは.Get(left, right)で簡単に見えます。しかし、私は2D間隔が必要です。明らかに、これは1Dのものから始めるのが難しくありません。

ネスティングが行われていると聞きました。

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

ただし、ここでもやはり意味がないようです。何か他の場所からのアパートは高価なように見えるし、どこに追加するかは複雑なようだ。

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などの別のコレクションに変換して、それをただちにトラバースするよりもすばやくトラバースできますか？

編集：

おそらく次のようなものです。

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); 
    } 
} 

何to_HashSetが（存在しないことを除く）ので、私は2つのセットが交差する場所を見つけるために、二重ループを使用することを抱えています。また、各要素のxとyはハードコードされています。

フィードバックが本当に好きです。 HashSetとforeachを使ってステップを進める前に、それぞれの要素を比較して希望の境界をオーバーラップさせました。

Answer 1

インターバルツリーではなく、KDツリーのデータ構造を実装する必要はありません。私が正しく覚えていれば、KDツリーは低次元のO（ログN）検索時間を可能にします。

例えば、http://www.codeproject.com/KB/architecture/KDTree.aspxのように多くの結果が返ってきました。あなたのニーズに合っているかどうかを調べたり、そうでない場合は別の実装を見つけることができます。