在python中查找地理数据中的一个圆内的所有坐标 [英] Find all coordinates within a circle in geographic data in python

问题描述

我有数百万个地理位置.对于这些中的每一个，我都希望找到所有相邻点"，即某个半径(例如几百米)内的所有其他点.

I've got millions of geographic points. For each one of these, I want to find all "neighboring points," i.e., all other points within some radius, say a few hundred meters.

对此问题有一个简单的O(N ^ 2)解决方案-只需计算所有成对点的距离即可.但是，由于我正在处理适当的距离度量(地理距离)，因此应该有一种更快的方法.

There is a naive O(N^2) solution to this problem---simply calculate the distance of all pairs of points. However, because I'm dealing with a proper distance metric (geographic distance), there should be a quicker way to do this.

我想在python中做到这一点.想到的一种解决方案是使用某些数据库(带有GIS扩展功能的mySQL，PostGIS)，并希望这样的数据库可以使用某些索引来有效地执行上述操作.不过，我更喜欢一些简单的方法，它不需要我构建和学习此类技术.

I would like to do this within python. One solution that comes to mind is to use some database (mySQL with GIS extentions, PostGIS) and hope that such a database would take care of efficiently performing the operation described above using some index. I would prefer something simpler though, that doesn't require me to build and learn about such technologies.

几点

• 我将执行数百万次查找邻居"操作
• 数据将保持不变
• 因为从某种意义上讲问题很简单，所以我想看看他们能解决问题的python代码.

根据python代码，我想要一些类似的东西:

Put in terms of python code, I want something along the lines of:

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) 

推荐答案

Eamon提出了一个简单的解决方案，该解决方案使用了SciPy中实现的btrees.

Tipped off by Eamon, I've come up with a simple solution using btrees implemented in SciPy.

from scipy.spatial import cKDTree
from scipy import inf

max_distance = 0.0001 # Assuming lats and longs are in decimal degrees, this corresponds to 11.1 meters
points = [(lat1, long1), (lat2, long2) ... ]
tree = cKDTree(points)

point_neighbors_list = [] # Put the neighbors of each point here

for point in points:
    distances, indices = tree.query(point, len(points), p=2, distance_upper_bound=max_distance)
    point_neighbors = []
    for index, distance in zip(indices, distances):
        if distance == inf:
            break
        point_neighbors.append(points[index])
    point_neighbors_list.append(point_neighbors)

这篇关于在python中查找地理数据中的一个圆内的所有坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！