在道路网络坐标列表中找到与给定点最近的点

Question

使用 Python，所以我的实际问题是计算从数组（数千个点）中找到最近的 2D 点，该数组表示到给定点（汽车位置）的道路网络坐标。此计算需要每次 0.2 秒的时间戳（在线）。在检查 closest pair of point problem algorithm 时，它会找到某个数组中的最近点，而不是我愿意找到的关于给定点的最近点。有没有人熟悉 python 实现或合适的算法？欢迎任何帮助。

Answer 1

如果您的数据是无序的，除了检查数组的每个点之外，您别无选择。
如果您的数据已排序 ascending/descending（例如按坐标），您可以以此为基础进行搜索。例如，评论中建议的二进制搜索。
如果您的数据代表道路网络并且数据结构类似于该网络的真实二维拓扑，您可以利用这一点并将 "pointer" 保持在您当前的位置并且只需探索该位置附近的环境，然后在当前位置附近的某处找到您的点。

编辑：还有一点：如果您需要比较距离以确定最近的距离（可能使用毕达哥拉斯来计算欧氏距离），如果不需要，请不要计算根，您也可以只比较二次距离这将节省一些操作（如果你经常这样做，可以很快总结）

Answer 2

谢谢大家 - 以下是我的解决方案（句法之一）：

import numpy as np
from sklearn.neighbors import KDTree

np.random.seed(0)
samples = np.random.uniform(low=0, high=500, size=(1000000, 2))
samples.sort(kind='quicksort')
tree = KDTree(samples)
car_location = np.array([[200, 300]])
closest_dist, closest_id = tree.query(car_location, k=1)  # closest point with respect to the car location
print(samples)
print("The car location is: ", car_location)
print("The closest distance is: ", closest_dist)
print("The closest point is: ", samples[closest_id])

输出：

[[ 274.40675196  357.59468319]
 [ 272.4415915   301.38168804]
 [ 211.82739967  322.94705653]
 ..., 
 [ 276.40594173  372.59594432]
 [ 464.17928848  469.82174863]
 [ 245.93513736  445.84696018]]
The car location is:  [[200 300]]
The closest distance is:  [[ 0.31470178]]
The closest point is:  [[[ 199.72906435  299.8399029 ]]]

ChrisN - 以上是针对您的第二个建议的解决方案。你的第三个听起来绝对是一个更好的计算解决方案。但是，我认为我的解决方案将满足所需的问题。如果不行，我会尝试 post 解决第 3 次的问题。谢谢！

在道路网络坐标列表中找到与给定点最近的点

Find the closest point on a road network coordinates list to a given point

python

closest-points