python - 智能存储坐标，获取(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]

其中 hasrsine(lat,lon) 是半正弦函数。

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

我的第一个想法是对纬度进行简单排序，然后在每次迭代中计算最大和最小纬度，将列表平分到这些值，然后在这个小得多的列表上运行points_in_range()。我也可以对这个较小的列表进行二等分，但我首先必须在 lon 上对其进行排序，因此就大 O 而言，仅使用 points_in_range() 实际上更好。

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

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

Answer 1

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

来自 m-tree 的 wiki 页面:

For a given query object Q ∈ D and a maximum search distance r(Q), the range query range(Q, r(Q)) selects all the indexed objects Oj such that d(Oj, Q) ≤ r(Q).[2]

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

您可以在亚线性时间内执行范围查询。此外，仅当您使用的距离测量遵守三角不等式时，此方法才有效。如果半正矢(我以前从未有过它的头)，遵守三角不等式，这应该对你有用。