1.2. Ієрархічні растрові структури

Таке представлення називається квадродеревом, оскільки 4 комірки замінюються на 1.

Tobler, Chen обговорюють модифіковану квадросистему для кодування поверхні Землі. Єдиний вузол на вершині представляє всю планету. На 15-му рівні резолюція комірок порівняна з метеорологічними супутниками. На 26-му рівні просторова резолюція порівняна з більшістю аерофотознімків. 30-й рівень - 1-см резолюція, яка підходить для геодезичних контрольних точок для широкого вжитку.

Розглянемо растр з 32 пікселів в стороні. Цей растр вимагає 1024 комірки зберігання. Якщо ми включимо вищі рівні, тоді всього 1365 комірок. Тобто, кількість комірок збільшилась на 33%.

Але цей недолік у деяких застосуваннях не відіграє важливої ролі. Наприклад, коли не потрібна повна резолюція.

Q-дерево - яскравий приклад звичайної проблеми застосувань СУБД: протиріччя вартість зберігання даних - вартість обробки.

Ієрархічна природа q-дерева дозволяє скоротити деякі пошуки. Наприклад, пошук високих точок (але не найвищих). Зауважимо, що відразу відсікається 75% даних на кожному кроці. При пошуку найвищої точки треба продивлятись увесь шар.

Навіть зберігаючи по одному значенню даних в кожному вузлі, за допомогою q-дерева можна ефективно здійснювати дуже специфічні пошуки. Звичайно, такі можливості підсилюються, оскільки ми можемо зберігати у кожній комірці 3 величини: середнє по області, мінімум та максимум. Пошук тоді здійснюється для всього регіону дуже швидко. Але є додаткові витрати на зберігання.

Модифікація q-дерева - представлення максимального блоку (maximum block representation).

Проблеми q-дерева у тому, що вони не є інваріантними (незмінними) відносно зсуву, повороту та масштабу.

Приклад.

Оригінальний растр і q-дерево

Перенесені растр і q-дерево

Що відбувається при переносі об’єкта на один проліт на схід? Він міг би представляти інший

об’єкт того ж типу та розміру, але в іншому місці. Існують деякі спроби вирішення цієї проблеми. Scott и Iyengar запропонували систему, яка базується на наступному:

1. знаходження однорідних кв. регіонів у растрі;

2. кодування розміру блоку і координат верхнього лівого кута блоку.

2. Векторні структури даних

Визначення. Вектор - величина з початковою точкою, асоційованим з нею зсувом та напрямком.

Векторні структури даних базуються на елементарних точках, розташування яких відоме. Замість прикладу розглянемо зберігання кола. В одній із зазначених растрових СД необхідно знайти й закодувати усі растрові комірки (визначеної форми й розміру), місцезнаходження яких відповідає границі кола. Це може бути названо низькорівневим описом кола. Опис вищого рівня, з другого боку, може ефективно зберігати коло, записуючи розташування точки для центру й радіуса кола. Зауважимо, що векторне зберігання менш витратне, якщо ми можемо вказувати геометричний об`єкт коло. Ці переваги можуть зникнути, якщо ми зберігаємо коло як зв`язану послідовність прямолінійних сегментів.

У більшості ГІС координати даних кодуються й зберігаються, як деякі комбінації точок, ліній, площ та полігонів. Декілька видів векторних СД знаходяться у загальному користуванні, замість засобів представлення БД всередині ГІС, так і замість стандартів обміну даними між системами. Це:

1. (цілісна) непросіяна полігональна структура (whole polygon structure),

2. подвійне незалежне кодування карт (Dual Independent Map Encoding (DIME)) файлова структура,

3. дуга-вузол (arc-node) структура,

4. реляційна (relational) структура,

5. цифрові лінійні графіки (digital line graphs або DLG).