3

octree または quad を反復する方法を把握するのに苦労しています。そして、それは、私が反復のさまざまな神話を経験していないためかもしれません. しかし、float x,y,z; を保持する四分木を作成したとしましょう。ワードカラー。ここで、このノードは一度に 4 つの子しか生成できないとしましょう (そして、これらの子は両方とも 4 つの子を生成することができます)。兄弟/姉妹はできる)、作成された 4 つの子すべてが同じ dword カラーである (繰り返しますが、その場合、その兄弟/姉妹はまだ作成できます)、または作成されたノードの合計は 87380 です。容器。そして、プロセスは続きます。

現在、ノードを保持するこのコンテナーは (たとえば) 7 レベルの深さであり、子の子のすべての子はすべて異なる x、y、z、および色です。私が抱えている問題は、このコンテナをどのように反復処理するか、すべての子供、姉妹をどのように処理できるかということです。ルートは 4 つの子につながり、それらの 4 つの子には 4 つの子があるため、等々: 4^1+4^2....+4^7. 複雑な if ステートメントを記述したり、ノード全体を (ルートから開始して) 反復したりせずに、必要なノードを見つけるにはどうすればよいですか? コンテナー (ノードを生成するコンテナー) には、このプロセスを単純にするための追加のコードが必要ですか?

質問が一般的な場合は申し訳ありません。

4

1 に答える 1

5

ツリー全体を反復するのは簡単で、再帰的に実行できます。

void iterate(node *n) {
    // do something with n
    if (n->child1 != NULL) iterate(n->child1);
    if (n->child2 != NULL) iterate(n->child2);
    if (n->child3 != NULL) iterate(n->child3);
    if (n->child4 != NULL) iterate(n->child4);
}

次に呼び出すiterate(root)とdo something、四分木内のすべてのノードで発生します。

ただし、これは実際にはあなたが求めているものではないと思います。四分木にデータを保持するだけでは意味がありません。四分木で特定のノードを見つけたい場合は、別のものが必要です。x,y四分木で点を見つけたいとしましょう。次に、次のようなことを行います。

void find(node *n, float x, float y) {
    if (x == n->x && y == n->y) // you've found it!
    if (x < n->x) {
        if (y < n->y) {
            if (n->child1 != NULL) {
                find(n->child1, x, y);
            } else {
                // point not in quadtree
            }
        } else {
           ...same, but child2
        }
    } else {
        ...same, child3 & 4
    }
}

四分木は通常、それ自体が保存するポイントで分割されないことに注意してください。通常、ポイントとは別に分割座標を保存することによって分割されます (四分木の葉にのみ保存されます)。例については、ウィキペディアの写真を参照してください。

于 2012-07-15T00:40:22.157 に答える