2D ジオメトリに n 個のランダムな点があり、各点について4つ(存在しない場合はそれ以下)の最も近い点( 、、、)pを見つける必要があります。ここで、qaは最も近い左上の点、qbは最も近い右上の点です。qcは点pに最も近い左下の点で、qdは最も右下の点です。同じx座標を持つものを左、同じy座標を持つものを下と見なします。qaqbqcqd
ポイント座標とその最近傍参照を格納するのに最適なデータ構造は何ですか? 最速または最もパフォーマンスの高いアルゴリズムはどれですか?
注: この問題は、各ポイントに 4 つの隣接ポイントが必要なため、最近傍アルゴリズムよりもはるかに重要です。
空間充填曲線と四分木のデータ構造を試すことができます。空間充填曲線は 2 次元を 1 次元に縮小し、2 乗グリッドで最適に機能します。四分木は、平面を 4 つのクワッドに分割します。空間充填曲線は、2 つの変数を取り、結果として 1 つの数値を与える数学関数です。3、4、5 個の変数を持つこともできますが、最も単純なのは 2 個の変数です。1 つの数値を指定し、2 つの変数を取るため、2 次元以上の質問に役立ちます。
k-dim ツリー インデックス (この場合は k=2) を使用して、クワッド ツリーを作成します。これにより、ポイントの上下左右のスペースを効率的に検索できるようになります。これについてはおそらく dmbs でクエリを作成できますが、概念的には、ポイント自体の「クワッド」を検索し、クワッド内のポイントの位置に応じて、一方向に最も近いポイントが見つかったかどうかを知ることができます。次に、残りのポイントを検索するクワッドがわかります。
対称性が存在することがわかっている各ポイントに対してこれを行っているため、ポイント P1 は P2 を最も近い左隣として持つため、P2 は P1 を最も近い右隣として持つことになります。したがって、それに応じてポイント オブジェクトを更新します。