반경에서 가장 가까운 이웃을 찾으십시오

Question

나는 내 공간에서 a 의 집합을 가지고 있지만, 나는 그들이 2D 비행기에 있다고 가정 할 수있다.

나는 b 의 또 다른 포인트 세트를 가지고있다.

b 의 모든 점에 대해 에서 r 의 모든 점을 에서 찾고 싶습니다. > B 세트.

KDtree와 함께했는데, 이것은 데이터 구조를 만들고 이웃 을 찾을 수있는 매우 빠르고 쉬운 알고리즘을 제공합니다 경로를 피할 수 있기 때문에 모든 점을 찾지 못합니다. 내 반지름의 요소가 포함되었지만 반경 중심의 동일한 하위 집합에는 포함되지 않습니다.

KDTree 실패한 의 최소 예 :

KDTREE를 탐색하는 동안 목표 지점 (빨간색)은 점수 1의 선 아래에 있습니다. 이렇게하면 줄의 점 탐색으로 진행하면 빨간색 점 반경 안의 실제 점이 놓칠 것입니다.

>>

어떤 알고리즘이나 데이터 구조가 100 % 정확도를 허용합니까?

나는 내가 더 나빠질 것이지만, 검색 속도와 정확성 사이의 균형을 찾는 것을 알고있다.

Answer 1

K-D 트리는이 문제를 해결하기위한 좋은 데이터 구조입니다.그러나 검색 절차를 중심점에 맹목적으로 적용 할 수는 없지만 조금 더 똑똑해야합니다.

포인트의 KD 트리를 검색하는 동안 왼쪽 또는 오른쪽 하위를 검색 할 때마다, 분할 평면이 원의 왼쪽에 있는지, 동그라미 오른쪽에 있는지 확인하십시오..

Splitting Plane이 원의 왼쪽에있는 경우 오른쪽 자식에서 계속해서 검색해야합니다.그러나 은 과 교차 할 때 어린이를 모두 검색해야합니다.