가장 가까운 이웃을 찾기 위한 공간 분할 알고리즘은 어떻게 작동합니까?

Question

가장 가까운 이웃을 찾기 위해, 공간 분할 알고리즘 중 하나이다.어떻게 작동하나요?

2D 점 집합(x 및 y 좌표)이 있고 점(a,b)이 주어졌다고 가정합니다.이 알고리즘은 가장 가까운 이웃을 어떻게 찾나요?

Answer 1

공간 분할은 실제로 응용 프로그램이 점이나 다각형을 더 쉽게 처리할 수 있도록 공간을 분할하는 밀접하게 관련된 알고리즘 제품군입니다.

문제를 해결하는 방법은 여러 가지가 있을 것 같아요.솔루션을 구축하려는 의도가 얼마나 복잡한지 모르겠습니다.간단한 방법은 아마도 공간을 2로 자르는 이진 트리를 만드는 것입니다.모든 점은 일부 중간 평면으로 나누어집니다.포인트가 부족할 때까지 재귀적으로 세분화하여 트리를 구축하세요.

그러면 트리를 순회할 때마다 검색 영역이 좁아지기 때문에 가장 가까운 이웃을 검색하는 것이 최적화됩니다.

일부 문헌에서는 이것을 다음과 같이 부릅니다. kd 트리

Answer 2

이 두 동영상은 다음과 같습니다.

• KD 트리가 어떻게 구축되는지 설명 :http://www.youtube.com/watch?v=T9H2KKJ_PL8
• 가장 가까운 이웃 검색을 수행하는 방법 설명 : http://www.youtube.com/watch?v=2SBVSXWGTPI