6

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

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

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

ジェイコブありがとう。KDツリーのデータ構造が答えになるのに適しているようです（そして、そうだと思います。関連する結果が得られたら更新します）。

編集2：この問題は「最近傍」と呼ばれていることがわかりました。

編集3：最初のタイトルは「アルゴリズムを求めて（空間クエリと空間インデックス用）（最近傍）」でした。新しいタイトルを選択しました：「ベストパフォーマンス-最近傍を解くための重要なアルゴリズム」。初期データに対して挿入および削除操作を実行したくなく、それらから新しいポイント（挿入されない）に最も近いデータだけが必要なため、（現在）KDツリーで作業することにしました。ありがとうございます！

4

5 に答える 5

10

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

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

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

編集: KD ツリーは、NN 検索に広く使用されています :) - また、おおよその一致を受け入れたい場合は、Fast Library forapproximate Nearest Neigbor (FLANN) を使用できます。FLANN 実装はOpenCV 2.0に含まれています。

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

于 2009-10-28T20:22:55.480 に答える
7

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

そこまで到達したら、どのポリゴンにいるのかを簡単に把握する方法が必要です。これは、ポイント位置問題として知られています。

この種のことについて本当に本当に良い本はComputational Geometry: Algorithms and Applicationsです。彼らは、ボロノイ線図の計算と点位置の台形スラブ法の両方について詳しく説明しています。

自分でコードを作成したくない場合や、そうすべきでない場合は、ほとんどの作業を自動的に実行してくれるCGALなどのライブラリを入手してみてください。これはおそらくKDツリーの回答にも当てはまりますが、具体的にはわかりません。

于 2009-10-28T20:29:00.117 に答える
5

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

独自のロールを作成すると、 R-TreeまたはQuad-treeアルゴリズムを選択するよりもはるかに悪い結果になる可能性があります。

于 2009-10-28T20:42:29.653 に答える
1

私は四分木で行きます。最も単純な空間構造です。2次元では、kd-treeの代わりにquadtreeをお勧めします。これは、よりシンプルで高速であるためです。次元数が多いとメモリ消費量が増えるという欠点がありますが、2 次元の場合はそれほど大きな違いはありません。

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

ただし、ビット操作でバグが発生しやすいため、最初に最適化せずに四分木を実装します。この最適化がなくても、最速のソリューションになります。

于 2009-10-31T00:41:25.813 に答える
0

Q (xq,yq) からの最小距離を見つけるために、距離の式を使用して 1 つおきのポイントを反復処理します。

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

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

2 番目の例として、膨大な数のポイントがある場合、ポイントをセクションに編成し、同じセクションおよび Q を含むセクションに隣接するセクション内のポイントのみから開始することができます。

于 2009-10-28T20:10:28.480 に答える