Октодерево — тип древовидной структуры данных, в которой у каждого внутреннего узла есть до восьми потомков. Деревья октантов чаще всего используются для разделения трёхмерного пространства, рекурсивно разделяя его на восемь октантов. Каждый узел представляет собой кубическое подмножество 3х мерного объема.
Каждый узел обозначается как:
1) Черный. Если куб полностью принадлежит объекту
2) Белый. Если куб не имеет пересечений с объектом, то есть принадлежит фону
3) Серый. Если куб частично принадлежит объекту. В этом случае узел имеет 8 потомков ( октантов), представляющих собой 8 одинаковых по размеру кубов
Алгоритм построения следующий
1) Сборка начального восьмеричного дерева, содержащего один единственный корневой узел с пометкой "черный"). Этот узел на уровне 0. Установить текущий уровень 0.
2) Все черные узлы текущего уровня находятся в связанном списке. Установить текущий узел первым узлом в списке.
3) Текущий узел проецируется на изображения и определяется его метка (этот метод написан)
4) Если узел отмечен серым , на следующем уровне он порождает восемь потомков, каждый из которых будет черным
5) Если есть еще узлы в списке текущего уровня то переходим к след. Узлу и переходим к шагу 3. Если все узлы текущего уровня обработаны, уровень увеличивается и переходим к шагу 2
6) Процесс продолжается пока не достигнут заданный максимальный уровень
Не могу написать алгоритм рекурсивного построения такого дерева. Пишу на C#, хотя буду рад помощи на любом языке
Структура следующая
Каждый узел обозначается как:
1) Черный. Если куб полностью принадлежит объекту
2) Белый. Если куб не имеет пересечений с объектом, то есть принадлежит фону
3) Серый. Если куб частично принадлежит объекту. В этом случае узел имеет 8 потомков ( октантов), представляющих собой 8 одинаковых по размеру кубов
Алгоритм построения следующий
1) Сборка начального восьмеричного дерева, содержащего один единственный корневой узел с пометкой "черный"). Этот узел на уровне 0. Установить текущий уровень 0.
2) Все черные узлы текущего уровня находятся в связанном списке. Установить текущий узел первым узлом в списке.
3) Текущий узел проецируется на изображения и определяется его метка (этот метод написан)
4) Если узел отмечен серым , на следующем уровне он порождает восемь потомков, каждый из которых будет черным
5) Если есть еще узлы в списке текущего уровня то переходим к след. Узлу и переходим к шагу 3. Если все узлы текущего уровня обработаны, уровень увеличивается и переходим к шагу 2
6) Процесс продолжается пока не достигнут заданный максимальный уровень
Не могу написать алгоритм рекурсивного построения такого дерева. Пишу на C#, хотя буду рад помощи на любом языке
Структура следующая
C++:
class octree
{
public voxel Data; //данные узла(текущий куб)
public octree[] Branchs; //массив из 8 потомков
int level; //уровень
NodeMark mark; //метка узла
}