如何迭代Quad/Oct树 [英] How to iterating a Quad/Oct tree

问题描述

我很难掌握如何迭代八叉树或四边形.可能是因为我对不同的迭代神话没有经验.但是，假设我生成了一个四叉树，其中包含浮点数x，y，z； dword颜色.现在，让我们说这个节点一次只能产生4个孩子(这些孩子可以同时产生4个孩子，依此类推)，直到:达到7个级别(这样孩子就不能再创建孩子了，但是兄弟/姐妹可以)，创建的所有4个子代都使用相同的双色(再次，如果发生这种情况，其兄弟/姐妹仍然可以生成)，或者创建的节点总数等于87380.容器.然后该过程继续.

I am having a difficult time grasping how to iterate an octree or quad. And it may be because I am not experienced with different mythologies of iterating. But let’s suppose that I produced a quad tree that holds float x,y,z; dword color. Now, Let’s also say that this node can only produce 4 children at a time (and those children can both produced 4 children, etc, etc) up until: 7 levels are reached (so that child can’t create anymore children, but its brothers/sisters can), all 4 children created are the same dword color (again, if that happens, its brothers/sisters can still produce), or total nodes created are equal to 87380. When the above happens, it is placed into a container. And the process continues.

现在，此保存节点的容器的深度为7层，例如，所有子级的子级的x，y，zs和颜色都不同.我遇到的问题是如何遍历此容器，如何遍历所有孩子，姐妹?由于根导致有4个孩子，而这4个孩子有4个孩子，依此类推，等等，等等:4 ^ 1 + 4 ^ 2 .... + 4 ^ 7.如何在不编写复杂的if语句并遍历整个节点(从根开始)的情况下找到所需的节点?容器(产生节点的容器)是否需要其他代码来简化此过程?

Now this container that holds the nodes is (for example) 7 levels deep, all children of children of children all different x,y,zs, and colors. The problem I am having is how I iterate this container, how can I go through all the children, sisters? Since the root leads to 4 children, and those 4 children have 4 children, etc, etc, etc: 4^1+4^2....+4^7. How can I find the node I want, without writing complex if statements, and iterating over the whole node (starting from root)? Does the container (the one that produces the node) need additional code that allows this process to be simple?

很抱歉，这个问题是笼统的.

Sorry if the question is to general.

推荐答案

遍历整个树很容易，您可以递归进行.

Iterating over the whole tree is easy, you can do it recursively.

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会在四叉树的每个节点上发生.

Then call iterate(root) and the do something will happen on every node in the quadtree.

不过，我怀疑这并不是您真正要问的.如果这就是您要做的一切，那么将数据保留在四叉树中就没有意义了.如果要在四叉树中找到一个特定的节点，则需要其他一些东西.假设您要在四叉树中找到一个点x,y.然后，您将执行以下操作:

I suspect this isn't really what you're asking, though. There'd be no point in keeping your data in a quadtree if that's all you were doing. If you want to find a particular node in the quadtree, then you need something else. Let's say you want to find a point x,y in a quadtree. Then you do something like:

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
    }
}

请注意，四叉树通常不会在自己存储的点上进行拆分，它们通常是通过将拆分坐标与点分开存储(仅存储在四叉树的叶子处)来拆分的.有关示例，请参见维基百科图片.

Note that quadtrees aren't normally split on the points they store themselves, they are usually split by storing the splitting coordinates separately from the points (which are only stored at the leaves of the quadtree). See the wikipedia picture for an example.

这篇关于如何迭代Quad/Oct树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！