以智能方式存储坐标以获取特定范围内的坐标集合

Question

我有一组点，每个点都有经纬度坐标，格式是point = (lat, lon)。这组点可能有几千个。在我以前简单的实现中，我是这样做的：

def points_in_range(point1,list_of_pts,tolerance):
    """
    takes one coordinate, a list of points and the tolerance and
    returns a list of indexes of points within range/tolerance from the coordinate.
    """
    return [i for i,point2 in enumerate(list_of_pts) if haversine(point1,point2)<= tolerance]

这里的haversine(lat, lon)是一个计算距离的函数。

这个方法的时间复杂度是线性的，显然我们可以做得更好。通过对列表中的点按纬度和经度进行排序，我认为可以在更短的时间内完成同样的操作，因为通常只有不到1%的点符合条件。通过以更聪明的方式存储数据，我可能只需要查看5%甚至更少的点。

我最初的想法是先对纬度进行简单排序，然后在每次迭代中计算最大和最小纬度，按照这些值将列表分成两部分，然后在这个更小的列表上运行points_in_range()。我也可以在这个更小的列表上进行二分查找，但我首先需要按经度对它进行排序，所以直接使用points_in_range()在大O表示法上其实更好。

第二个想法是将整个坐标系统离散化成一个二维数组，但我觉得这样做很麻烦。

有没有人看到我可以使用的好数据结构？谢谢。

Answer 1

你可以看看m-tree。这是一种空间索引，还有很多其他的空间索引可以参考：http://en.wikipedia.org/wiki/Spatial_database。最开始，你需要构建一个数据结构（也就是索引），之后你就可以进行范围查询了。

关于m-tree的维基百科页面上提到：

对于给定的查询对象Q ∈ D和最大搜索距离r(Q)，范围查询range(Q, r(Q))会选择所有满足条件的索引对象Oj，使得d(Oj, Q) ≤ r(Q)。[2]

m-tree的维基百科页面上还有范围查询的算法。

你可以在亚线性时间内进行范围查询。这种方法只有在你使用的距离测量符合三角不等式时才有效。如果haversine（我之前没听说过）符合三角不等式，那么这个方法就适合你。