Квадротомическая модель данных

Общие положения

Определение 3.12. Квадротомическое представление данных или квадродерево – это модель представления пространственных объектов в виде иерархической древовидной структуры, основанный на декомпозиции пространства на квадратные участки или квадратные блоки (квадранты), каждый из которых делится рекурсивно на 4 вложенных до достижения некоторого уровня – числа Мортона, обеспечивающего требуемую детальность описания объектов, эквивалентную разрешению растра.

Квадротомическое представление данных еще называют «дерево квадратов», «Q-дерево» и «4-дерево».

Обычно модель используется как средство снижения времени доступа к данным в базе пространственных данных. Это средство повышения эффективности обработки и компактности хранения данных по сравнению с растровыми представлениями, является «интеллектуализированным» растром.

В случае 3D-систем используется октотомическое дерево. По сути использование такого дерева является трехмерным групповым кодированием пространственных данных.

Квадротомическая модель используется, в основном, для компактного представления растров, но иногда она применяется и для компактного представления векторных данных. Ниже рассмотрим идею квадротомических деревьев и один из алгоритмов перевода данных в растровом формате в квадротомическое дерево.