xy 範囲内のポイントの高速検索を容易にする、不規則な標高データ {xi,yi,zi} を格納するデータ構造を探しています。
私が集めたものから、kdツリーはこれに適しているはずですか? また、実装もかなり簡単ですか？
ただし、標高データセット内のポイントの数は膨大になる場合があります。したがって、一度にすべてのポイントを処理できない場合があります。代わりに、xy 領域をタイルに分割し、各タイルを個別に処理することを目指しています。
緑の四角形内のポイントは、タイル 1 に必要なポイントです。タイル 2 に移動すると、タイル 2 を中心とする緑の四角形内のポイントが必要になります。タイル 1 の周りの緑の四角形の右端の 2 点は、引き続き必要です。他のポイントは、必要に応じてメモリからスワップできます。さらに、タイル 2 にはさらに 4 ポイントが必要になります。新しいタイルごとに完全なツリーを再構築する必要があるため、kd ツリーは最適ではない可能性があります。Rツリーの方が良い選択でしょうか?
ポイント自体は、何らかの巧妙な形式でディスクに保存し、必要になる直前にメモリに読み込む必要があります。タイル 1 の処理を開始する前に、ポイントを維持するデータ構造に、次にタイル 2 が必要になることを伝えることができ、別のスレッドでディスクから必要なポイントを読み取り始めることができます。
ポイントをデータ構造にロードするために小さなタイルを使用することを検討していました。たとえば、図の点は 16x16 のタイルに分割できます。
この機能を実装する C/C++ のライブラリはありますか?