通過接近對一組點進行分組

Question

我有幾千個點表示爲緯度和經度的2D浮點數組。

(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公里範圍內，會好得多。

我想過使用哈希映射或二維數組，但然後設置有效的鍵或引用正確的區域將是棘手。

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。您可以使用布爾索引過濾掉配對距離爲< 5公里的配對。或者你可以運行一個聚類分析。