Зацерковний В.І. та ін. ГІС та бази даних

7.3. Растрові моделі даних на основі нерегулярних мереж

Серед нерегулярних мереж у ГІС застосовуються полігони Тиссена22,

діаграми Вороного, лінійна нерегулярна мережа системи нерівнокутних трикутників.

7.3.1. Полігони Тиссена

Полігони Тиссена (Thiessen polugons, Thiessen polygons) – полігональ-

ні області, що утворюються на заданій множині точок таким чином, що відстань від будь-якої точки області до даної точки менша, ніж для будь-якої іншоїточки множини.

Полігони Тиссена – це багатокутники (полігони), що утворюються навколо множини точкових об’єктів таким чином, що для будь-якої позиції в межах полігонів відстань від центрального точкового об’єкта завжди менше, ніж до іншого об’єкта множини, що розглядається (рис. 7.10).

Полігони Тиссена є зручним інструментом для здійснення просто-

рового аналізу на сусідство, близькість і досяжність.

Рис. 7.10. Полігони Тиссена

Побудова полігонів Тиссена є основою локально-детермінованих методів просторової інтерполяції точкових даних.

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

22Альфред H. Тиссен (8.04.1872–1956) – американський метеоролог, народився в м. Трой штату Нью-Йорк. Отримав ступінь бакалавра в Корнельскому університеті в 1898 р. Працював в Бюро погоди (сьогодні NOAA – Національне управління океанічних і атмосферних досліджень).

Найбільш відомою працею (1911 р.) був опис прогнозу погоди геометричним методом, який зараз носить його ім’я. Полігони Тиссена також використовувалися для оцінки сфер впливу міста держави індійців майя.

241

дійсності. До того ж характер змодельованого просторового розподілу значною мірою залежить від просторового розміщення вузлів мережі. У зв’язку з цим метод рекомендується для інтерполяції точкових значень при:

а) відносно невеликому діапазоні змін даної змінної; б) просторовій однорідності умов формування її поля.

7.3.2. Діаграми Г. Вороного

Завдання побудови зон близькості вперше було поставлене в 1908 р. Георгієм Вороним23.

У ГІС завдання побудови зон близькості часто виникає при розв’я- занні різноманітних задач оптимізації розміщення пунктів обслуговування [19]. Наприклад, потрібно визначити всі точки площини, для яких відстань S до множини об’єктів {ai} є мінімальною.

Припустимо, що є площина, на якій необхідно подати кінцеву множину точок (як мінімум, дві). Ці точки зададуть розбивку площини на області, в кожній із яких будь-яка точка буде більш наближена до виділеної точки. Для двох точок це набуде вигляду – див. рис. 7.11:

Рис. 7.11. Побудова діаграми Вороного двох точок

Границя – серединний перпендикуляр відрізка, з’єднуючого ці точки. Для трьох і чотирьох точок отримаємо (рис. 7.12):

23Вороний Георгій Феодосійович (28.04.1868–20.11.1908) – відомий український математик, визнаний фахівцями як один із найяскравіших талантів у галузі теорії чисел на рубежі ХIХ– ХХ ст. Вороний за своє життя надрукував тільки дванадцять статей. Але вони дали поштовх для розвитку декількох нових напрямків у аналітичній теорії чисел, алгебраїчній теорії чисел, геометрії чисел, які зараз активно розвиваються в багатьох країнах. Сфера застосування його розроблень – від комп’ютерної графіки до геометричного моделювання та створення штучного інтелекту. Сьогодні роботи Г. Вороного використовуються фахівцями різних галузей знань практично в усіх розвинених країнах.

242

Рис. 7.12. Побудова діаграми Вороного: а – для трьох точок; б – для чотирьох точок

Таким чином, будь-яка кінцева множина точок на площині задасть розбивку на області, в кожній з яких будуть знаходитися точки, що лежать ближче до даної точки, ніж до будь-якої іншої.

У загальному вигляді розбивка виглядає як зображене на рис. 7.13.

Рис. 7.13. Побудова діаграми Вороного для множини точок

7.3.3. Трикутні сітки неправильної форми

Трикутні сітки неправильної форми (Triangulated Irregular Network, TIN) – лінійна нерегулярна мережа системи нерівнокутних трикутників

(рис. 7.14).

При побудові TIN-моделі дискретно розташовані точки з’єднуються лініями, які утворюють трикутники. В межах кожного трикутника, поверхня зазвичай подається площиною.

243

Рис. 7.14. Лінійна нерегулярна мережа системи нерівнокутних трикутників

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

TIN-моделі є ефективним засобом збереження й аналізу поверхонь, оскільки дозволяє більш точно моделювати неоднорідні поверхні, які можуть на одних ділянках різко змінювати форму, а на інших – несуттєво, або взагалі не змінювати. Там, де поверхня змінюється різко, можна помістити більше точок, де поверхня змінюється плавно – менше точок.

Нерегулярні мережі володіють більшими перевагами порівняно з регулярними, оскільки за їх допомогою можна відображати характер реальних поверхонь.

TIN-моделі можуть також використовуватись як засіб збереження вхідних даних про поверхню, як і моделі для розв’язку задач на поверхнях у ГІС, надають можливість роботи з 3D-моделями і знайшли широке застосування в задачах моделювання рельєфу.

7.4. Ієрархічні моделі

Ієрархічні моделі є найбільш придатними для відображення ієрархічно організованих растрових зображень. Подання растрової інформації у вигляді декількох пов’язаних внутрішньо рівнів, при якому нижній рівень відповідає вихідному представленню растру, що має розмір N×M елементів, а кожний вище розташований рівень є узагальненням інформації в m комірках нижчого рівня, має назву пірамідального (рис. 7.15).

244

Рівень 0

Рівень 1

Рівень m

Рис. 7.15. Ієрархічні растрові структури даних, подані у вигляді піраміди

Вихідне зображення записується в декількох копіях. Кожна наступна копія має вдвічі меншу розрізненість. І коли растрове зображення необхідно подати на екран у заданому масштабі, обирається копія найближчої розрізненості.

Ієрархічним моделям притаманні два внутрішніх обмеження. Перше обмеження – всі типи зв’язків повинні бути функціональними; друге – структура зв’язків повинна бути деревоподібною. Саме тому ієрархічні растрові структури іноді називають пірамідальними, або деревоподібними.

Наслідком цих обмежень є необхідність відповідної структуризації даних. Через функціональність зв’язків запис може мати не більше одного вихідного запису будь-якого типу, тобто зв’язок повинен мати жорсткий вигляд – 1:n ("один – до багатьох").

Очевидним недоліком ієрархічних моделей є збільшення часу доступу при великій кількості рівнів, тому в ГІС не використовують моделі з великою кількістю рівнів, принаймні більше 10. В той же час ієрархічні моделі доволі ефектно використовуються для складання різноманітних класифікаторів.

Пірамідальна модель – це декілька внутрішньо пов’язаних рівнів таким чином, що кожний нижній рівень складає ¼ від розміру попереднього рівня.

Американські вчені У. Тоблер і З. Чен [19, 61] використали пірамідальну модель при кодуванні даних для всієї поверхні Землі. Одинична вершина на верхньому рівні піраміди (дерева) подає повну поверхню Землі. На 15-му рівні розмір комірки порівняний з тим, що отримують від метеосупутників, на 26-му рівні просторова розрізненність порівняна з розрізненністю аерофотознімків, а на 30-му рівні – це розрізненість сантиметрового масштабу.

У ГІС ORRMIS, розробленій в США для цілей регіонального планування, виділено шість рівнів ієрархії. На верхньому рівні, призначеному

245

для збереження агрегованих даних масштабу біома24 чи континенту, розмір комірок 7,5 х 7,5 хвилин (площа 15606,6 га), на нижньому 10 х 10 м (площа 0,01 га). Число максимальних за розміром комірок – 140, мінімальних – понад 200 млн.

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

Частковим, однак досить часто використовуваним у ГІС, різновидом ієрархічних структур є квадратомічні структури растрових даних, або квадродерева.

Квадратомічні (квадро) дерева (quadtree, Q-tree). Один із способів подання просторових об’єктів у вигляді ієрархічної деревоподібної структури, заснований на декомпозиції простору на квадратні ділянки або квадратні блоки, квадранти (quarters, quads), кожний із яких рекурсивно поділяється на 4 вкладених квадрати, до досягнення певного рівня, що забезпечує необхідну детальність опису об’єктів, еквівалентну розрізненність растру. Квадроструктура описується ієрархічною системою вкладених квадратів.

Квадродерева використовується як простий засіб зменшення часу доступу, підвищення ефективності обробки й компактності даних, які зберігаються будучи "інтелектуалізованим" растром.

Простота витікає з геометричної регулярності розбивки, а ефективність досягається за рахунок збереження тільки вузлів із даними.

Аналогічні деревоподібні структури на зразок трихотомічних дерев (tri tree) можуть будуватися також на множині трикутних елементів моделі TIN. Менш відомі гексотомічні дерева (hextree), засновані на розподілі простору на шестикутники (гексагони). Запропоновані та використовуються розширення квадротономічного простору на багатомірні випадки, в тому числі тривимірний випадок у формі так званого октотомічного дерева або октарного дерева (octatree).

24Біом – термін у екології, яким позначають велике регіональне угруповання рослинних і тваринних співтовариств, адаптованих до регіональних фізичних особливостей навколишнього середовища, клімату та ландшафту. Біом складається із співтовариств, що перебувають у довготривалому стані, а також всіх асоційованих з ними перехідних, ушкоджених і деградованих флори, фауни та ґрунтів. Біоми, крім загальної функціональної класифікації, можуть мати також і місцеві назви. Наприклад, трав’янисті або чагарникові біоми помірного поясу мають назву степ в Азії та Східній Європі, савана або вельд у Південній і Східній Африці, прерія в Північній Америці, аутбек або скреб у Австралії.

246

Квадратомічним деревом називають деревоподібний граф, ступінь вершини кожного вузла якого дорівнює 4, тобто розмір комірки кожного розташованого вище тематичного шару рівно в 4 рази більший за попередній.

Технологія побудови квадратомічного дерева заснована на рекурсивному поділі квадрата на квадранти та підквадранти доти, поки всі підквадранти не стануть однорідними щодо значення зображення (кольору) або поки не буде досягнутий попередньо визначений найменший рівень розрізненості. Спочатку квадрат розміром на всю карту ділиться на чотири квадранти (рис. 7.16).

Якщо один із них виявляється однорідним (тобто містить комірки з одним і тим же значенням), то цей квадрант записується і більше не бере участі в діленні. Кожний із квадрантів, що залишився, знову ділиться на чотири квадранти і перевіряється на однорідність. Всі однорідні квадранти записуються, і кожний з тих, що залишився, знову поділяється та перевіряється.

Рис. 7.16. Ієрархічні растрові структури даних у вигляді квадродерева

Процес поділу триває доти, доки вся карта не буде записана як множина квадратних груп комірок, кожна з яких матиме однакове значення атрибута всередині. Найменшим квадрантом буде найменша комірка растру [19].

Таким чином, особливістю квадродерев є те, що вони дозволяють зберігати й обробляти тільки значущі фрагменти растру. Перехід на нижчі рівні в квадродереві здійснюється лише для просторово неоднорідних комірок певного рівня. Якщо комірка є однорідною, вона кодується на даному рівні.

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

247

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

7.5. Безструктурні гіперграфові моделі

Безструктурні гіперграфові25 моделі обробляють координатні дані у вигляді простих рядків координат без будь-якої структури. У випадку обробки площ спільні границі полігонів завжди вводяться двічі. Прикладом практичного використання цих моделей є збереження в пам’яті комп’ю- тера повних полігонів і векторних ланцюгових кодів.

Приклад гіперграфа V = {v1,v2,v3,v4,v5,v6,v7}, E = {e1,e2,e3,e4} = {{v1,v2,v3},

{v2,v3}, {v3,v5,v6},{v4}}, де V – непорожня множина об’єктів певної природи, що називаються вершинами гіперграфа, а E – родина непустих (необов’язково різних) підмножин множини V, що називаються ребрами гіперграфа, представлено на рис. 7.17 [88].

Рис. 7.17. Приклад гіперграфа

Гіперграфові моделі засновані на теорії множин і використовують шість абстрактних типів даних: "клас", "атрибут класу", "зв’язок класу", "об’єкт", "атрибут об’єкта", "зв’язок об’єкта".

Клас відповідає границі гіперграфа, причому об’єкти є вузлами цього графа. Кожний клас містить об’єкти з атрибутами об’єкта і розрізнюваний вузол, який містить атрибут класу. Використовуючи підкласи, вводять ієрархію класів.

Зв’язки класів і зв’язки об’єктів встановлюють співвідношення між тими класами, які не пов’язані ієрархічно. Зв’язки класів відображають потенційні співвідношення між класами, а зв’язки об’єктів – дійсні співвід-

25Гіперграф – узагальнений вид графа, в якому кожним ребром можуть з’єднуватися не тільки дві вершини, а й будь-які підмножини вершин.

248

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

Гіперграфові моделі можуть застосовуватись як для координатних, так і атрибутивних даних. Зазвичай, вони відрізняються високим ступенем складності.

7.6. Решітчасті моделі

Решітчасті моделі базуються на математичній теорії решіток, яка оперує частково упорядкованими наборами даних. Їх доцільно використовувати у тих випадках, коли відсутня чітка ієрархія об’єктів.

Елементи алгебраїчної теорії автоматних моделей синтезу типових конструктивних моделей дозволяють спростити процес отримання складних графічних зображень. Однак такий підхід, що широко застосовується в САПР, поки що не найшов широкого застосування в технологіях ГІС.

7.7. Джерела даних для растрових моделей

Перетворення растрових даних у цифровий вигляд відбувається шляхом їх сканування. Джерелами растрових даних для растрової моделі можуть слугувати:

–фотозображення (image): аерота космічні знімки території, фотографії об’єктів;

–креслення, малюнки;

–топографічні карти; плани; схеми;

–конвертування з триангуляційних даних,

–растеризація векторних даних;

–тексти: документи; таблиці.

7.8. Характеристики растрових моделей

Растрові моделі характеризуються розрізненістю, орієнтацією, зна-

ченням (форматом запису), зонами, місцем розташування, геометрією растрів, координатами комірок, топологією комірок.

7.8.1. Розрізненість

Розрізненість растрових моделей – величина, що відповідає мінімальним лінійним розмірам об’єкта, який може бути відображений у даній моделі та відображується одним пікселем.

249

Треба відрізняти розрізненість графічного файлу, яка наводиться в пікселях (точках) на дюйм (dot per inch), наприклад, 300 dpi, 600 dpi, і картографічну розрізненість (у пікселях на метр). Точність відповідності растрового об’єкта реальному просторовому об’єкту залежить від кількості пікселів, якими цей об’єкт представлений.

Примітка. Розрізненість у пікселях на метр по-різному може обчислюватись на зарубіжних і вітчизняних знімках, оскільки існують різні критерії обчислення точок на знімку.

Розрізненість растрового зображення залежить від розміру комірок. Чим вища розрізненість, тим більшу кількість пікселів містить зображення і, відповідно, менший розмір має кожний окремий піксель. Як наслідок, зображення з більш високою розрізненістю характеризується більшою кількістю деталей, більшою кількістю комірок, меншими розмірами комірок. Проте зменшення розміру комірки растрової моделі істотно збільшує об’єм даних, що зберігаються в комп’ютері, що відповідно вимагає більшої пам’яті комп’ютера. Наприклад, розрізненість 100 метрів означає, що об’єкти, розмір яких не перевищує 100 м у даній моделі, відображені не будуть, тобто зіллються з фоном. Оскільки за певних масштабів відображення фігури будуть нерозрізнені, то при створенні картографічної продукції важливо співвідносити масштаб планованої вихідної продукції і масштаб (реальну детальність) використовуваних растрових даних.

Ще один приклад. Коло може бути представлено 4 пікселями, а може бути представлено 1000 пікселями. Ні в першому, ні в другому випадку це зображення реальним колом не стане, але в другому випадку формально буде більш адекватно описувати реальний об’єкт.

Для різних задач використовуються різні розміри комірок (растри різної розрізненості). Наприклад, для дослідження використання землі (землі промисловості, землі багатоповерхової, середньоповерхової або малоповерхової забудови, землі рекреації) можуть бути використані комірки розміром 10х10 м, а для відображення ґрунтів – 50х50 м, для управління землекористуванням області – 5х5 км. Більш високу розрізненість має растр із меншим розміром комірок (рис. 7.17).

Рис. 7.17. Відображення географічного об’єкта різною просторовою розрізненістю: а – низька розрізненість; б – середня розрізненість; в – висока розрізненість

250