Растрові структури даних

Однією з найпростіших структур даних є растрова або коміркова організація просторових даних. У растрі значення параметра або властивості, що нас цікавить (наприклад, висота над рівнем моря, клас землекористування, біомаса водоростей у гр/м3), існує для кожної комірки, як правило, у регулярному масиві над простором. Наприклад, висота у метрах над рівнем моря представлена середньою висотою у регулярній комірці.

Прості растрові структури

Хоч проста растрова структура і популярна, але має принаймні два обмеження:

· на здатність визначення місцезнаходження - можна знаходитись лише в комірках - між ними нічого нема, причому межі комірок недостатньо тонкі;

· просторове сусідство: комірки, що розділяють сторони, у середньому ближчі одна до одної, ніж діагональні.

Визначення. Геометричні фігури, які повністю покривають частину простору, називаються мозаїками.

Растрові множини даних на практиці дуже великі. Наприклад, дані дистанційного зондування часто використовують для визначення типів ґрунтів на значних територіях. Стандарт U.S. Landsat ==30000 кв. км, що при номінальному розмірі піксела 30 метрів відповідає приблизно 35 млн. растрових комірок або пікселів (pixels. Pixel - скорочення "picture element").

Для роботи з такими великими множинами даних треба використовувати алгоритми компресії даних. Деякі з них зворотні. Інші мінімізують об`єм, втрачаючи деяку кількість інформації. Наведемо два методи, що допускають відновлення.

Кодування довжин прогону

Кодування довжин прогону (run length encoding - RLE) використовує той факт, що деякі множини даних мають великі однорідні області.

111 333 2 333 333 333 - 16 елементів

(3 1) (3 3) (1 2) (9 3) - 8 елементів

У наведеному прикладі ступінь компресії - 2 рази.

Для бінарних даних [ Burrough ] наводить інший приклад RL Coding, де у рядку зберігається позиція комірки, у якій починаються (перемикаються) прогони.

Ланцюгове кодування

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

Це має важливе значення, якщо нас цікавлять об`єкти.