智能存储坐标，从(lat_，lon_)中获取一定范围内的坐标集

Question

我有一个坐标形式为point = (lat,lon)的点列表。该列表可以包含几个1000点。在我的旧的，简单的实现。我正在做这个:

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)为haversine函数。

这在时间上是线性的，我们显然可以做得更好。通过按纬度和经度对列表中的点进行排序，我认为可以在很短的时间内完成相同的操作，因为通常只有<1%的点符合标准。通过以一种智能的方式存储数据，我可以只查看5%的点，甚至更少。

我的第一个想法是在lat上做一个简单的排序，然后在每次迭代中计算最大和最小纬度，将列表wrt平分到这些值，然后在这个小得多的列表上运行points_in_range()。我也可以在这个较小的列表上做一个等分，但我首先要对它进行lon排序，所以直接使用points_in_range()实际上在大o方面更好。

第二个想法是将整个坐标系统离散成一个二维数组，但这对我来说似乎很尴尬。

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

Answer 1

看一下m-tree。还有许多其他的空间索引:http://en.wikipedia.org/wiki/Spatial_database最初，您构建数据结构(索引)，然后仅执行范围查询。

来自wiki页面的m-trees:

对于给定查询对象Q∈D，最大搜索距离r(Q)，范围查询范围(Q, r(Q))选择D (Oj, Q)≤r(Q)的所有索引对象Oj [2]

m树的维基百科页面也有范围查询的算法。

可以在次线性时间内执行范围查询。这也只适用于你使用的距离测量服从三角形不等式的情况。