使用搜索算法 (python) 到给定点的最近路线坐标

Question

我有以 lat/long 坐标形式表示的路线。根据路线的长度，它可能有 100 个甚至 800 个坐标。然后我又得到了一个特定的坐标 lat/lon 代表我的位置。我想做的是在到我所在位置的路线上找到最近的点（坐标）。我可以用 haversine 公式来计算路线中每个点到我的位置的距离并取最小值，但这可能会花费太长时间，因为有些路线真的很长并且有很多点要比较。是否有搜索算法可以帮助解决这个问题？我对黄金分割搜索进行了研究，但不确定这是否是我要找的。

Answer 1

我可以想到两种方法来解决这个问题。一种是为每条路线创建一个 K-D 树，并在每棵树中查询您的新坐标点以搜索最近的点。检查 sci-kit KDTree

另一种更简单的可能性是将每条路线创建为一个数组，在您的点和每个数组之间使用一些度量并找到度量最小的那个，例如使用 Euclidean distance

import numpy as np
from sklearn.metrics import euclidean_distances

x = np.array([[0.1, 0.5]])
route = np.random.rand((10,2))

array([[0.78275588, 0.92844543],
       [0.30066744, 0.21161873],
       [0.95533462, 0.11647814],
       [0.37786273, 0.58306683],
       [0.86670199, 0.90861542],
       [0.68658895, 0.60087646],
       [0.19966574, 0.57160265],
       [0.34182302, 0.02809684],
       [0.08862117, 0.89459785],
       [0.18083728, 0.39331416]])

dist = euclidean_distances(x,route)

array([[0.80605278, 0.35132774, 0.9373827 , 0.29001344, 0.8687914 ,
        0.59519968, 0.12272001, 0.53025557, 0.39476188, 0.13385266]])

然后如果我们得到argmin，你可以看到最近的点是第6个元素

np.argmin(euclidean_distances(x,route))
6

使用搜索算法 (python) 到给定点的最近路线坐标

Nearest coordinate of a route to a given point using search algorithm (python)

python

search

coordinates

haversine