QuadTree中的相鄰單元格

Question

是否有任何方法可以在四叉樹細分中查找相鄰單元格？我的意思是在任何層次上與所選單元相鄰的所有單元格？

Answer 1

空間填充曲線填充空間完整性並將2維減小到1維。我已經在phpclasses.org（hilbert曲線）上寫了一個免費的php類。它包括一條z曲線，4條希爾伯特曲線和摩爾曲線以及一個quadkey函數。這是一個關於碰撞檢測和四叉樹的博客：lab.polygonal.de/？p = 202？

甲莫頓又名Z-曲線很容易構造。將x值和y值轉換爲二進制值並連接值。你可以在這裏找到一些代碼：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選取第一個非空值。