근접으로 포인트 세트 그룹화

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 경의 존으로 그룹화 한 다음 각 존을 한 번 고려하여 각 존의 포인트에 대한 계산과 작업을 수행하려고합니다.

두 개 이상의 지점이 너무 가깝게 위치하는 반경 3km 이내의 지점을 찾을 수 있다면 훨씬 더 좋습니다.

해시 맵 또는 2D 배열을 사용하려고 생각했지만 유효 키를 설정하거나 올바른 영역을 참조하는 것은 까다로울 수 있습니다.

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 킬로미터를 사용하여 부울 색인을 사용하여 쌍을 필터링 할 수 있습니다. 또는 클러스터 분석을 실행할 수 있습니다.