点のk番目の最も近い隣人のための空間クエリ

Question

私は点のベクトルから取られた特定のクエリ点からk番目の最も近い点まで（ユークリッド距離）を繰り返し必要とするアルゴリズムに取り組んでいます。また、ある点の半径内のすべての点を繰り返し見つける必要があります。

私はnanoflannライブラリのk-dツリーを使用することを考えています。しかし、knnSearch（）関数は、必要としないすべてのk最近傍を返します。 （radiusSearch（）関数は私にはうまく合っていますが）。

いつでもすべてのk個の最も近いネイバーをスローする以外に、必要なものを得るためのより効率的な方法がありますか？より良いデータ構造またはより良い実装？ （私はC++を使用しています。）

Answer 1

を私は

2Dまたは3Dのための優れた選択肢を、K-dの木を使用したと思っています。

低次元データ（ナノフランは「2Dまたは3D点群に最適化されています。」）からk-dツリーが適しています。

いつでもすべてのk個の最も近いネイバーをスローする以外に、必要なものを得るためのより効率的な方法がありますか？ダウン下降する必要があります最初のNNを（発見されたk個のNN、（時間的に）高価な操作のためのkd木を検索するとき

あなたは、k番目の最近傍（NN）が必要ですが、木、根元から葉まで）。

第2、第3、または他のインデックス付きNNを見つけることは比較的安価であり、性能に悪影響を及ぼすことは非常に疑問です（つまり、ツリーから返されたkNNからk番目のNNを得ることはボトルネックになります）。

ですから、そのステップについて心配しないことを強くお勧めします。

データ構造が優れているか、実装が優れていますか？

私はそうは思わない。私はnanoflannを使用していませんが、この種の問い合わせにはCGALを使用しましたが、試してみる価値があります（ただし、CGALはインストールする必要があります）。