查找距离最近的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坐标（最邻近搜索）

回答

相关问题