セット内にかなり大きな 2D ポイント (~20000) のセットがあり、xy 平面の各ポイントについて、セットのどのポイントが最も近いかを判断したいと考えています。(実際には、ポイントはさまざまなタイプであり、どのタイプが最も近いかを知りたいだけです。xy 平面はビットマップで、たとえば 640x480 です。)
この回答から、「 2D、C++ のすべての k 個の最近傍」という質問に対して、グリッドを作成するというアイデアが浮かびました。n*m の C++ ベクトルを作成し、どのビンに該当するかに応じてポイントをベクトルに配置しました。アイデアは、すべてのポイントではなく、ビン内のポイントの距離を確認するだけでよいということです。ビンにポイントがない場合は、隣接するビンをらせん状に続行します。
残念ながら、その後、Oli Charlesworth のコメントしか読んでいません。
残念ながら、隣接しているだけではありません (たとえば、東に 2 番目のセル内のポイントが、北東に直接あるセル内のポイントよりも近い可能性があると考えてください。この問題は、高次元ではさらに悪化します)。また、隣接するセルのポイントが 10 未満の場合はどうなるでしょうか。実際には、「スパイラルアウト」する必要があります。
幸いなことに、私はすでにスパイラル コードを把握していました ( C++ の優れたバージョンがここにあり、同じ質問に他のバージョンがあります)。しかし、私はまだ問題を抱えています：
セルでヒットを見つけた場合、隣接するセルでより近いヒットがある可能性があります (黄色は私のプローブ、赤は間違った選択、緑は実際の最も近いポイント):
Oli Charlesworth が述べたように、隣接するセルにヒットが見つかった場合、2 歩離れたセルにヒットがある可能性があります。
しかし、さらに悪いことに、2 歩離れたセルでヒットを見つけた場合でも、3 歩離れたセルでより近いヒットが発生する可能性があります。つまり、dx、dy= -3...3、または 49 個のセルを持つすべてのセルを考慮する必要があります。
実際には、セルが十分に満たされるようにビンのサイズを選択できるため、これは頻繁には発生しません。それでも、すべてのポイントを反復せずに、正しい結果を得たいと思っています。
では、「スパイラル」または検索をいつ停止するかをどのように判断すればよいでしょうか? 複数のグリッドを重ねるアプローチがあると聞きましたが、よくわかりませんでした。このグリッド技術を救済することは可能ですか?