查找到最近的 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 和最近的 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+) 个坐标上执行此操作。

下面是我尝试的解决方案，使用 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

您可以使用 PostGIS/PostgreSQL 高效地执行此操作，但随后您必须将数据放入 sql table 中，这可能很困难。您可以从 python 发出 postgresql 命令，但您仍然需要设置后端。希望有人能够通过 python.

为您提供有关如何使用它的提示

Answer 2

空间索引应该有所帮助。

您可以使用数据库（例如带有 PosGIS 扩展的 Postgres）实现空间索引，但您也可以使用内存解决方案。

看看 Rtree 库。您将需要创建一个索引，将您所有的点添加到索引中，然后使用 nearest 方法查询索引。

Answer 3

'scipy.spatial' 有很多有用的（而且速度极快的）空间搜索算法。 'cKDTree' 似乎是解决您的问题的正确工具。

tree = cKDTree(data)

数据应该是一个形状为 n*2 的 numpy 数组（它可以计算 n 维的距离 space，但在本例中我们有两个维度）

然后您可以查询树的 k 个最近邻居：

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

使用索引，获取id应该是微不足道的。我回答了一个类似的问题。另请查看有关投影信息的评论。

查找到最近的 GPS 坐标的距离（最近的邻居搜索）

Find Distance to Nearest GPS Coordinates (Nearest Neighbors Search)

python

pandas

gis

geopandas