Зацерковний В.І. та ін. ГІС та бази даних. І бази даних
 Скачать 31.1 Mb.
|
|
8.6. Поняття про топологічні відношення в ГІС Співвідношення між елементами векторних даних у термінах розташу- вання і з’єднання відомі як топологічні відношення 31 . Теоретичною основою топологічних моделей служать алгебраїчна топологія і теорія графів. 31 Напрямок математики, відомий як топологія, виник у 1736 р., коли математик Леонард Ейлер опублікував статтю, де розглянув задачу, названу ним "Сім мостів Кенігсберга". Власне термін "топологія" ("topologie" німецькою мовою) вперше з’явився лише в 1847 р. у статті Лістінга Vorstudien zur Topologie. Однак на той час Лістінг уже понад 10 років вико- ристовував цей термін в своїх листуваннях. "Topology", англійська форма терміна, була запропонована в 1883 р. в журналі Nature для того, щоб розрізнити якісну геометрію від геометрії звичайної, в якій превалюють кількісні співвідношення. Слово topologist – тобто тополог, у значенні "спеціаліст з топології", було вперше використано в 1905 р. в журналі 283 Топологія – це розділ математики, що вивчає ідею безперервності. Безперервність – це одна з фундаментальних властивостей категорії "простору-часу". Топологія вивчає просторові відношення, які не зміню- ються при взаємно однозначних і взаємно безперервних перетвореннях. Топологія реалізується математичною процедурою явного визна- чення просторових відношень. Топологія надає векторним даним "інтелектуального" рівня. Це означає, що ГІС спроможна розпізнавати, який сегмент з яким з’єднаний, та ідентифікувати полігони, що межують з певним об’єктом. Топологічні властивості фігур не змінюються при будь-яких деформа- ціях, що відбувається без розривів або з’єднань. На рис. 8.17 представлені то- пологічно-родинні фігури: прямокутний чотирикутник, квадрат, коло, еліпс. Рис. 8.17. Топологічно-родинні фігури Так, коло, еліпс, контур квадрата і контур прямокутника мають одні й ті ж топологічні властивості, оскільки ці фігури можуть бути трансформовані одна в одну. Як відомо, ГІС займаються відображенням (моделюванням) метрич- них просторів. Причому виконується це на площині – також метричному просторі. Великомасштабні карти, відображаючи площину, відображають "площину ділянки земної поверхні – площину карти", а дрібномасштабні – "сферичну поверхню (еліпсоїд, геоїд) – площину карти". Дійсно, якщо зобразити карту на плоскій гумі, а потім розтягти її в різних напрямках, то фігури (картографічні зображення) деформуються, але відношення (зв’язки) між елементами залишаться без змін; суміжні лінії різних фігур, зв’язані своїми кінцями з іншими елементами, так і залишаться зв’язаними при деформуванні. Змінюються лише форми ліній. Саме тому й ствер- джують, що коло, еліпс і контур квадрата мають одні і ті ж топологічні властивості, при їх деформаціях можна розтягти ділянки гуми таким чином, що навіть квадрат перетвориться на коло. Інший приклад. Уявіть "повітряну" конструкцію, яка складається з паличок, з’єднаних кінцями між собою (на кінцях паличок є гачки для зчеп- лення). Якщо з ними виконати певні маніпуляції, то конструкція внаслідок зв’язаності кінців паличок залишиться цілісною: форма її зміниться, але кожна паличка, якщо вона була зв’язана з конкретними сусідами, так і Spectator. Завдяки впливу згаданих вище статей Пуанкаре топологія тривалий час була відома ще під назвою Analysis Situs (лат. аналіз місця). 284 лишиться з ними зв’язаними, як би не підкидали або не стискали таку конструкцію. Конструкцію зі зв’язаних паличок можна розмістити на пло- щині. При переміщенні паличок за ними зміщуються і сусіди (гачки не дають відірватися). Все це зумовлено наявністю жорстких зв’язків між кінцями паличок, оскільки створена топологічна конструкція. Тепер наведемо приклад нетопологічних конструкцій. Кільце і коло мають різні топологічні властивості: коло обмежене одним контуром, а кільце – двома. Також можна взяти окремі сірники і скласти з них конструкцію на площині. Конструкція може бути такою за формою, як у прикладі зі скріпленими між собою паличками. Однак можна взяти будь-який сірник і перемістити його. Оскільки він фізично не скріплений з сусідами, то зробити це можна досить легко, не зачепивши сусідні сірники. В такому разі кажуть, що сірники не утворюють топологічно зв’язану конструкцію з іншими сірниками. Конструкція легко розсипається, якщо стукнути по площині, на якій розмістили конструкцію. Навпаки, в прикладі зі скріпленими між собою паличками після струшування може змінитися форма конструкції, але зв’язки між сусідами збережуться. Необхідна процедура при роботі з топологічною моделлю – підго- товка геометричних даних для побудови топології. Цей процес не може бути повністю автоматизований вже на даних середньої складності і реалізується тільки при додаткових витратах праці, зазвичай істотних. Таким чином, дані, які зберігаються в системі, що не передбачає підтримки топології, не можуть бути належно перетворені на топологічні дані іншої ГІС за суто автоматичним алгоритмом. Топологічні характерис- тики повинні обчислюватись у ході кількісних перетворень моделей об’єк- тів ГІС, а потім зберігатися в базі даних спільно з координатними даними. 8.7. Характеристики топологічних моделей Для аналізу топологічних зв’язків між об’єктами можуть застосо- вуватись такі топологічні характеристики: – зв’язаність – контури, дороги та інші вектори повинні зберіга- тися не як незалежні набори точок, а як взаємопов’язані один з одним об’єкти. Зв’язаність і прилягання районів – інформація про взаємне розташування районів і про вузли перетинання районів (рис. 8.18); – сусідство (близькість) – наприклад, для полігональних – два зображення будівель, які стоять поруч, для лінійних – зображення річки і розташованої поруч із річкою дороги. Близькість – показник просторової близькості лінійних або ареальних об’єктів (рис. 8.19), оцінюється числовим параметром, у даному випадку параметром δ; 285 Рис. 8.18. Зв’язаність і прилягання районів Рис. 8.19. Оцінка близькості об’єктів Рис. 8.20. Тривалентне (ліворуч) і чотиривалентне (праворуч) перетинання – перетинання – наприклад, зображення двох комунікацій, які перетинаються. Інформація про типи перетинань дозволяє відтворювати мости і дорожні перетинання (рис. 8.20). Так, Т-подібне перетинання (3 лінії) є тривалентним, Х-подібне (4 лінії сходяться в точці перетину) називають чотиривалентним перетинанням. Валентність вузла – спеціальна (топологічна) характеристика вершини вузла мережі (сітки), яка визначається кількістю ланок у ній. Кінці відособлених ліній одновалентні (валентність дорівнює 1). Для вуличних мереж перетинання типу перехрестя характерними є чоти- ривалентні вузли, тривалентні вузли характерні для мережі річок. Різновидом мережі є деревоподібна структура або дерево, що має тільки один шлях між парами вузлів. Більшість річкових мереж є деревами; – суміжність – наприклад, для полігональних об’єктів – зобра- ження двох суміжних будівель, для лінійних – зображення річки та межі, яка проходить по одному з берегів; – еквідистантне сусідство – наприклад, дві будівлі, розташовані паралельно одна до одної, або паралельно розташовані залізниця і шосе; – вкладеність – наприклад, зображення острова, вкладеного в зо- браження озера; – накладення – наприклад, для полігональних – зображення стінного репера, накладеного на зображення будівлі, для лінійних – зображення наземних і підземних комунікацій; – прилягання – наприклад, зображення двох прилеглих ділянок русла річки, що мають різні семантичні характеристики. Топологічні характеристики лінійних об’єктів можуть бути пред- ставлені візуально за допомогою зв’язаних графів. Граф зберігає структу- ру моделі з усіма вузлами і перетинами. Він нагадує карту з перекрученим масштабом. Прикладом такого графа може служити схема метрополітену. Різниця між картою і схемою метро показує різницю між картою і графом. Вузли графа, що описують картографічну модель, відповідають перетинам доріг, місцям стикування доріг із мостами тощо. Ребра такого 286 графа описують ділянки доріг і об’єкти, які їх з’єднують. На відміну від класичної мережної моделі, в даній моделі довжина ребер може не мати інформативного навантаження. Топологічні характеристики ареальних об’єктів можуть бути представлені за допомогою графів покриття і суміжності. Граф покриття є топологічно гомоморфним контурній карті відповідного району. Ребра такого графа описують межі між районами, а його вузли (вершини) представляють точки змикання районів. Ступінь вершини такого графа – це число районів, які в ній змикаються. Граф суміжності – це начебто виверну- тий навиворіт граф покриття. В ньому райони відображаються вузлами (вершинами), а пари районів, що змикаються, – ребрами. Такий граф ГІС дозволяє визначити, чи є прохідною розглянута територія, чи поділяється вона на прохідні та непрохідні ділянки. Топологічні характеристики супроводжуються позиційною й описовою інформацією. Вершина графа покриття може бути доповнена координатними точками, якими змикаються відповідні райони, а ребрам приписують лівосторонні та правосторонні ідентифікатори. Після введення точкових об’єктів при побудові лінійних і площин- них об’єктів необхідно створити топологію. Ці процеси передбачають обчислення і кодування зв’язків між точками, лініями й ареалами. Перетинання і зв’язки мають векторне представлення. Топологічні характеристики заносяться при кодуванні даних у вигляді додаткових атрибутів. Цей процес здійснюється автоматично у більшості ГІС у про- цесі дигіталізації картографічних або фотограмметричних даних. Зазвичай, об’єкти пов’язані між собою. Це визначає ефективність застосування реляційних моделей і баз даних, у яких використовується поняття "відношення". В свою чергу, відношення задають множину зв’яз- ків. Найпростіші приклади таких зв’язків: "найближчий до…", "пере- тинає", "з’єднаний з…" Кожному об’єкту можна визначити ознаку, яка являє собою іденти- фікатор найближчого до нього об’єкта такого ж класу, таким чином кодуються зв’язки між парами об’єктів. У ГІС часто кодуються два типи зв’язків: – зв’язки в мережах; – зв’язки між полігонами. Мережі топологічно складаються з об’єктів двох типів: ліній (ланки, грані, ребра, дуги) і вузлів (вершини, перетинання, з’єднання). Найпрос- тіший спосіб кодування зв’язків між ланками і вузлами полягає в при- своєнні кожній ланці двох додаткових атрибутів – ідентифікаторів вузлів на кожному кінці (вхідний вузол і вихідний вузол). У цьому випадку при кодуванні геометричних даних використовуються два типи записів: 287 1) координати дуг: (x 1 , y 1 ), (x 2 , y 2 ), …(x n , y n ); 2) атрибути дуг: вхідний вузол, вихідний вузол, довжина, описові характеристики. Така структура дозволяє, переміщуючись від ланки до ланки, визначати ті з них, у яких перекриваються номери вузлів. Більш складна, але й більш досконала структура має список усіх ланок для кожного вузла. Це може бути виконано доданням до перших двох записів запису третього типу: 3) вузол (x, y), суміжні дуги (зі знаком "+" для вхідного кута і зі знаком "–" для вихідного). Щоб уникнути незручностей, пов’язаних зі збереженням неодна- кової кількості ідентифікаторів дуг, використовують два окремі файли: – простий упорядкований список, у якому файл вузлів стиснутий до ряду ідентифікаторів дуг; – таблицю, в якій для кожного вузла зберігається інформація про накладання першої дуги списку [56]. 8.8. Топологічні моделі сучасних ГІС 8.8.1. Опис топологічної інформації Сучасне математичне забезпечення ГІС засноване на топологічних моделях, які дозволяють ефективно формалізувати подання про просто- рові відношення між основними об’єктами карти. Топологія в ГІС – це процедура визначення просторових зв’язків (сусідства) об’єктів. Формування топології включає визначення і кодування взаємо- відносин між точковими, лінійними і полігональними об’єктами. У топологічному шарі в процесі його створення і редагування створю- ються і фіксуються як самі просторові об’єкти, так і просторові відношення між зазначеними об’єктами, які контролюють цілісність об’єкта. Термін "топологічний" означає, що в моделі об’єкта зберігаються взаємозв’язки, які розширюють використання даних ГІС для різних видів просторового аналізу. Завдяки своїм властивостям топологічні моделі забезпечують розв’язання просторових задач, наприклад, відповісти на питання: "Що знаходиться поруч?", "Що потрапить у полігони даних типів?", "Які від- різки ліній необхідно включити в маршрут" тощо. Крім того, якщо кожен графічний елемент буде пов’язаний з певною атрибутивною інформацією у форматі звичайної бази даних, тоді, позначивши об’єкт на карті, можна буде визначити його характеристики. 288 Топологічні моделі дозволяють представляти елементи карти і всю карту у вигляді графів. Топологічна інформація описується набором вузлів і дуг. Вузол (node, junction) – початкова (beginning point, start node) або кінцева точка (ending point, end node) дуги у векторно-топологічному поданні (лінійно-вузлової моделі) просторових об’єктів типу лінії або полігона; списку або таблиці. Вузли містять атрибути, що встановлюють топологічний зв’язок з усіма дугами, що замикаються на ньому. Кожний вузол з’єднується прямою лінією, яку називають сегмен- том або дугою. Відрізок спільної межі між двома точками має різні назви, які є синонімами у предметній галузі ГІС. Наприклад, спеціалісти з теорії графів надають перевагу терміну ребро над терміном лінія, а для точок (перетинань) використовують термін вершина. Згідно з національ- ним стандартом США, офіційним є термін ланцюг (chain). У деяких ГІС, наприклад в ArcInfo, та графічному редакторі GorelDraw використо- вується термін дуга. Поняття дуги (ланцюга, ребра) є фундаментальним для векторних ГІС. Дуга (аrc, link) – 1. послідовність сегментів, що мають початок і кінець у вузлах; елемент (примітив) векторно-топологічних (лінійно- вузлових) подань лінійних і полігональних просторових об’єктів; 2. кри- ва, що описується відносно множини точок деякими аналітичними функціями. Графічне зображення дуг і вузлів представлене на рис. 8.21. Рис. 8.21. Графічне зображення дуг і вузлів Площі, лінії і точки описуються межами й вузлами (дугова / вузлова структура). Кожна межа йде від початкового до кінцевого вузла і надає можливість визначити, які площі знаходяться ліворуч і праворуч. 289 Існує декілька видів топологічних відношень. Необ’єктні топології, "внутрішньооб’єктні" і "міжоб’єктні" лінійно-вузлові топологічні від- ношення. "Об’єкт" у лінійно-вузлових ГІС і в об’єктних ГІС – це дещо різні поняття, тому вони взяті в лапки. Об’єктні топології: – внутрішньооб’єктні топологічні відношення; – міжоб’єктні топологічні відношення: • вузлові топологічні відношення; • міжоб’єктні топологічні відношення в межах одного шару; • міжшарові топологічні відношення між об’єктами; • топологічні міжоб’єктні ресурсні зв’язки; – концептуальні топологічні відношення (відношення між класами об’єктів, а не між екземплярами); – псевдотопологія. В ГІС найбільш поширеними є вузлові топології (node topology), мережеві топології (network topology) та полігональні топології (poligon topology) (рис. 8.22). Рис. 8.22. Типи топології в ГІС Топологія в ГІС реалізується на підставі оригінальної і простої ідеї: різні типи просторових відношень представляються пов’язаними спис- ками об’єктів. Площинні об’єкти 290 У ГІС реалізовані три базові топологічні відношення дуг (аrc): – дуги, які з’єднуються в полігон, оточують область; – дуги, що мають напрямок, мають праві та ліві сторони; – дуги з’єднуються у вузлах. На цій основі в ГІС формалізована топологічна група просторових відношень, які не змінюються за будь-яких безперервних перетворень простору [8]: 1. Область (аrea) – визначається дугами, що з’єднуються в полігон для оточення області. 2. Суміжність (contiguity) – визначається дугами, що мають напрямок і тому мають праву і ліву сторони. 3. Зв’язність (connectivity) – визначається дугами, які з’єднуються у вузлах. Створення та збереження моделей географічних об’єктів на основі просторових відношень мають низку переваг, тому що: – дані зберігаються більш ефективно; – дані можна обробляти швидше та більшими наборами; – топологія полегшує застосування аналітичних функцій. Більш ефективний спосіб збереження даних заснований на понятті "граф". Граф – це множина елементів, пов’язаних між собою відношеннями. Геометрично граф представляється у формі векторної схеми, що складається з вершин, вузлів, ребер, дуг. Вершина (англ. vertex) – це об’єкт графа. Вершини зображують точками. Ребро (англ. edge) – це лінія, яка зв’язує точки (об’єкти графа). Ребра представляють відношення між об’єктами. Дуга (англ. arc) – це ребро з певною орієнтацією відносно її кінцевих вершин. Вузол (англ. node) – це спільна вершина для двох або більшої кількості дуг. У вузлах сходяться дуги. На рис. 8.23 зображено два альтернативні методи для подання полігонів. Перший метод (рис. 8.23 а) описує полігон як замкнену послі- довність векторів, що представлена списком координат. Другий метод (рис. 8.23 б) описує полігон як набір дуг (1, 2, 3) та вузлів (a, б). Полігон А визначають дуги 1, 2. Полігон В визначають дуги 2, 3. У першому випадку координати точок суміжних ліній повторюють- ся. У другому випадку загальну межу суміжних полігонів представляє дуга 2, координати якої використовуються один раз при описі дуги. |