Обход дерева квадрантов

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

Может ли кто-нибудь указать мне в правильном направлении?


c++ iterator tree quadtree
person Matt Mils    schedule 03.02.2012    source источник

Ответы (3)


arrow_upward
4
arrow_downward

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

person Pochi    schedule 03.02.2012
comment
Так просто так хорошо! Как же я не додумался это сделать. Теперь, кстати, я столкнулся с проблемами с узлами с одним из индексов, равным его родителю. Кажется, мне нужно изменить правила вставки или что-то в этом роде. Есть идеи? - person Matt Mils; 04.02.2012

arrow_upward
3
arrow_downward

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

Простые и эффективные методы обхода деревьев квадрантов и октодеревьев

person hatboyzero    schedule 03.02.2012
comment
Я быстро попробовал эту бумагу, прежде чем спрашивать. Может быть, это было слишком быстро. - person Matt Mils; 03.02.2012

arrow_upward
2
arrow_downward

Это моя реализация в javascript: https://github.com/alexroat/quadtree-traversal

Существует наглядная демонстрация, которая показывает поведение алгоритма.

person alexroat    schedule 05.09.2015