H Октодерево. Что это такое и для чего применяется в черновиках Из песочницы

Я хочу рассказать о такой структуре данных, как октодерево и для чего оно применяется. Так же приведу простую реализацию на C++.

Теория

Октодерево — древовидная структура данных, представляющая собой дерево, которое может иметь не более 8 потомков (причем для каждого из потомков верно утверждение, что его размеры в 2 раза меньше предка). Еще она позволяет эффективно хранить точки, которые находятся близко относительно друг друга в пространстве. В 2D случае аналогом октодерева является квадродерево.

Если это визуализировать, то выглядеть это будет так:

В чем заключается эффективность?

• С точки зрения разработчика, благодаря этой структуре данных, мы можем хранить XYZ координату за 3 байта вместо 12.(в большинстве языков float занимает 4 байта);
• Точки упорядоченны по поддеревьям. Следовательно поиск наименьшего поддерева, содержащего искомую точку, выполняется за О(logN) (N — количество узлов).

Как достичь эффективного хранения точек?

1. Зададим размеры корня дерева по xyz осям.(size);
2. Для каждого из деревьев определим его уровень в нашей иерархии. Отлично, теперь мы можем вычислить размеры любого поддерева;
3. Теперь для корня установим вектор к (0;0;0) точке его внутренней системы координат (offset). Так же для каждого из потомков получим его номер от 0 до 7. Зная вектор корня и номер относительно предка, мы можем выполнить эту операцию для всех поддеревьев (об этом чуть позже);
4. Есть некий байт. Как его преобразовать в координату по некой оси?
   
   coord = (size / 255.0 * byte) + offset;

   Выводы из формулы:
   
   • Присутствует погрешность. Чем меньше size, тем меньше погрешность;
   • На данном уровне нельзя хранить точки, расстояние между которыми по каждой из координат меньше size / 255.0.

Практика

Опишем структуру поддерева:

struct Tree{
     Tree* parent; // Предок
     Tree* childs[8]; // Потомки
     uint8_t blockNum,level; //Номер по отношению к предку и уровень
     float offset_x,offset_y,offset_z; // Offset вектор
     std::vector<std::array<uint8_t,3>> bytes; // Точки
};

Теперь нам достаточно хранить:

     Tree* root; // Корень дерева
     std::vector<std::array<float,3>> sizes; // Размеры граней

Кульминация. Получение offset по parent:

void setOffset(Tree* cur){
      /* Изначально смещение относительно начала координат равно смещению предка */
      float dx = parent->offset_x, dy = parent->offset_y, dz = parent->offset_z;
      /* Далее в зависимости номера блока смещаем его x,y,z осям */
      if (cur->blockNum && 1) dx += sizes[cur->level][0];
      if (cur->blockNum && 2) dy += sizes[cur->level][1];
      if (cur->blockNum && 4) dz += sizes[cur->level][2];
      cur->offset_x = dx,cur->offset_y = dy, cur->offset_z = dz;
}

Ну и получение координат точки:

std::array<float,3> transform(std::array<uint8_t,3> bytes,Tree* cur) {
      std::array<float,3> res;
      res[0] = (sizes[cur->level][0] / 255.0 * bytes[0]) + cur->offset_x;
      res[1] = (sizes[cur->level][1] / 255.0 * bytes[1]) + cur->offset_y;
      res[2] = (sizes[cur->level][2] / 255.0 * bytes[2]) + cur->offset_z;
      return res;
}

Заключение

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