6. Контрольні запитання та завдання

1. Дайте визначення просторовим об’єктам.

2. Яка геоінформаційна структура даних у ГІС?

3. Наведіть векторну структуру даних.

4. Наведіть растрову структуру даних.

5. Які векторні моделі даних ви можете навести?

6. У яких випадках використовуються векторні моделі даних?

7. У яких випадках використовуються растрові моделі даних?

8. Назвіть найбільш поширені моделі БД та їх особливості.

9. Які формати даних підтримує ГІС?

3 Структури просторових даних гіс

План лекції. Зберігання растрових даних. Ієрархічні структури даних. Алгоритми на квадродеревах. Просторові індекси.

1. Зберігання растрових даних

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

У деяких форматах графічних файлів використовується стиснення зображення, засноване на заміні великих послідовностей повторюваних значень парою <значення, кількість повторів> (рис. 3.1, а). Географічні дані зазвичай автокорельовані. У растровій моделі це означає, що сусідні комірки мають велику ймовірність бути однаковими, ніж різними. При звичайному порядку сканування в кінці кожного рядка відбувається стрибок на початок наступного рядка. Запропонуємо просту зміну порядку сканування: непарні рядки кодувати зліва направо, а парні – у зворотному напрямку (рис. 3.1, б). Напрям сканування нагадує рух бика, що зорює поле, звідси і назва цього способу сканування – Boustrophedon (грец. – бик орав поле). Тепер при переході до нового рядка перша клітинка є суміжною з останньою коміркою старого рядка. Так в лінійному розкладанні растра зберігається автокореляція і підвищується ефективність кодування.

А

А

А

А

А

А

А

А

А

А

В

А

А

А

В

А

А

В

В

В

А

В

В

В

А

В

В

В

А

В

В

В

а) б)

АААААА В АА ВВВ А ВВВ – 16 байт	ААААА В ААА ВВВВВВ А – 16 байт
6А 1В 2А 3В 1А 3В – 12 байт	5А 1В 3А 6В 1А – 10 байт

Рисунок 3.1 – Порядки сканування растрів, їх лінійне розкладання і

стиск: а) звичайний порядок, б) Boustrophedon

Порядок сканування Мортона (названий на ім'я Гая Мортона, вперше цей спосіб було використано у Canada GIS) заснований на ієрархічному розбитті карти. У попередніх способах сканування враховувалася автокореляція значень клітинок тільки по одному напрямку (по рядку). Але, частіш за все, географічні об'єкти утворюють на растровому зображенні плями. У порядку Мортона робиться спроба сканування комірок таким чином, щоб охопити лінією обходу ці двовимірні плями. Для растра розміром 2 x 2 застосовується звичайний порядок сканування. На наступному рівні матриця розміру 4 x 4 складається з чотирьох матриць розміру 2 x 2, розташованих в такому ж порядку, як комірки матриці 2 x 2 (рис. 3.2). Аналогічно формується лінія сканування будь-якої матриці порядку 2n. Матриця формується рівень за рівнем, повторюючи один і той самий шаблон розміру 2 x 2. При скануванні растру за Мортоном лінія сканування є фракталом. Недоліки сканування за Мортоном очевидні. По-перше, присутні скачки, наприклад, від комірки 7 до комірки 8. По-друге, таким способом можна кодувати тільки растри розміру, кратного двом.

Рисунок 3.2 – Порядок сканування растра за Мортоном

При роботі з растровими даними важливим є завдання визначення місця розташування комірки в послідовному файлі за растровими координатами і навпаки. Для звичайного порядку сканування і для Boustrophedon-сканування отримання такого відображення не складає труднощів. При скануванні за Мортоном завдання ускладнюється. Розглянемо приклад, нехай потрібно по растровим координатами комірки A (2,3) визначити її номер у послідовності Мортона. Для цього представимо координати A в двійковій системі числення і на їх основі сформуємо число N так, що координати стовпця ( ) комірки A задають непарні біти N, а координати рядка – парні біти ( ). Число, що вийшло відповідає позиції комірки A в послідовності Мортона. Зворотне завдання вирішується схожим способом. Нехай комірка B записана в десятій позиції послідовності Мортона. Представимо її номер у двійковій системі числення і розділимо парні і непарні біти між растровими координатами стовпця і рядка комірки: . Отримаємо растрові координати комірки A (3, 0).

Розглянемо наступний спосіб сканування, в якому відсутні скачки між комірками. На рис. 3.3 комірки растра скануються по лінії Пеано.

Є базовий П-подібний шаблон, який повертається від рівня до рівня так, щоб забезпечити безперервність лінії сканування.

Рисунок 3.3 – Порядок сканування растра Пеано