algorithm - QuadTree の隣接セル

Question

四分木の細分化で隣接するセルを見つける方法はありますか? 任意のレベルで選択したセルに隣接するすべてのセルを意味しますか?

Answer 1

空間充填曲線は、空間を完全に充填し、2 次元を 1 次元に縮小します。私は phpclasses.org で無料の 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 ?? ynull 以外の最初の値を選択します。