QuadTree中的相邻单元格

Question

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

Answer 1

一个空间填充曲线完全填充一个空间，并将2维减少到1维。我在phpclasses.org (希尔伯特曲线)写了一个免费的php类。它包括一条z曲线，4条希尔伯特曲线，摩尔曲线和一个四键函数。这里有一个关于碰撞检测和四叉树的博客: 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选取第一个非空值。