什么是在2D空间中确定点p最近的点q（最小欧几里得距离）的最快方法？请参见附图。
我目前在Python中使用的方法是将所有距离存储在列表中，然后运行
numpy.argmin(list_of_distances)
当计算m个点p时，这种方法可能会有些慢。不过，它真的会这样吗？
3个回答
5
你可以计算平方距离而不是直接计算距离。这样就不需要进行 n * m 次平方根运算了。
- Jackson Pope
1
老游戏程序员的秘诀 :) - Jackson Pope
4
这属于最近点查询问题。
预计会有多少个点？您的点是静态的还是会改变？对于静态点来说，一个天真但强大的方法是预先计算每个已知距离，这将导致O(1)的查找。
预计会有多少个点？您的点是静态的还是会改变？对于静态点来说，一个天真但强大的方法是预先计算每个已知距离，这将导致O(1)的查找。
- randomguy
1
啊，谢谢。n通常只有大约10个，但m可以在数千个范围内变化。然而，q i的分布可能会随着每次迭代而改变。“预先计算每个已知距离”，这适用于浮点数吗？ - Theodor
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)
- eumiro
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接