Формирование октодерева по облаку точек при ограничении объёма оперативной памяти

Лазерное сканирование – современный и активно развивающийся метод дистанционного зондирования. Результат лазерного сканирования представляет собой облако точек, которое кроме координат каждой точки может содержать цвет точки и другие атрибуты. Одной из особенностей технологии лазерного сканирования, обусловившей её популярность, является возможность получения достаточно плотного облака точек, что определяет высокую точность цифрового представления геометрии объекта сканирования. В некоторых случаях облака точек могут содержать миллиарды точек, для хранения которых необходимы сотни гигабайт. Загрузка и обработка таких колоссальных объёмов данных требует больших временных и вычислительных ресурсов. Распространенным подходом является построение октодерева для ускорения операций пространственного поиска и группировки близких в пространстве точек. Использование такого октодерева совместно с внешней памятью открывает возможность ограничения объёма потребляемой оперативной памяти. В статье представлен метод построения октодерева с использованием двухуровневой системы кеширования участков облака точек. Предложены способ организации процесса построения структуры данных и способ анализа эффективности метода с помощью вычислительного эксперимента. Приведены результаты анализа эффективности предложенного метода.