给定任何经纬度坐标，如何最快地找到列表上最接近的坐标？

Question

我有这样的表格：

import pandas as pd
import numpy as np


df1 = pd.DataFrame([
    ['A', (37.55, 126.97)],
    ['B', (37.56, 126.97)],
    ['C', (37.57, 126.98)]
], columns=['STA_NM', 'COORD'])

df2 = pd.DataFrame([
    ['A-01', (37.57, 126.99)]
], columns=['ID', 'COORD'])

我尝试从df2中挑选每个坐标，并找到距离df1中每个坐标最近的两个站点（STA_NM），然后将它们及其与每个坐标的距离添加到df2的一个新列中。我尝试了以下代码：

from heapq import nsmallest
from math import cos, asin, sqrt


def dist(x, y):
    p = 0.017453292519943295
    a = 0.5 - cos((y[0] - x[0]) * p) / 2 + cos(x[0] * p) * cos(y[0] * p) * (1 - cos((y[1] - x[1]) * p)) / 2
    return 12741 * asin(sqrt(a))

def shortest(df, v):
    l_sta = []
    
    # get a list of coords
    l_coord = df['COORD'].tolist()
    
    # get the two nearest coordinates
    near_coord = nsmallest(2, l_coord, key=lambda p: dist(v, p))

    # find station names
    l_sta.append((df.loc[df['COORD'] == near_coord[0], 'STA_NM'].to_string(index=False), round(dist(near_coord[0], v) * 1000)))
    l_sta.append((df.loc[df['COORD'] == near_coord[1], 'STA_NM'].to_string(index=False), round(dist(near_coord[1], v) * 1000)))
    
    # e.g.: [('A', 700), ('B', 1000)]
    return l_sta

df2['NEAR_STA'] = df2['COORD'].map(lambda x: shortest(df1, x))

原始数据中，df1大约有700行，df2大约有55000行。当我尝试上述代码时，执行时间接近两分钟。有没有更好的方法让它运行更快？

- vuvugelato

---

“最快的方式”可能要高级得多，但这个问题至少已经在三维点方面得到了解决: https://dev59.com/pG855IYBdhLWcg3wbjrO - Andrew Allaire

我相信在这种情况下，SciPy有scipy.spatial.KDTree。 - Aaron Keesing

还要注意到有一个可能会有帮助的 RTree，但我不确定：https://pypi.org/project/Rtree/ - Andrew Allaire

Answer 1

在进行距离计算之前，您可以将纬度/经度坐标转换为地心固定坐标系（即从地球核心开始的x/y/z），这样会使您的dist函数更快，因为它将变成单个欧几里得距离计算。

您还可以放弃dataframe / lambda方法，改用cython或numba来显着加速此过程。

如果您知道站点的空间分布情况，则还有加速的机会。例如，如果它们位于规则网格上，则只需查看四个相邻站点。如果您知道通常至少有2个站点在某个距离内，则只需要在该半径内搜索。如果没有这样的先验信息，则很抱歉没有什么技巧可言。

- Graham S