2. Ієрархічні структури даних

Розглянуті вище порядки сканування растрових зображень дають незначні відмінності в стисканні даних. Основна перевага Мортон-сканування та інших ієрархічних структур даних полягає у більш швидкому доступі до даних.

Варто зазначити, що інформація розподілена по карті нерівномірно, тому іноді з’являється потреба у збільшенні або зменшені роздільності растрового зображення. Але треба це робити дуже обережно, тому що збільшення роздільності може призвести до сильного збільшення розмірів файлів, а зменшення – до втрати інформації.

Далі піде мова про адаптивні методи подання растрових даних з різною щільністю інформації. На рис. 3.4 зображена растрова матриця розміру 16 x 16, у якій містяться 255 значень "A" і одне "B". Індексуємо растр наступним чином. Розділимо матрицю на чотири підматриці розміру 8 x 8 і нумеруємо їх 0, 1, 2, 3 в порядку Мортона. Назвемо підматрицю гомогенної, якщо в ній містяться однакові значення. Будемо рекурсивно розбивати негомогенні підматриці до тих пір, поки не досягнемо гомогенності всіх підматриць. Таким чином отримаємо растрове зображення, де ділянки з меншою щільністю інформації представлені великими блоками комірок, а з більшою щільністю – дрібними блоками комірок. Ідея виділення гомогенних блоків растра тотожна кодуванню растра за Мортоном. Гомогенний блок растра розміру при скануванні за Мортоном відповідає коду .

Рисунок 3.4 – Розбиття растра на гомогенні блоки

Відповідність двовимірних растрових координат комірки і адреси клітинки в послідовному файлі схоже на аналогічне перетворення при кодуванні растра за Мортоном. Єдина відмінність в тому, що використовується система числення з основою чотири. У прикладі на рис. 3.4 комірка "B" має код 0311. У двійковій системі числення . Розділимо біти між растровими координатами і з'ясуємо, що комірка лежить в четвертому рядку ( ) і сьомому стовпці ( ).

Представлені таким способом растрові дані відповідають квадродереву, вершина якого – вихідне зображення, а листя – гомогенні блоки комірок. При кодуванні квадродерева комірки на кожному рівні можуть містити або значення гомогенного блоку, або вказівник на наступний рівень. Дерево, показане на рис. 3.4 може бути представлено у вигляді лінійної послідовності (рис. 3.5).

Рисунок 3.5 – Кодування квадродерева

Як вже зазначалося вище, основна перевага ієрархічної організації даних у ГІС полягає в просторовому впорядкування інформації та більш швидкому її пошуку. Тому розглядаються два завдання ГІС, пов'язані з індексацією квадродерева: перша – пошук всіх частин карти із заданим значенням і друга – визначення вмісту деякої комірки. Позначимо n – число рівнів квадродерева (тоді розмір растра 2n х 2n) і через m – число листків у дереві. Щоб знайти частини карти з деяким значенням «B», необхідно перевірити кожен лист дерева, що займе m кроків. Визначення значення комірки відбувається шляхом спуску по квадродереву до тих пір, поки не буде отриманий гомогенний блок. У гіршому разі, коли клітинка знаходиться на самій вершині дерева (як, наприклад, комірка «B» на рис. 3.4), пошук займе n кроків. Порівняємо тепер трудомісткості обох завдань на квадродереві з трудомісткостями цих завдань при різних варіантах сканування растра (табл. 3.1).

Таблиця 3.1 – Трудомісткість алгоритмів при різній організації растрів

Структура даних	Пошук частин із заданим значенням	Визначення значення клітинки
Квадродерево
Звичайний порядок
Boustrophedon
Мортон

Примітка: * – перевіряється кожна клітинка матриці, ** – безпосереднє обчислення позиції клітинки, *** – кількість ланцюжків приблизно відповідає кількості листя, **** – перевіряється кожен ланцюжок.

Існують різні модифікації квадродерев, що дозволяють, наприклад, ефективно індексувати тривимірні дані (при цьому куб рекурсивно ділиться на вісім частин). При кодуванні глобальних даних в проекції Меркатора, представлених в растровій формі, існує проблема різниці у формі та розмірах комірок, що призводить до відхилень в моделі. Проблема може бути вирішена шляхом подання даних в ієрархічній формі. Для цього будується глобальна тесселяція: земна поверхня проектується на октаедр, що містить вісім пронумерованих трикутників. Далі кожен трикутник ділиться на чотири трикутника з'єднанням відрізків середин його сторін. Отримана модифікація квадродерева дозволяє отримувати дозвіл 1 метр при рівні вкладеності дерева, рівному 20.