我有数百万个地理点。对于其中的每一个，我都想找到所有“相邻点”，即某个半径(比如几百米)内的所有其他点。
这个问题有一个简单的 O(N^2) 解决方案——简单地计算所有点对的距离。但是，因为我正在处理适当的距离度量(地理距离)，所以应该有一种更快的方法来执行此操作。
我想在 python 中执行此操作。想到的一种解决方案是使用某些数据库(带有 GIS 扩展的 mySQL，PostGIS)，并希望这样的数据库能够使用某些索引有效地执行上述操作。不过，我更喜欢更简单的东西，它不需要我构建和学习此类技术。
几点
- 我将执行“寻找邻居”操作数百万次
- 数据将保持静态
- 因为这个问题在某种意义上很简单，所以我希望看到他们使用 python 代码来解决它。
就 python 代码而言，我想要一些类似的东西:
points = [(lat1, long1), (lat2, long2) ... ] # this list contains millions lat/long tuples
points_index = magical_indexer(points)
neighbors = []
for point in points:
point_neighbors = points_index.get_points_within(point, 200) # get all points within 200 meters of point
neighbors.append(point_neighbors)
最佳答案
科学
首先要做的事情:有一些预先存在的算法可以做一些事情，比如 k-d tree . Scipy 有一个 python 实现 cKDtree可以找到给定范围内的所有点。
二分查找
然而，根据您正在做的事情，实现类似的事情可能并不简单。此外，创建一棵树相当复杂(可能会产生相当大的开销)，您可以通过我之前使用过的一个简单技巧来解决问题:
- 计算数据集的 PCA。您想要旋转数据集，使最重要的方向在第一，正交(较小)的第二方向在第二。您可以跳过此步骤而只选择 X 或 Y，但它的计算成本低且通常易于实现。如果只选择X或Y，选择方差较大的方向。
- 按主要方向(将此方向称为 X)对点进行排序。
- 要找到给定点的最近邻居，请通过二分搜索找到 X 中最近的点的索引(如果该点已经在您的集合中，您可能已经知道该索引并且不需要搜索)。迭代地查看下一个和上一个点，保持迄今为止的最佳匹配及其与搜索点的距离。当 X 的差异大于或等于到目前为止最佳匹配的距离时，您可以停止查找(在实践中，通常点数很少)。
- 要找到给定范围内的所有点，请执行与步骤 3 相同的操作，除了在 X 的差异超过范围之前不要停止。
实际上，您正在进行 O(N log(N)) 预处理，并且对于每个点，如果您的点分布不佳，则大致为 o(sqrt(N)) - 或更多 .如果这些点大致均匀分布，则 X 中比最近邻点更近的点数将在 N 的平方根的数量级上。如果许多点在您的范围内，则效率较低，但绝不会比蛮力差很多。
这种方法的一个优点是它可以在非常少的内存分配中执行，并且大部分可以在非常好的内存局部性下完成，这意味着尽管有明显的限制，它仍然表现得很好。
德劳尼三角剖分
另一个想法:一个Delauney triangulation可以工作。对于 Delauney 三角剖分，假定任何点的最近邻居都是相邻节点。直觉是，在搜索期间，您可以根据与查询点的绝对距离维护一个堆(优先级队列)。选择最近的点，检查它是否在范围内，如果是，则添加它的所有邻居。我怀疑不可能遗漏任何这样的点，但您需要更仔细地查看它以确保...
关于python - 在python中的地理数据中查找圆圈内的所有坐标，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6371187/