1

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

指定されたコレクションと重複するコレクションから間隔を取得する必要があります。これは で簡単に思え.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 のインスタンスが存在し、両方のセットに属しますが、状況が変化したときにセットが再構成された場合、問題は発生しますか?

ただし、 a が.Get(...)返されますList<stored_type>。間隔リストにあるものよりもはるかに少なくなりますが、これにはまだ大量のアイテムListがあり、迅速に処理する必要がありますが、独立して注文する必要はありません. を LinkedList や HashSet などの別のコレクションに変換してList、単にトラバースするよりも速くトラバースできますか?

編集：

したがって、おそらく次のようなものです。

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 を使用してそれをステップ実行し、各要素を比較して目的の境界をオーバーラップさせていました。

4

1 に答える 1

2

Interval Tree ではなく KD-Tree データ構造の実装は必要ないようです。私の記憶が正しければ、KD ツリーは低次元の O(log N) 検索時間を有効にします。

簡単なグーグル検索で多くの結果が返されました。たとえば、次のようになります。

于 2012-01-08T21:36:10.730 に答える