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

Question

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

Answer 1

1. 如果您的数据是无序的，那么除了检查数组的每个点之外，您将别无选择。

2. 如果您的数据按升序/降序排列（例如按坐标），您可以以此为基础进行搜索。例如，评论中建议的二进制搜索。

3. 如果您的数据代表道路网络并且数据结构类似于该网络的真实二维拓扑，您可以利用它并保持指向您当前位置的“指针”，然后探索该位置的附近环境并找到您的点当前位置附近的某处。

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

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 - 以上是您的第二个建议的解决方案。你的第三个听起来绝对是一个更好的计算解决方案。但是，我认为我的解决方案将满足所需的问题。如果不是，我会尝试发布第三个解决方案。天呐！