私は（実際の座標のサンプル）を以下のように緯度と経度の組とのデータフレームを持って最寄りのGPS座標（最近傍探索）

Question

に距離を探す：

id latlon    
67 79 (39.1791764701497, -96.5772313693982) 
68 17 (39.1765194942359, -96.5677757455844) 
69 76 (39.1751440428827, -96.5772939901891) 
70 58 (39.175359525189, -96.5691986655256) 
71 50 (39.1770962912298, -96.5668107589661) 

私はidとの距離を見つけたいです私はPEにしたい座標の数が多い（45K +）を持っている

id latlon         nearest_id nearest_dist 
67 79 (39.1791764701497, -96.5772313693982) 17   37   
68 17 (39.1765194942359, -96.5677757455844) 58   150   
69 76 (39.1751440428827, -96.5772939901891) 50   900   
70 58 (39.175359525189, -96.5691986655256) 17   12   
71 50 (39.1770962912298, -96.5668107589661) 79   4  

：同じデータフレーム（説明のために、私はちょうどnearest_idで下記の番号を構成するとnearest_dist列てる）で最寄りlatlonこの操作を実行します。ここで

はgeopy.distancesからgreat_circleを使用して、以下の私の未遂ソリューションです：

def great_circle_dist(latlon1, latlon2): 
    """Uses geopy to calculate distance between coordinates""" 
    return great_circle(latlon1, latlon2).meters 

def find_nearest(x): 
     """Finds nearest neighbor """ 
     df['distances'] = df.latlon.apply(great_circle_dist, args=(x,)) 
     df_sort = df.sort_values(by='distances') 
     return (df_sort.values[1][0], df_sort.values[1][2]) 

df['nearest'] = df['latlon'].apply(find_nearest) 
df['nearest_id'] = df.nearest.apply(lambda x: x[0]) 
df['nearest_dist'] = df.nearest.apply(lambda x: x[1]) 
del df['nearest'] 
del df['distances'] 

効率的にこの計算をするために何ができますか？

Answer 1

空間索引付けが役立ちます。

データベース（例：PosGIS拡張機能付きのPostgres）を使用して空間インデックスを作成できますが、インメモリソリューションを使用することもできます。

Rtreeライブラリをご覧ください。インデックスを作成し、すべてのポイントをインデックスに追加してからnearestメソッドを使用してインデックスをクエリする必要があります。

Answer 2

これはPostGIS/PostgreSQLで効率的に行うことができますが、難しいかもしれないSQLテーブルにデータを入れなければなりません。 pythonからpostgresqlコマンドを発行することはできますが、依然としてバックエンドを設定する必要があります。うまくいけば、誰かがあなたにちょうどpythonを使ってこれを使う方法に関するヒントを与えることができるだろう。

Answer 3

'scipy.spatial'には、空間検索に役立つ（非常に高速な）アルゴリズムが多数あります。あなたの問題の正しいツールであると思われるものは 'cKDTree'です。

tree = cKDTree(data) 

データは

（これは、n次元空間内での距離を計算することができるが、この場合には、我々は2次元を持っている）numpyの形状の配列のn * 2する必要があります次に、あなたが最も近いk個のツリーを照会することができます隣人：

dist, idx = tree.query(x, k=1) 

インデックスを使用すると、idを取得するのは簡単です。私は同様の質問hereに答えました。また、投影に関する情報については、コメントをチェックしてください。