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

Question

在二维空间中，如何最快地找出n个点中哪个点q离点p最近（也就是距离最小），见附图。

我现在在Python中做这个的方式是把所有的距离存到一个列表里，然后运行

numpy.argmin(list_of_distances)

不过，当我需要对m个点p进行计算时，这个方法有点慢。或者说，真的是这样吗？

Answer 1

尽快把所有数据放到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)

Answer 2

与其计算实际的距离，不如计算距离的平方。这样你就不需要进行 n * m 次开平方运算了。

Answer 3

这属于一种叫做最近点查询的问题。

你预计会有多少个点？这些点是固定不变的，还是会变化？对于固定的点，有一种简单但有效的方法就是提前计算好所有已知的距离，这样查找的时候就可以在O(1)的时间内完成。