查找距離最近的GPS座標（最鄰近搜索）

我有緯度和經度的元組數據框如下（實際座標的樣品）：查找距離最近的GPS座標（最鄰近搜索）

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和距離在同一個數據幀最近latlon（爲了說明，我只是在nearest_id和nearest_dist列組成的數字如下圖）：

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

我有座標的大量（45K +）上，我想PE執行此操作。

下面是我下面的嘗試性解決方案，使用great_circle從geopy.distances：

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']

什麼可以做，以有效地使這個計算？

來源

2017-08-28 Joseph Dasenbrock

空間索引應該有幫助。

您可以使用數據庫實現空間索引（例如PostgreSQL with PosGIS擴展），但您也可以使用內存中的解決方案。

查看Rtree庫。您需要創建索引，將所有點添加到索引，然後使用nearest方法查詢索引。

來源

2017-08-29 15:00:34 daphshez

您可以高效地使用PostGIS/PostgreSQL來做到這一點，但是您必須將數據存入一個可能很困難的sql表中。你可以從python發出postgresql命令，但你仍然需要設置後端。希望有人能夠給你提示如何使用這個只是使用python。

來源

2017-08-28 23:50:00 Bootstrap

'scipy.spatial'有很多有用的（和極快的）空間搜索算法。似乎是你的問題的正確工具之一是'cKDTree'。

tree = cKDTree(data)

數據應形狀的numpy的數組n * 2（它可以計算在n個維空間中的距離，但在這種情況下，我們有兩個維度）

然後可以查詢樹的k個最近鄰居：

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

使用索引，它應該是微不足道的獲得id。我回答了類似的問題here。同時查看關於投影的信息。

來源

2017-08-30 00:15:10

在這裏使用'cKDTree'是否假設輸入是笛卡爾座標？ –

@JosephDasenbrock是的。您可以使用'pyproj'將投影座標從lon/lat投影到UTM（或任何其他適用於測量的投影），或者使用大圓或甚至更好的半投影公式作爲用scipy.spatial.distance的自定義距離度量。你選擇的算法>。第二種方法在[相同問題]的另一個解決方案中進行了解釋（https://stackoverflow.com/a/45807448/6517541） –

cKDTree是100％準確的還是它是一個搜索算法，它將速度優先於完整的準確度？ –

查找距離最近的GPS座標（最鄰近搜索）

回答

相關問題