Iterative octree traversal

Question

Я не могу определить процедуру для итеративного обхода осцилля, хотя я попытался приблизиться к нему в способе обхода двоичного дерева. Для моей проблемы у меня есть узлы octree, у которых есть дочерние и родительские указатели, и я хотел бы перебирать и хранить только узлы листа в стеке. Кроме того, идет итеративный обход быстрее, чем рекурсивный обход?

Answer 1

Это действительно как обход двоичного дерева, но вам нужно сохранить немного промежуточной информации. Рекурсивный алгоритм не будет медленнее как таковой, но использует немного больше пространства стека для рекурсивных вызовов O (log8) (около 10 уровней для 1 миллиарда элементов в октете). Итерационные алгоритмы также нуждаются в том же объеме пространства, чтобы быть эффективными, но вы можете поместить его в кучу, которую вы боитесь, что ваш стек может переполняться.

Рекурсивный вы могли бы сделать (псевдокод):

function traverse_rec (octree): 
    collect value // if there are values in your intermediate nodes 
    for child in children: 
     traverse_rec (child) 

Самый простой способ достичь итеративного алгоритма является использование стека или очереди на глубину первой или дыхания первого обхода:

function traverse_iter_dfs(octree): 
    stack = empty 
    push_stack(root_node) 
    while not empty (stack): 
     node = pop(stack) 
     collect value(node) 
     for child in children(node): 
      push_stack(child) 

Замените стек очередью, и у вас начался первый поиск дыхания. Тем не менее, мы сохраняем что-то в области узлов O (7 * (log8 N)), которые нам еще предстоит пройти. Если вы думаете об этом, это меньшее зло, хотя, если вам не нужно ехать действительно большие деревья. Единственный способ - использовать родительские указатели, когда вы делаете это в дочернем элементе, а затем вам нужно выбрать следующего брата.

Если вы не храните заранее индекс текущего узла (по отношению к его братьям и сестрам), вы можете искать только все узлы родителя, чтобы найти следующего брата, что существенно удваивает сумму (для каждого узла вы не просто проходите через детей, но также через братьев и сестер). Кроме того, похоже, что вам, по крайней мере, нужно помнить, какие узлы вы уже посетили, поскольку в общем случае неразрешимо, следует ли спускаться дальше или возвращать обратно дерево в противном случае (докажите, что я кто-то не так).

В целом я бы рекомендовал не искать такое решение.

Answer 2

В зависимости от цели. Вы пытаетесь найти, является ли узел видимым, если луч пересечет его ограничивающий прямоугольник или если точка содержится в узле?

Предположим, что вы делаете последнее, проверяя, должна ли точка быть/должна содержаться в узле. Я бы добавил метод к Octnode, который принимает точку и проверяет, лежит ли она в ограничивающей рамке Octnode. Если он возвращает true, else false, довольно просто. Отсюда вы можете вызвать метод сверления, который начинается с вашего головного узла и проверять каждый дочерний элемент, простой цикл «для», чтобы увидеть, в каком Octnode он находится, он может быть не более одного.

Вот где ваш итеративный и рекурсивный алгоритм вступает в игру. Если вы хотите итеративный, просто сохраните указатель на текущий узел и замените этот указатель с головного узла на тот, который содержит вашу точку. Затем просто продолжайте сверлить, пока не достигнете максимальной глубины, или не найдете Octnode, содержащий его. Если вы хотите рекурсивное решение, вы назовете этот метод детализации на Octnode, в котором вы нашли точку.

Я бы не сказал, что итеративный и рекурсивный имеет большую разницу в производительности по скорости, но это может имеют разницу в показателях производительности памяти. Каждый раз, когда вы рекурсируете, вы добавляете еще одну глубину вызова в стек. Если у вас большой Octree, это может привести к большому количеству вызовов, возможно, выдув ваш стек.