緯度経度座標の束を含む csv ファイルがあります。また、特定の人が立っている位置の束を含む csv ファイルもあります。2 番目のファイルの各ポイントについて、それらが最初のファイルのいずれかのポイントに近い (1 マイル未満) かどうかを調べる必要があります。各ファイルに約 500 ポイントあります。
私はJavaでこれを解決しようとしています.最初のファイルを読み込んで、簡単に検索できるある種の構造に入れるという行に沿って何かを使用すると思いました。このようにして、IO操作を続ける必要はありません. 特定のポイントの半径内にあるポイントを簡単に検索できるように、ポイントを保持する必要があるデータ構造のタイプが不明です。誰かが私を正しい方向に向けることができますか? n^2 の比較を行う必要がないように、これを整理する方法はありますか?
最も簡単な方法は、粗いグリッドを定義し、ポイントを最初のリストからグリッド セルにバケット化することです。各ポイントのセル「ID」を計算し、その ID に基づいてハッシュ テーブルに入れる必要があります。それができたら、適切なセルを見つけてそのコンテンツ (および隣接するセルのコンテンツ) を列挙することにより、特定の緯度/経度の近くのポイントを簡単に検索できます。秘訣は、緯度/経度をセル ID に変換することです。1 つの方法は、緯度/経度を切り上げることです。たとえば、(47.43402067, -121.89068567) ペアを "47_-121" 文字列に変換します。1 度は赤道で約 70 マイルであるため、これは大まかすぎる可能性があります。特定の小数点以下を四捨五入して締めることができます。たとえば、"47.43_-122.89" です。北または南に行くにつれて、セルの幅が狭くなることに注意してください。
JTS Topology Suite などのライブラリから既存の地理空間インデックスを使用することもできるため、柔軟性が大幅に向上します。
緯度と経度に基づいてポイントをkdツリーに保存したいようです。
Dある pointから一定の距離内にあるすべてのポイントが必要であることがわかっている場合、北/南の距離の単位に対応する緯度の差と、東/西のいずれかの距離の単位に対応する経度の(lat, lon)差を計算するのは簡単です。緯度または極に最も近い場所。これを使用して、ツリー内で緯度が と の間、経度が と の間のすべてのポイントに対して直交範囲検索を実行します。次に、これらのそれぞれの距離を計算し、離れているものを拒否する必要があります。d_latDd_lonDlat-d_latlat+d_latlat-d_latlat+d_latlon-d_lonlon+d_lonD(lat, lon)- しかし、ツリーがない場合ほど多くの計算を行う必要はありません (この段階に到達したポイントの約 1-pi/4 = 21.5% を拒否するだけで済みます)。
もちろん、関連する場合は、エッジケースを考慮する必要があります。
d_lonにいる場合は、ツリーで 2 つの異なる検索を行う必要があります (180 度の両側)。(lat, lon)が極の緯度内にある場合は、極から最も遠い北/d_lat南のすべてを探します。lat-d_latlat+d_lat