모르몬 코드가있는 가장 가까운 이웃을 찾습니다

Question

두 번째 점을 각각 morton code으로 변환하기 위해 decode/encode 방법을 구현했습니다.

points=[(200,300),(500,150),(100,50)] 
mortonCodes = {} 
for p in points: 
    mortonCodes[encode(p)] = p 

nearest = findNearestNeighbor(mortonCodes, (201,305)) 
print(nearest) # ---> should return (200,300) 

가 어떻게이게 가능 : 내가 찾던

그래서이 같은 예를 들어 뭔가를 (A min_distance에서) 가장 가까운 이웃을 찾는 것입니다?

Answer 1

당신은 예 (120)에 대해 다음, min_distance을 사용하여 수행 할 수 있습니다 는 쿼리 포인트 qp=(201,305)을 사용하고 거리를 추가/substracting하여 최소 및 최대 포인트를 만듭니다 min=(81, 185) 및 max=(321,425)을. 이제이 두 점에 대한 morton 코드를 만듭니다.

(210,305)의 120 분의 거리 내에있는 모든 포인트는 인 모르몬 코드 mcWithin120을 갖습니다. morton 코드로 정렬 된 점 목록이 있으면 검색 영역을 상당히 좁혀 야합니다.

범위에는 오 탐지가 포함됩니다. min과 max 사이의 morton 코드가있는 모든 점이 주어진 거리 120에있는 것은 아니므로 범위에서 모든 점을 '실제로'올바른 거리 내에 있는지 확인해야합니다.

공간 검색에 관심이 있다면 PH-Tree을 살펴보십시오. quadtree와 비슷한 공간 인덱스로, morton 순서를 사용하여 트리 구조와 검색을 최적화합니다.