データセットの各点について、最も近いすべての点を見つける必要があります。データセットには約が含まれています。1000 万の 2D ポイント。データはグリッドに近いですが、正確なグリッドを形成していません...
このオプションは、(私の意見では) KD ツリーの使用を除外します。基本的な前提は、同じ x 座標と y 座標を持つポイントがないことです。
この問題を解決するには、O（n）以上の高速アルゴリズムが必要です（ただし、実装にはそれほど難しくありません:-)））...ブーストは標準化されていないため、使用したくありません...
回答またはコードサンプルをありがとう...
私は次のことをします：
ポイントの上に大きなグリッドを作成します。
ポイントを直線的に調べ、それらのそれぞれについて、それが属する大きな「セル」を見つけます（そして、そのセルに関連付けられたリストにポイントを追加します）。
(これは、ポイントごとに一定の時間で実行できます。ポイントの座標の整数除算を実行するだけです。)
次に、ポイントを再び直線的に通過します。10 個の最近傍を見つけるには、隣接する大きなセル内のポイントを確認するだけで済みます。
ポイントはかなり均等に分散しているため、各 (大きな) セルのポイント数に比例して時間内にこれを行うことができます。
状況を説明する（醜い）写真は次のとおりです。
セルは、(中心) と隣接するセルが最も近い 10 個のポイントを含むのに十分な大きさである必要がありますが、計算を高速化するには十分に小さくなければなりません。同じバケット内で最も近いポイントを見つける「ハッシュ関数」として見ることができます。
(厳密に言えばO(n)ではありませんが、より大きなセルのサイズを微調整することで、十分に近づく必要があることに注意してください。:-)
私はANN (Approximate Nearest Neighbour) と呼ばれるライブラリを使用して大きな成功を収めました。試行するアルゴリズムは複数ありましたが、Kd ツリー アプローチを使用します。三角面上の点の位置に使用しました。あなたはそれでいくつかの運があるかもしれません。最小限で、ソースをドロップするだけでライブラリに簡単に含めることができました。
この興味深いタスクで頑張ってください！