我正在开发一个算法和数据结构来处理查询通过欧氏距离在大量的2维点。

I'm developing a algorithm and data structures to handle lookup by euclidean distance on a large quantities of 2-dimentional points.

我试着研究这个在谷歌学术搜索却一无所获，但（可能是因为我不知道这是什么问题，通常被称为文献）。

I've tried researching this on google scholar but found nothing yet (probably because I don't know what this problem is usually called in the literature).

这些都是这两种方法，我认为：

These are the two approaches I've considered:

方法1： 创建bidimentional网格桶。将积分兑换成桶，保持每个点的桶的参考。 在P点与距离D的查找，获取其斗B和所有在那里任其格方的角落有（距离B）＆LT桶; D. 最后，枚举点在所有这些桶和计算距离为P。

Approach 1: Create a bidimentional grid with buckets. Insert points into buckets, keeping a reference of each point's bucket. On lookup of point P with distance D, get its bucket B and all the buckets where any of the corners of its grid-square have (distance to B) < D. Finally, enumerate the points in all those buckets and calculate distance to P.

方法二： 创建两个列表，每一个与所有订购的坐标（x，y）的一个点。上的点P与距离D的查找，执行二进制搜索找到两个点中的每个列表中，以便找到矩形区域分有其切比雪夫距离为P＆所述; D.     最后，计算所有这些点的欧氏距离P

Approach 2: Create two lists, each with all the point ordered by one of the coordinates (x,y). On lookup of point P with distance D, perform binary search to find two points in each of the list in order to find the rectangular region where points have their Chebyshev distance to P < D. Finally, calculate euclidean distance of all those points to P

我猜一个国家的最先进的算法，将大大优于这个有关系吗？任何对此的想法是AP preciated

I'm guessing the state-of-the-art algorithms will be vastly superior to this, though? Any ideas on this are appreciated

推荐答案

一些技巧可以帮助你：

看看 KDTree ，它是一个k维树（2D的你的情况），这是寻找近邻的最佳方式之一。 也许你可以受益于一个空间数据库，专门开发来处理空间数据; 您可以使用上述任何你想要的距离函数。根据您的应用程序，你想图上距离，大圆距离，不断的斜距，定方位的距离，等你的距离函数应该由你知道。我用它来申请大圆（半正弦波）的距离，以应对谷歌，地图状地图和轨迹。 Take a look at KDTree, it is a k-dimensional tree (2d in your case) which is one of the best ways to look for nearest-neighbors. Perhaps you could benefit from a Spatial Database, specifically developed to deal with Geospatial Data; You could use any of the above with your desired distance function. Depending on your application, you want map distance, great circle distance, constant slope distance, constant bearing distance, etc. Your distance function should be known by you. I use to apply great circle (haversine) distance to deal with google-maps-like maps and tracks.

如果你想要一个Python实现，有 scipy.spatial （文档）。从这个模块，功能 query_ball_point（（PX，PY），半径）好像是你在寻找什么。

In case you want a Python implementation, there is scipy.spatial (docs). From this module, the function query_ball_point((px, py), radius) seems to be what you're looking for.

希望这有助于！