最近傍を解決するための最高のパフォーマンスクリティカルアルゴリズム

Question

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

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

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

ありがとう、ヤコブ。 KD-Treeのデータ構造は、答えになる良い候補のようです（そして、私はそう感じます。関連する結果が得られたら更新します）。

編集2：この問題は「最近接」と名付けられました！

編集3：最初のタイトルは「In Search of a Algorithm（Spatial-Querying and Spatial-Indexing）（Nearest Neighbor）」でした。私は新しいタイトルを選びました：「最も近い近隣を解くための最高のパフォーマンスクリティカルアルゴリズム」。私は初期データに対して挿入および削除操作を実行したくなく、それらから最も近いものだけを（挿入されない）新しいポイントにしたいので、（現在）KDツリーで作業することを選択しました。すべてに感謝します！

Answer 1

Stephan202が指摘したように、複数のポイントで最も近い一致を見つける場合は、ツリーを使用する必要があります。

OpenCV 2.0のようないくつかのパッケージで簡単に実装できるKDツリーをお勧めします。または、自分で実装することもできます！

編集： kd-treeの実装について質問したこちら-役に立つかもしれません。

編集： KDツリーはNN検索で広く使用されています:)-また、おおよその一致を受け入れる場合は、近似最近傍（FLANN）の高速ライブラリ。 FLANNの実装は、 OpenCV 2.0 にあります。

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

Answer 2

クエリポイント（xq、yq）が変化し、リストが変化しない場合、を計算する必要がありますポイントのリストのボロノイ図 。これにより、一連のポリゴンまたは「セル」が得られます。 （そのうちのいくつかは無限です）;各ポリゴンは、「サイト」と呼ばれる元のリストのポイントに対応しています。その細胞の。 1つのポリゴンの完全に内側にあるポイントは、元のリストの他のサイトよりもそのポリゴンのサイトに近くなります。 2つのポリゴンの境界上の任意のポイントは、各サイトから等しく離れています。

ここまで進んだら、どのポリゴンにいるかを簡単に把握する方法が必要です。これは ポイントロケーションの問題 。

この種の非常に優れた本は、計算幾何学：アルゴリズムとアプリケーションです。 。彼らは、ボロノイ図の計算と台形のスラブ法の両方でポイント位置を詳しく説明します。

自分でコードを実行したくない場合、実行したくない場合は、 CGAL を使用すると、ほとんどの作業が自動的に行われます。これはおそらくKDツリーの回答にも当てはまりますが、具体的にはわかりません。

Answer 3

空間インデックスが必要です。

自分でロールバックする場合は、 Rツリーを選択するよりもはるかに悪いことができますまたはクアッドツリーアルゴリズム。

Answer 4

私は四分木に行きます。最も単純な空間構造です。 2次元では、kd-treeではなくquadtreeをお勧めします。これは、より簡単で高速だからです。欠点は、次元の数が多い場合により多くのメモリが消費されることですが、2次元の場合、その差は大きくありません。

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

しかし、ビット操作でバグを作りやすいため、最初に最適化なしでクアッドツリーを実装します。この最適化がなくても、最速のソリューションになります。

Answer 5

距離の式を使用して他のすべてのポイントを反復処理し、Q（xq、yq）からの最小距離を見つけます。

ただし、パフォーマンスが重要な答えを得るには十分な情報が提供されていません。

たとえば、Qが非常に一般的なポイントである場合、Qまでの距離を計算し、各ポイントに保存することができます。

2番目の例では、膨大な数のポイントがある場合、ポイントをセクションに整理し、同じセクションのポイントとQを含むセクションに隣接するセクションのみでポイントを開始できます。