Как перебрать дерево Quad/Oct

Мне трудно понять, как повторять октодерево или квадроцикл. И это может быть потому, что я не знаком с различными мифологиями повторения. Но давайте предположим, что я создал дерево квадрантов, которое содержит числа с плавающей запятой x, y, z; цвет двойного слова. Теперь давайте также скажем, что этот узел может производить только 4 дочерних элемента за раз (и эти дочерние элементы могут производить по 4 дочерних элемента и т. братья/сестры могут), все 4 созданных потомка имеют один и тот же цвет dword (опять же, если это произойдет, его братья/сестры все еще могут производить), или общее количество созданных узлов равно 87380. Когда происходит вышеизложенное, он помещается в контейнер. И процесс продолжается.

Теперь этот контейнер, который содержит узлы, имеет (например) 7 уровней глубины, все дочерние элементы дочерних элементов имеют разные x, y, zs и цвета. Проблема, с которой я сталкиваюсь, заключается в том, как я перебираю этот контейнер, как я могу пройти через всех детей, сестер? Поскольку корень ведет к 4 дочерним элементам, а эти 4 дочерних элемента имеют 4 дочерних элемента, и т. д., и т. д., и т. д.: 4 ^ 1 + 4 ^ 2.... + 4 ^ 7. Как мне найти нужный узел без написания сложных операторов if и перебора всего узла (начиная с корня)? Нужен ли контейнеру (тот, который создает узел) дополнительный код, который позволяет упростить этот процесс?

Извините, если вопрос общий.


c++ containers octree quadtree
person User    schedule 15.07.2012    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Итерировать по всему дереву легко, вы можете сделать это рекурсивно.

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

Обратите внимание, что деревья квадрантов обычно не разбиваются по точкам, которые они хранят сами по себе, они обычно разбиваются путем хранения координат разделения отдельно от точек (которые хранятся только в листьях дерева квадрантов). В качестве примера см. картинку из Википедии.

person Keith Randall    schedule 15.07.2012
comment
Вау, это действительно очень помогает. Теперь я полностью понимаю логику таких контейнеров! Это имеет смысл :). Существуют ли другие способы сверхбыстрого поиска точки в дереве или это все? Мне также интересно, если вы убьете узел ветвления, как вы воспитаете одного из его дочерних элементов, чтобы он взял на себя управление? - person User; 15.07.2012
comment
Есть много других способов — см. en.wikipedia.org/wiki/Spatial_index . Удалить узлы непросто, когда у вас есть точки внутри дерева, поэтому большинство людей помещают их только на листья. Но это, вероятно, можно сделать, просто сложно. - person Keith Randall; 15.07.2012