python - 按接近度对一组点进行分组

Question

我有几千个点表示为纬度和经度的二维 float 组。

(42.385305, -87.963793)
(41.703427, -88.121665)
(41.889764, -87.978553)
(41.995931, -87.787501)
(42.25875, -87.948199)
              .
              .
              .

在此集合中，纬度的最小值和最大值分别为 34.03176 和 42.470814，经度的最大值和最小值分别为 -118.238819 和 -87.598201。

我想把这些点分成0.025纬度和0.03经度的区域，然后每个区域考虑一次，对每个区域的点做一些计算和操作。

或者，如果我能找到两个或更多点靠得太近的区域，比如半径 3 公里以内，那就更好了。

我曾考虑过使用 HashMap 或二维数组，但设置有效键或引用正确的区域会很棘手。

R-tree 可能不合适，因为它的构建复杂且效率低下，特别是考虑到我不需要随机访问。正如我上面提到的，我正在一个一个地遍历每个区域。

执行此操作的有效方法是什么？

Answer 1

如果您完全矢量化距离计算，几千个点应该不会花那么长时间:

In [1]:
from numpy import *
In [3]:
def lg_lat_distance(p1,p2): #based on Spherical Law of Cosines
    lg1=p1[0] #data format, (latitude, longitude)
    la1=p1[1]
    lg2=p2[0]
    la2=p2[1]
    return arccos(sin(la1)*sin(la2)+cos(la1)*cos(la2)*cos(lg1-lg2))*6371 #in km
In [14]:
data=array([(42.385305, -87.963793),
            (41.703427, -88.121665),
            (41.889764, -87.978553),
            (41.995931, -87.787501),
            (42.25875, -87.948199)]) #5 elements
data=data/180*pi
In [16]:
dist_matrix=(lg_lat_distance(hstack([data,]*5).reshape(-1,2).T, vstack([data,]*5).T)).reshape(5,5)
print dist_matrix

[[  9.49352980e-05   1.77442357e+01   2.54929710e+00   1.96682533e+01
    1.80515399e+00]
 [  1.77442357e+01   0.00000000e+00   1.59289162e+01   3.71753501e+01
    1.94041828e+01]
 [  2.54929710e+00   1.59289162e+01   0.00000000e+00   2.12484793e+01
    3.67668607e+00]
 [  1.96682533e+01   3.71753501e+01   2.12484793e+01   0.00000000e+00
    1.79018035e+01]
 [  1.80515399e+00   1.94041828e+01   3.67668607e+00   1.79018035e+01
    9.49352980e-05]]

In [17]:
%timeit dist_matrix=(lg_lat_distance(hstack([data,]*5).reshape(-1,2).T, vstack([data,]*5).T)).reshape(5,5)
1000 loops, best of 3: 245 µs per loop

我认为一旦你有了 dist_matrix，事情就会变得简单。您可以使用 bool 索引过滤掉成对距离 <5 公里的对。或者您可以运行聚类分析。