Настройка
Допустим, у нас есть куб в 3D, который описывает пространство. Мы подразделяем этот куб на 8 различных меньших кубов, которые описывают восьмую часть пространства, и мы продолжаем делать это несколько раз.
Это дерево, где корень - это полный пробел, а каждый дочерний узел - это подраздел более высокого уровня подразделения до максимального разрешения.
т.е. первый уровень - это полный пробел, следующий - 8 подпространств, следующие 64 подпространства ... до 8 ^ n подпространств.
Каждый из этих узлов может существовать в одном из двух состояний, занятом или пустом. Пустые узлы не имеют дочерних узлов, у занятых узлов есть хотя бы один непустой дочерний элемент, если они не являются листом.
Задача
Мне дан массив с самым низким уровнем разрешения (наименьшие подпространства, т.е. листья). Этот массив содержит дискретизированные (x, y, z) координаты занятых листьев. Другими словами, в этом массиве существуют только занятые листья, пустые листья явно не заданы, поэтому, если лист не найден в этом массиве, мы можем считать его пустым.
Информация не указана в каком-либо определенном порядке, но каждый лист сам идентифицирует свое положение в трехмерном пространстве по своей координате (x, y, z).
Используя эту информацию, мы хотим построить описанное дерево. Другими словами, мы хотим создать октавное дерево, в котором пустые листья не имеют дочерних элементов.
Как мне эффективно построить упомянутое дерево?