주기적인 한계를 가진 쿼드 트리를 구현하는 방법에 대한 참조가 있습니까?

StackOverflow https://stackoverflow.com/questions/941135

  •  06-09-2019
  •  | 
  •  

문제

평면에 공간 데이터 - (x, y) 포인트가 있습니다. 아이디어는 주어진 (a, b) 포인트의 이웃인지 찾는 것입니다. 포인트는 둘 사이에 약간의 거리가 있다면 이웃입니다. 문제는 공간이 주기적이라는 것입니다. 즉, 점이 가장자리에 매우 가까운 경우 (<l)이 점은 반대쪽 가장자리에 가까운 점의 인접이어야합니다. (이 경우 정기적으로 비행기가 반복된다는 것을 의미합니다) 

|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
|=================== | ===================|
|(a, b)         (c,d)| (a, b)      (c,d)  |
|                    |                    |
|  (e,f)             |   (e, f)           |
|               (h,i)|               (h,i)|
| ================== | ===================|

그것은 점 (a, b) 및 (c, d) 및 (h, i) 이웃이어야합니다. (a, b)의 이웃은 중심 (a, b)이있는 반경 L이있는 원 안에있는 지점입니다.

논문, 방법은 모두 환영합니다.

감사,

얘들아:

답변 해주셔서 감사합니다. STACKOVERFLOW를 확인하지 않았습니다. 잠시 동안 다른 프로젝트에서 바쁘게 답변을 확인할 것입니다. 정말 감사합니다.

도움이 되었습니까?

해결책

"검색 원"을 PI/2 각도로 원형 차트로 나누지 않겠습니까? 텍스트와 간단한 이미지를 통해 이것을 얻을 수 있는지 살펴 보겠습니다.

Alt Text http://img168.imageshack.us/img168/8426/circleinquarters.gif

아이디어는 "서클 검색"을 4 개의 "파이 차트"로 보는 것입니다. 따라서 C (a, b, l)로 검색 할 때 쿼드 트리에서 통과 할 때 원이 DOCENT ''를 고려해야합니다. t 쿼드 트리의 왼쪽 상단 구석에만 교차 하므로이 경우 4 개의 가지로 분기해야합니다 (이 영역이 주기적이지 않은 경우 1 개가 아니라).

다른 팁

xdist = min( (x1-x2) % px, (x2-x1) % px )

여기서 px는 x-period입니다.

ydist와 나머지는 독자를위한 운동으로 남겨 둡니다 :-)

루트 레벨 만 주기적으로 복제되므로 쿼드 트리를 그대로 유지하는 것이 더 간단 해 보입니다. 주기성을 고려하려면 몇 가지 요청을 수행하십시오 (x+i*dx,y+j*dy,L) 각 요청에 대해 (x,y,L). 쿼리 디스크가 트리의 루트 노드와 교차하도록 I, J의 루프.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top