最寄りのNeighborを解決するための最善のパフォーマンスクリティカルアルゴリズム

Question

x、yペアのリストがあります。すべてのペアは、2D空間上の点を表します。私はこのリストから最も近い点を特定の点xq、yqにしたいと思います。この問題のための最高のパフォーマンスクリティカルなアルゴリズムは何ですか？ポイントのLispは変更されません。つまり、私は挿入と削除を実行する必要はありません。私はちょうどこのセットのターゲットxq、yqポイントの最近隣を見つけたい。

編集1：ありがとうございます！ Stephan202が正しく推測しているので、私はこれを繰り返し実行したい。関数のように。リストは必ずしもソートされているわけではありません（実際にはどのようにソートすることができないのですか？2列のaとyの主キーを持つテーブルのように？

リストに基づいてデータ構造を1回構築してから、関数でこの生成されたデータ構造を使用します（このプロセス自体が関連する場合）。

ありがとうございます。それは、KD-Treeのデータ構造が答えの良い候補であると思われます（そして、私はそれがそうであると感じます、私はいくつかの関連する結果を得る時に更新します）。

編集2：この問題は「最近隣」と呼ばれています。

編集3：最初のタイトルは「空間検索と空間索引付けのためのアルゴリズムの検索（最近隣）」でした。私は新しいタイトルを選んだ：「最寄りのNeighborを解決するための最高のパフォーマンスクリティカルアルゴリズム」。私は最初のデータに対して挿入と削除操作を実行したくないので、それらから最も近いものだけを新しいポイントに挿入したいので、私はKD-Treesに取り組むことを選択しました。ありがとうございます！

Answer 1

を含むセクションのみに同じセクションと隣接するセクション内のポイントで開始し、もし1点以上の点で最も近い点を見つけることを計画している場合は、ツリーを使用する必要があります。

私はKDツリーを推奨します。その実装は、OpenCV 2.0のようないくつかのパッケージで簡単に見つけることができます。あるいは自分で実装することもできます。

EDIT：私はkd-treeの実装について質問しましたhere - 有用かもしれません。

EDIT： KD-木は広く:) NN検索のために成功裏に使用されている - あなたがおおよその一致を受け入れるために喜んでいる場合も、あなたはFast Library for Approximate Nearest Neigbor (FLANN)を使用することができます。 FLANNの実装はOpenCV 2.0にあります。

おおよその回答が必要ない場合は、FLANNパラメータを調整してツリー全体を検索することができます。

Answer 2

Q（xq、yq）からの最小距離を見つけるために、距離式を使用して1点おきに繰り返します。

しかし、パフォーマンスに重大な回答を得るには十分な情報がありません。

たとえば、QがVERY共通点である場合、Qまでの距離を計算して各点に保存したい場合があります。

第二の例、あなたがポイントの膨大な数を持っている場合は、セクションにポイントを整理するかもしれないとStephan202が指摘したようQ.

Answer 3

クエリポイント（xq、yq）が変化してリストにない場合は、ポイントリストのVoronoi diagramを計算する必要があります。これはあなたにポリゴンまたは "セル"のセットを与えます（そのうちのいくつかは無限です）。各ポリゴンは、そのセルの「サイト」と呼ばれる元のリストからのポイントに対応します。 1つのポリゴンの内側にあるポイントは、元のリストの他のサイトと比べて、そのポリゴンのサイトに近くなります。 2つのポリゴン間の境界上の任意の点は、各サイトから等しく離れています。

これまでのところ、どのポリゴンを使用しているのかを簡単に把握する必要があります。これはpoint location problemとして知られています。

この種のもののための本当に、本当に良い本はComputational Geometry: Algorithms and Applicationsです。彼らは、ボロノイ図の計算とポイント位置の台形スラブ法の両方を詳細に議論します。

自分でコードを実行したくない場合は、のようなライブラリをCGALのようにして、ほとんどの作業を行います。これはおそらくKDツリーの回答にも当てはまりますが、特に分かりません。

Answer 4

spatial indexが必要です。

自分でロールする場合は、R-TreeまたはQuad-treeアルゴリズムを選択するよりもかなり悪いことがあります。

Answer 5

私はクアッドツリーに行きます。これは最も単純な空間構造です。 2次元では、kd-treeではなくquadtreeをお勧めします。なぜなら、より簡単で高速なのでです。次元の数が多い場合、その欠点はより多くのメモリ消費ですが、2次元の場合、その違いは重要ではありません。

座標が浮動小数点型の場合は、最適化のトリックがあります。 クエリでは、最も近い点が求められるポイントを含むリーフノードを最初に見つけなければなりません。これを行うには、ルートからリーフまでツリー内を移動する必要があります。各反復で、どの子ノードをステップするかを決定します。 子ノードの識別子/アドレスをノード構造の4サイズの配列に格納します。クエリアルゴリズムのポイント座標を数値化します。次に、デジタル化されたポイント座標の2つの適切なビットで配列をインデックスするだけで、適切なサブノードを見つけることができます。デジタイズは高速です：単純なstatic_castで実装します。

しかし、ビット操作でバグを作るのは簡単だから、まずクワッドツリーを最適化せずに実装してください。この最適化がなくても、それはいまだ最速のソリューションになります。