C++での補間座標のソートと検索

Question

最近隣の補間プログラムを作成する必要があります。私の入力は、x、点のY座標とy座標であろう

、例えばX = 0.5の場合、yは0.3を=、Z = 0.1

出力は、最も近い時点で測定された速度であろう利用可能です。私は4つのベクトルx、y、z、Vを持つので、プログラムは最も近いノードを探し、x[5239], y[5239], z[5239]（x = .501 y = .299 z = .1に相当）と出力し、V[5239]と出力します。

私はいくつかの参照点を設定することを考えていました（pとqと呼ぶ）。そして、私の考えはpとqに対するすべてのノードの距離を計算することです。次にノードのpとqまでの距離に応じてベクトルを並べ替えます（V[i]を見つけるためには元のインデックスの参照を保持する必要があります）。その後、私はバイナリ検索を使うことができ、pとqに関して与えられた点の距離を使って、最も近いノードを見つけることができます。

私が見つけたもう一つの物は、ハッシュテーブルです。ベクトルの要素の数が〜96,000で、実行する必要がある補間の回数がそれほど多くなる場合は、どれが効率的になるでしょうか。

私はどのようにインデックス（matlabのソート機能のような）に目を向けるつもりです。この場合、どのようなソートアルゴリズムをお勧めしますか？

は

Answer 1

Nearest neighbor searchは、標準的な問題です、ありがとうございました。あなたはおそらくcover treeを探しています。 Wikipediaの記事自体は非常に詳細ではありませんが、元の論文とGitHubの実装にリンクしています。