在路网坐标列表中查找距离给定点最近的点

Question

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

Answer 1

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

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])

输出：

^{pr2}$

以上是你第二个建议的解决方案。你的第三个听起来绝对是一个更好的计算解决方案。然而，我认为我的解决方案将满足所需的问题。如果不行的话，我会尝试发布第三个.tnx的解决方案！在

Answer 2

1. 如果您的数据是无序的，那么您就没有其他选择，然后检查数组的每个点。

2. 如果您的数据是按升序/降序排列的（例如按坐标），则可以基于此进行搜索。例如，注释中建议的二进制搜索。

3. 如果你能在你的网络中找到一个接近你当前网络位置的指针，你就可以找到一个接近你当前网络位置的指针。

编辑：还有一点：如果你需要比较距离来确定最接近的距离（可能用毕达哥拉斯来计算欧几里得距离），如果你不需要计算根，你也可以直接比较二次距离，这样可以节省一些运算（如果你经常这样做的话，可以很快地求和）