计算二维空间中的欧几里得距离的最快方法

Question

什么是fastes方法来确定在二维空间中n个点中的哪一点是距离点p最近的（最小的欧几里德距离），参见附加的行李。

计算本作点P的m个时我目前在Python中，这是存储在一个列表中的所有距离，然后运行

numpy.argmin(list_of_distances) 

这种方法是但有点慢。或者是？

Answer 1

这属于closest point query-问题。

预计有多少点？你的观点是静态的还是改变了？对于静态点来说，一种天真但强大的方法是预先计算每个已知距离，这将导致O（1）查找。

Answer 2

除了计算距离外，还可以计算平方距离。这样你就不需要执行n * m平方根。

Answer 3

尽可能将所有东西放入numpy并在那里进行计算。如果你有很多点，它比计算列表中的距离要快得多：

import numpy as np 

px, py 
x = np.fromiter(point.x for point in points, dtype = np.float) 
y = np.fromiter(point.y for point in points, dtype = np.float) 

i_closest = np.argmin((x - px) ** 2 + (y - py) ** 2)