Неявное k-d дерево
-
Определение неявного k-d дерева
- Неявное k-d дерево определяется неявно над прямолинейной сеткой
- Положения и ориентации плоскостей разделения задаются рекурсивной функцией разделения
- Плоскость разделения каждого внутреннего узла разделяет сетку узла на две подсети
-
Номенклатура и ссылки
- Термины «минимальное/максимальное k-d дерево» и «неявное k-d дерево» иногда путают
- В первой публикации использовались явные минимальные/максимальные k-d деревья, но назывались «неявными»
- Введены неявные k-d деревья для применения в компьютерной графике
-
Строительство
- Неявные k-d деревья не создаются явно
- Ориентация и положение в плоскости разделения вычисляются с помощью функции разделения
- Различные функции разделения могут создавать разные деревья для одной сетки
-
Разделение функций
- Невырожденные функции разбиения не создают вырожденные узлы
- Полные функции разбиения создают полные неявные k-d деревья
- Функция разделения медианы сетки создает сбалансированные деревья
-
Присвоение атрибутов неявным узлам
- Неявные k-d деревья не требуют явного сохранения ориентации и положения разделенной плоскости
- Внутренние узлы могут иметь дополнительные атрибуты, такие как биты или скалярные значения
- Для полных неявных k-d деревьев можно предварительно выделить массив атрибутов
-
Приложения
- Неявные деревья max-k-d используются для построения изоповерхностей/MIP
- Неявное минимальное/максимальное kd-дерево используется для оценки видимости на местности
-
Сложность
- Присвоение атрибутов узлам требует O(kn) времени и O(n) памяти
- Лучевое преобразование iso-поверхностей занимает O(log(n)) времени