algorithm - QuadTree 中的相邻单元格

Question

有没有办法在四叉树细分中找到相邻的单元格？我的意思是在任何级别与所选单元格相邻的所有单元格？

Answer 1

空间填充曲线完全填充空间并将 2 维减少为 1 维。我在 phpclasses.org（希尔伯特曲线）上写了一个免费的 php 类。它包括az曲线、4条希尔伯特曲线和摩尔曲线和一个四键功能。这是一篇关于碰撞检测和四叉树的博客：lab.polygonal.de/?p=202?

morton aka 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选择第一个非空值。