Octree에서 가장 가까운 이웃 검색

Question

octree에서 NN 알고리즘은 어떻게 작동합니까? 나는 좋은 설명을 찾았지만, 사람들은 KD- 트리를 대신 사용한다고 대부분 이야기했다. 내가 그것을 할 수 없어, 나는 octree에 NN 알고리즘을 단계별로 시각화해야합니다. 포인트가 속한 곳

1) 하위 팔분 찾기 :

내가 가장 논리적 인 방법에있을 거라고 생각 바와 같이

. 더 가까운 지점이 발견되면 그 거리

4) 내의 인접한 octants 어떠한 오버랩이 있으면

2) 선택)이 팔분

3에 가장 가까운 지점까지의 거리 계산, 탐색 거리를 계산할 .

5) 모든 가능한 octants이

6

을 통과 할 때까지 가장 가까운 지점

를 돌려줍니다) 반복하지만 난이 하나 단계를 시각화하여 좋은 단계를 생각하지 못할.

Answer 1

검색 지점에 가장 가까운 지점을 찾으거나 거리가 증가하는 순서로 지점 목록을 얻으려면 트리의 내부 노드와 포인트를 모두 저장할 수있는 우선 순위 대기열을 사용할 수 있습니다. 거리의 순서.

점 (잎)의 경우 거리는 검색 지점에서 점까지의 거리에 불과합니다. 내부 노드 (옥탄트)의 경우 거리는 검색 지점에서 옥탄트에있을 수있는 지점까지의 최소 거리입니다.

이제

, 당신은 단지 우선 순위 큐에 트리의 루트를 넣어 검색하고 반복 :

1. 가 우선 순위 큐의 머리를 제거;
2. 큐의 헤드가 지점 인 경우 트리에서 아직 반환하지 않은 가장 가까운 지점입니다. 내부 노드가 더 가까운 지점을 가질 수 있다면 우선 순위 대기열에서 먼저 반환되었으므로 이것을 알 수 있습니다. 큐의 헤드 내부 노드가 있었다면
는, 다음 검색 지점에서 거리가 증가하는 순서로 큐

이 트리의 모든 포인트를 생산할 예정으로 다시 아이를 넣어. 동일한 알고리즘이 KD 트리에도 적용됩니다.