javascript - Javascript: 2 つのプロパティで検索するためのオブジェクトのインデックス セット

Question

これにはどのデータ構造/アルゴリズムを使用すればよいですか?

(x, y) で指定された位置のデカルト グリッド上に多数のポイントがあります。x と y の指定された範囲内にあるポイント (オブジェクト) のセットを返す高速検索が必要です。(グリッド内の四角形)。

おそらく、これを行う軽量のフレームワークがありますか?

ありがとう

Answer 1

ポイントを x と y の 2 つの属性を持つオブジェクトとして保存し、残りの属性をタイ ブレーカーとして使用して、一方の属性または他方の属性でそれらを並べ替える比較関数を使用します。

function Point(x, y){
    this.x = x;
    this.y = y;
    this.compareTo =function(otherPoint){
        if(otherPoint.x != this.x)
            return this.x-otherPoint.x;
        return this.y-otherPoint.y;
    }
}

points[n] = new Point(someX, someY);

次に、並べ替えアルゴリズム (QuickSort - with O(n log(n)) など) を使用して並べ替え、単純な挿入並べ替えを使用して、ポイントが行き来するときに並べ替えを維持できます。長方形の選択を使用する必要がある場合は、単純にそれら全体でバイナリ検索 ( O(log(n)) ) を実行して、最初の属性 (たとえば、x) の境界を見つけてから、その小さなセット全体で境界を見つけることができます。y残りのセットは探しているものになり、検索時間 ( O (4 log(n) ) ) が最悪のケースになり、挿入時間が線形になります (最悪の場合)。私がそう言うなら、あまりにもみすぼらしいことではありません。