최근 접 이웃 탐색 : 파이썬

는 I는 2 차원 어레이 가지고최근 접 이웃 탐색 : 파이썬

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0], 
       [6588253.79, 1933602.89, 212.66, 0, 0], 
       etc...)

처음 두 요소 MyArray[0] 및 MyArray[1]는 포인트 X 및Y 좌표이다.

배열의 모든 요소에 대해, 나는 X 단위의 반경에있는 그것의 하나의 가장 가까운 이웃을 반환하는 가장 빠른 방법을 찾고 싶습니다. 우리는 이것이 2D 공간에 있다고 가정합니다.

이 예의 경우 X = 6라고 말하면됩니다.

모든 요소를 다른 모든 요소와 비교하여 문제를 해결했지만 목록 길이가 22k 포인트 인 경우 15 분 정도 걸립니다. 우리는 결국 약 3 천만 포인트의 목록에서이를 실행하기를 희망합니다.

K-d 나무에 대해 읽었으며 기본 개념을 이해했지만 스크립트를 작성하는 방법을 이해하는 데 어려움이있었습니다.

출처

2012-10-16 Dlinet

"Kt 나무"란 무엇입니까? "k-d tree"를 의미합니까? 2 차원 포인트의 경우 [쿼드 트리] 만 있으면됩니다 (http://en.wikipedia.org/wiki/Quadtree). 이전 질문은 파이썬에서 quadtree 구현을 찾고있었습니다 : http://stackoverflow.com/questions/6060302/pure-python-quadtree-implementation –

감사합니다! 나는 k-d 나무를 의미했다. 나는 쿼드 트리를 찾을 것입니다. – Dlinet

[scipy.spatial'] 모듈 (ko-d 트리 구현)이 있습니다. –

scipy를 제안한 John Vinyard에게 감사드립니다.

전제 조건 : 는 NumPy와 및 SciPy

가져 SciPy와 NumPy와 모듈
이 5의 복사본을 만듭니다 설치 좋은 연구와 테스트 후, 여기이 질문에 대한 솔루션입니다 을 포함하는 2 차원 배열로 X 축과 Y 축의 값이입니다.

같은 cKDTree의 인스턴스를 만듭니다

YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100) 
#Play with the leafsize to get the fastest result for your dataset

를 조회 가장 가까운 이웃에 대한 cKDTree를 6 개 단위 내에서 같은 :
```
for item in YourArray: 
    TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6) 
```
각 항목에 대한 YourArray에, TheResult 것 두 점 사이의 거리의 튜플이고 점의 위치 인덱스는 YourArray입니다.

KD 나무와 혼동을 느끼는 사람에게 도움이 되었기를 바랍니다.

출처

2012-10-26 00:07:55 Dlinet

컬렉션이 아닌 특정 시점에 가장 가까운 것은 어떨까요? –

@SteveYeago [query_ball_point] (http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.spatial.cKDTree.query_ball_point.html#scipy.spatial.cKDTree.query_ball_point) 사용할 수 있습니다. – ldavid

답변

관련 문제