データ配列内の指定されたポイントに最も近いポイントを見つける最も速い方法は何ですか?
たとえば、A
3D ポイントの配列 (通常どおり、座標 x、y、z) とポイント (x_p、y_p、z_p) があるとします。A
(x_p、y_p、z_p) に最も近いポイントを見つけるにはどうすればよいでしょうか。
私の知る限り、最も遅い方法は線形探索を使用することです。もっと良い解決策はありますか?
任意の補助データ構造を追加できます。
ベストアンサー1
ポイントを整理するにはオクトリーそうすれば、小さなサブセットのみを検索すれば済みます。
Octree は、自分で実装できる非常にシンプルなデータ構造です (貴重な学習体験になります)。また、役立つライブラリを見つけて、それを活用することもできます。