QuadTree의 인접 셀

Question

quadtree 세분화에서 인접 셀을 찾을 방법이 있습니까? 어느 레벨에서나 선택한 셀에 인접한 모든 셀을 의미합니까?

Answer 1

공간 채우기 곡선은 공간 completley를 채우고 2 차원을 1 차원으로 줄입니다. 필자는 phpclasses.org (hilbert 커브)에서 무료 PHP 클래스를 작성했습니다. 그것은 z 곡선, 4 힐버트 곡선과 무어 곡선과 쿼드 키 기능을 포함합니다. 다음은 충돌 감지 및 쿼드 트리에 대한 블로그입니다 : lab.polygonal.de/?p=202?

모튼 일명 Z-곡선 구성하는 것이 용이하다. x와 y 값을 2 진수로 변환하고 값을 연결하십시오. 여기에서 코드를 찾을 수 있습니다 : http://msdn.microsoft.com/en-us/library/bb259689.aspx. 최상위 비트를 사용하여 상위 경계를 확인할 수 있습니다.

Answer 2

노드가 어떤 자식인지 추적해야합니다. 인접 노드가 동일한 상위 노드에 있으면 그냥 반환하십시오. 그렇지 않다면, 당신은 공통 조상을 찾을 수있을 때까지 나무 위로 걸어 가야합니다. 그런 다음 올바른 레벨로 되돌아 올 때까지 (또는 아래쪽에 도달 할 때까지) 비슷한 경로를 따르십시오.

Node WalkLeft(Node node) 
{ 
    if (node == null) return null; 

    Node leftParent; 
    switch (node.ChildDirection) 
    { 
     case ChildDirection.Root: 
      return null; 
     case ChildDirection.TopRight: 
      return node.Parent.TopLeft; 
     case ChildDirection.BottomRight: 
      return node.Parent.BottomLeft; 
     case ChildDirection.TopLeft: 
      leftParent = WalkLeft(node.Parent); 
      return leftParent.TopRight ?? leftParent; 
     case ChildDirection.BottomLeft: 
      leftParent = WalkLeft(node.Parent); 
      return leftParent.BottomLeft ?? leftParent; 
    } 
} 

다른 방향으로도 마찬가지입니다.

x ?? y은 첫 번째 Null이 아닌 값을 선택합니다.