도넛 형 2D 공간 용 이진 공간 분할 데이터 구조

Question

필자는 모서리를 감싸는 2D 맵을 가지고 있습니다. 따라서 오른쪽 가장자리에서 벗어나면지도의 왼쪽에 다시 나타납니다. 다른 세 가지 가장자리와 마찬가지로.

점의 범위에서 요소를 찾는 데 사용하는 KDTree의 문제는 상속받을 수 있습니다. 일반적으로 하이퍼 영역이 하이퍼 평면과 충돌하여 트리의 다른면을 계속 검색해야하는지 확인하지만 가장자리를 배치하는 경우에는이 체크가 작동하지 않습니다.

도넛 형 2D 공간에서 작동하도록 KD 트리를 수정할 수있는 방법이 있습니까?

Answer 1

쿼드 트리는 4 개의 리프가있는 KD 트리입니다. quadtree는 데이터 구조가 랩 자체이기 때문에 줄 바꿈하는 데 도움이되지 않습니다. 구조의 quadtree 2x 크기 만 사용하면됩니다.

Answer 2

지타 마로는 "2x 크기"쿼드 트리를 기반으로하는 방법을 제안했지만 설명하지 않았습니다. 이것은 합리적인 제안입니다. 쿼트 트리가 두 개가 아닌 네 개의 노드를 4 번 이상 사용한다는 점을 제외하고는 잠정적으로 다른 방법을 제안하기 전에 아래에서 설명하겠습니다.

각 좌표 (X, Y)를 가지고 있다고 가정하고 -.5 < x <= .5 -.5 < y <= .5 및 j, k 정수, 점 (x +의 J와 Y + K)가있을 때마다 점 (X, Y)과 동일하다. quadtree T가 좌표 범위가 -1 < x,y <= 1 인 표지를 보자. -.5 < x,y <= .5 인 경우 (x, y)에 항목을 추가 할 때마다 x>0을 x+1}, y' = {y-1을 으로 설정하면 x' = {x-1을 입력하십시오. 또한 항목을 (x, y '), (x', y ') 및 (x', y)에 추가하십시오. [나중에 포인트를 삭제할 때 (x ', y') 등을 다시 계산하고 삭제하십시오.] (-.5,.5] 외부의 조회 좌표가 제대로 조정되는 한 가장 가까운 포인트 조회가 제대로 작동하는지 확인하기 쉽습니다.

4 배 노드 수가 거래 차단기 인 경우 위의 하위 트리에서 위에서 설명한 좌표가 레벨 k=3이고 상대 좌표가 레벨 k 아래에 저장되어 있으면 단일 노드를 유지할 수 있어야합니다 레벨 k 아래의 하위 트리 사본. 즉, 레벨 k의 각 하위 트리에는 네 개의 부모가 있습니다. (나는 이것이 충분히 작동 하는지를 충분히 알지 못했고, 그렇지 않다면 대답을 편집 할 것입니다.)

Answer 3

데이터 구조는 변경할 필요가 없지만 검색 절차는 않습니다. 각 점을 [0, w] * [0, h]의 좌표 (x, y)로 나타내며, w는지도의 폭, h는 높이, *는 데카르트 곱을 나타냅니다. 이 포인트를 일반 KD 트리에 저장하십시오.

포인트 (x, y)와 직사각형 [a, b] * [c, d]가 주어지면 KD 트리를 검색하기위한 기본 기본 요소는 점에서 사각형까지의 거리 (제곱)를 결정합니다. 일반적으로이 g이

g(z, e, f) = e - z if z < e 
      0  if e <= z <= f 
      z - f if f < z 

가 Z의 일차원 거리이다 (X, A, B) ² + g (Y, C, D) ²이다 [즉, (F)]. 토 로이드 형 공간에서 랩 어라운드를 설명하기 위해 g를 약간 수정합니다.

g(z, e, f, v) = min(e - z, (z + v) - f) if z < e 
       0      if e < z < f 
       min(z - f, (e + v) - z) if f < z. 

제곱 거리를 g (X, A, B, W) ² + g (Y, C, D, H) ²이다. 나는 실행 시간이이 변형에 필적 할 것으로 기대한다.(재발행을 다시 시도 하겠지만 정규 KD 나무에 대한 최악의 경우는 대부분 n 시간 중 가장 가까운 이웃을 2D로 식별하는 O (n ^1/2)보다 훨씬 나쁩니다.