c++ - グラフィックス ハードウェアでの最近傍検索

Question

2 次元空間でポイント (float64) の膨大なコレクションが与えられた場合...

OpenGL または DirectX の機能を使用して最近傍を特定する方法はありますか?

kd-tree を実装しましたが、まだ十分に高速ではありません。

Answer 1

kd-treeは問題なく動作するはずです。しかし、ここにいくつかのヒントがあります。

100 万点のデータ セットに対して 1 回の kd ツリーを 1 回実装しました。そこから学んだことは次のとおりです。

コードのプロファイリングを試みましたか? 一般的なヘルパー関数を強制的にインラインにする必要があるなど、簡単に最適化できる場合があります。

コードを実際にテストして、「遠すぎる」と簡単に識別されるパーティションのツリー ブランチを選別していることを検証しましたか。注意しないと、あまりにも離れたポイントで不必要な距離計算を行うバグが簡単に発生する可能性があります。

最も簡単なこと: ポイント間の直線距離を比較する場合、(x2-x1)*(y2-y1) の SQRT を取得する必要はありません。

私のコードで費やされた時間のほとんどは、元のデータ セットからツリーを構築することだけでした。これには、分割するのに最適な軸を決定する各反復での複数の完全な並べ替えが含まれます。より簡単なアルゴリズムは、ツリー ブランチごとに x 軸と y 軸でパーティション分割を交互に行い、各軸の並べ替え順序をキャッシュすることです。最適な検索ツリーが構築されない可能性がありますが、全体的な節約は非常に大きくなる可能性があります。