我正在开发一种算法和数据结构来处理大量二维点上的欧氏距离查找。
我试过在google scholar上研究这个问题，但是什么也没有发现（可能是因为我不知道这个问题在文献中通常被称为什么）。
这是我考虑过的两种方法：
方法1：
创建一个包含bucket的bidimentational网格。将点插入到桶中，保留每个点的桶的参考。
在用距离d查找p点时，得到它的bucket b和它的网格正方形的任何角（距离b）最后，枚举所有这些桶中的点并计算到p的距离。
方法2：
创建两个列表，每个列表的所有点都由一个坐标（x，y）排序。在距离为d的点p的查找中，执行二进制搜索以在列表中的每个点中查找两个点，以查找其chebyshev距离为p最后，计算所有这些点到p的欧氏距离。
不过，我想最先进的算法将远远优于这一点？对此有任何想法我们都很感激
最佳答案
一些帮助您的提示：
看看KDTree，它是一个k维树（在你的例子中是2d），这是寻找最近邻居的最好方法之一。
也许您可以从专门为处理地理空间数据而开发的Spatial Database中获益；
你可以用上面的任何一个来实现你想要的距离功能根据您的应用程序，您需要地图距离、大圆距离、恒定坡度距离、恒定方位距离等。您应该知道距离函数我经常用大圆（haversine）距离来处理google地图，比如地图和轨迹。
如果您想要一个Python实现，这里有scipy.spatial（docs）在这个模块中，函数query_ball_point((px, py), radius)似乎是您要寻找的。
希望这有帮助！