Зацерковний В.І. та ін. ГІС та бази даних. І бази даних
 Скачать 31.1 Mb.
|
|
Вузол – це перетин двох або більше дуг. Його номер використо- вується для посилання на будь-яку дугу, якій він належить. 291 a б Рис. 8.23. Відображення суміжних полігонів на основі структури "граф": а – просте; б – векторне подання Кожна дуга (arc) починається і закінчується або в точці перетину з іншою дугою, або у вузлі, що не належить іншим дугам. Дуги утворюються послідовностями відрізків, з’єднаних проміжними (формотворними) точ- ками. У цьому випадку кожна лінія має два набори чисел: пари координат проміжних точок і номери вузлів. Крім того, кожна дуга має свій іденти- фікаційний номер, який використовується для визначення того, які вузли репрезентують її початок і кінець. Області, обмежені дугами, також мають ідентифікаційні коди, які використовуються для визначення їх відношень з дугами. Кожна дуга містить явну інформацію про номери областей ліворуч і праворуч, а це дозволяє знаходити суміжні області. Ця особливість моделі дозволяє комп’ютеру знати дійсні відношення між просторовими об’єкта- ми. Інакше кажучи, ми маємо векторну модель даних, яка краще відображає те, як ми, користувачі карт, визначаємо просторові взаємовідношення, записані в традиційному документі. Елементом вузлової топології є вузол. Кожний вузол у вузловій топології може характеризуватись набором даних: {ID, StartNode, EndNode, LeftPol, RightPol, DirectWeight, BackWeight }, де ID – ідентифікатор; StartNode, EndNode – початковий і кінцевий вузол дуги; LeftPol, RightPol – ідентифікатори полігонів праворуч і ліворуч від дуги (якщо одночасно побудована полігональна топологія); DirectWeight, BackWeight – вага дуги в прямому і зворотному напрямку. Залежно від того, скільки дуг об’єднано в одному вузлі, вузли можуть позначатися по-різному (рис. 8.24) і відрізнятися як: ∆ – нормальні вузли (три і більше дуг); ◊ – псевдовузли (дві дуги, в тому числі різні кінці однієї дуги); ◘ – висячі вузли (одна дуга). 292 Псевдовузли не є вузлами відгалуження, не є необхідними для розв’язання топологічних задач і тому можуть бути видалені (підчистка псевдоузлів) з об’єднанням кожної пари дуг, інцидентних 32 псевдовузлу, в одну дугу у відповідній вершині [43]. Рис. 8.24. Позначення вузлів Рис. 8.25. Сусідство двох полігонів Елементом полігональної топології є полігон. При створенні полігональної топології створюються і мережева, і вузлова топології. На рис. 8.25 проілюстровано приклад сусідства двох полігонів. Кожний полігон може характеризуватися наступним набором даних: {ID, Area, N, X, Y}, де ID – ідентифікатор полігона; Area – його площа; N – число ребер, що обмежують полігон; X, Y – координати центроїда полігона. Топологічний простір – множина елементів будь-якої природи, в якому тим або іншим способом визначені граничні співвідношення. Як визначається відстань між двома точками в евклідовому метрич- ному просторі, ми всі знаємо, бо в ньому живемо. Хоча дехто заперечить і скаже, що ми живемо трохи в іншому просторі (теж метричному) – на поверхні кулі, якому "ближче" сферична геометрія, ніж евклідова. З цим можна погодитися, тому що евклідовий простір – це простір на сфері без- крайньо великого діаметра, тобто частковий граничний випадок сфери. У ГІС потрібно розрізняти топологію простору і топологію фігури (конструкції), яка знаходиться в цьому просторі. Топологія об’єкта може бути не пов’язана з топологічністю метрич- ного простору. Наприклад, принципова електрична схема якогось при- ладу утворює топологічну конструкцію, але ця топологія – не метрична 32 Термін, що вживається в геометрії для вираження відношення належності між основними об’єктами геометрії. 293 (відстань між елементами не задана, та й не має сенсу її задавати). Іншим прикладом топологічно родинних фігур можуть служити арифметичні знаки додавання "+" і множення "*". Елементи топології, що входять в опис моделей даних ГІС, визначаються зв’язками між елементами основних типів координатних даних. Можна стверджувати, що зображення карти завжди топологічне внаслідок топологічних властивостей самого аркуша паперу. Аналогічно, топологічним буде й екран монітора. Поняття топології для точкових, лінійних об’єктів і полігонів суттєво різниться (рис. 8.26) [90]. Рис. 8.26. Топологія точкових, лінійних і полігональних об’єктів Набір ліній має топологію, якщо визначені: – взаємовідношення ліній; – напрямок ліній; – довжина ліній. У місцях перетинання лінійних об’єктів утворюються вузли (рис. 8.27). а б Рис. 8.27. Утворення вузлів Рис. 8.28. Подання полігонів: а – топологія відсутня; б – наявність і коректне зображення топології 294 Для топології вони повинні не просто стояти близько, їх координати повинні співпадати. Для площинних об’єктів топологія визначається коректністю геометрії об’єкта та їх взаємного розташування (сусідства). Коректність геометрії. Коректні в топологічному відношенні полі- гони повинні бути ідеально замкнуті і не мати самоперетинань ("вісімок") (рис. 8.28). Сусідство. Топологічна коректність взаємного розташування озна- чає, що межа між двома полігонами повинна бути завжди одна. Інакше кажучи, полігони не можуть перекривати один одного. Найнеобхідніша процедура при роботі з топологічною моделлю – підготовка геометричних даних для побудови топології. Цей процес не може бути повністю автоматизованим на даних середньої складності і реалізується тільки при додаткових, зазвичай істотних витратах праці. Таким чином, якщо дані зберігаються в ГІС, яка не передбачає підтримки топології, то вони не можуть бути надійно перетворені на топологічні дані іншої ГІС суто автоматичним алгоритмом. Примітка. Для забезпечення можливості використання сучасних аналітичних методів потрібно внести в комп’ютер якомога більше явної топологічної інформації. Оскільки математичний співпроцесор об’єднує багато спеціалізо- ваних математичних операцій, то і топологічна модель даних поєднує рішення функцій, які найбільш часто використовуються в географічному аналізі. Це забезпечується включенням у структуру даних інформації про суміжність об’єктів для елімінації 33 необхідності визначення топології при виконанні багатьох операцій. 8.8.2. Топологічне подання полігонів Топологічне подання полігонів розглянемо на прикладі карти (рис. 8.29). На карті: – полігон 1 – зовнішній полігон; – полігон 2 охоплюють дуги 4, 6, 7, 10, 8; – полігон 3 охоплюють дуги 3, 9, 10; – полігон 4 охоплюють дуги 2, 7, 9; – полігон 5 охоплюють дуги 1, 5, 6; – полігон 6 охоплює дуга 8. У ГІС топологічне подання реалізується списком "Полігон – Дуга" (рис. 8.30) та пов’язаним із ним списком "Координати дуг" [89]. 33 Елімінація (від лат. eleminatio – винесення за поріг) матем. – виключення невідомих із системи рівнянь. 295 Рис. 8.29. Карта полігональних об’єктів Рис. 8.30. Список "Полігон – Дуга" У списку "Полігон – Дуга" полігон 2 описується дугами 4, 6, 7, 10, 0, 8, де 0 перед дугою 8 вказує, що ця дуга створює острів (дірку) в полігоні 2. В списку "Полігон – Дуга" дуги можуть з’явитися 2 рази, у списку координат дуг – один раз. Кінцевими вершинами дуг є вузли. Ву- зол двох та більшої кількості дуг повинен мати у списку одні координати. Таким чином, топологічний опис області реалізується у цифровій формі двома пов’язаними списками. Топологічне подання суміжності розглянемо на прикладі карт дуг (рис. 8.31) [89]. Рис. 8.31. Карта дуг і полігонів 296 На карті ліворуч відносно дуги 5 знаходиться полігон 5, а праворуч – полігон 4; ліворуч відносно дуги 6 знаходиться полігон 2, а праворуч – полігон 5; ліворуч відносно дуги 1 знаходиться полігон 1, а праворуч – полігон 5 тощо. Зовні усіх полігонів знаходиться зовнішній полігон 1, який називають полігоном Всесвіту. Він уводиться для одноманітного (уніфікованого) опису полігонів: кожна дуга повинна мати полігони ліворуч і праворуч. Топологічне відношення суміжності дозволяє ідентифікувати те, що оточує об’єкт. Наприклад, виявити сусідів по земельній ділянці або чи суміжний ліс з озером тощо. Будь-які полігони, які спільно використо- вують дугу, є суміжними. Оскільки дуга має напрямок від вузла до вузла, то можна підтримувати список полігонів як з лівого, так і з правого боку. Таким чином, топологічний опис суміжності реалізується двома списками в цифровій формі [89]. У ГІС топологічне подання суміжності реалізується списком "Полі- гон ліворуч-праворуч" та зв’язаним із ним списком "Координати дуг" (рис. 8.32). Рис. 8.32. Список "Полігон ліворуч-праворуч" і зв’язаний із ним список "Координати дуг" Рис. 8.33. Карта дуг і вузлів (топологічне подання зв’язності) 8.8.3. Топологічне подання зв’язності Топологічне подання зв’язності розглянемо на прикладі карти дуг (рис. 8.33) [89]. Кінцеві точки дуги називаються "вузлами". Кожна дуга має два вузли: початковий, який називають "з вузла", та кінцевий, який називають "до вузла". Дуги можуть з’єднуватися тільки у вузлах. На рис. 8.34: дуги 7, 8, 9, 10 з’єднуються у вузлі 5; дуги 5, 6, 7 з’єднуються у вузлі 2 тощо. 297 У ГІС топологічне подання зв’язності реалізується списком "Дуга- Вузол" і зв’язаним з ним списком координат дуг. Отже, топологічний опис зв’язності у цифровій формі реалізується 2 списками. При простежуванні усіх дуг у списку "Дуга-Вузол" програма визначає, які дуги з’єднуються (пов’язані) одна з одною. Рис. 8.34. Список "Дуга-Вузол" і зв’язаний з ним список "Координат дуг" Зв’язність є надзвичайно ефективним засобом для розв’язання транспортних задач. Наприклад, можна проїхати по дугах 6, 7, 10 через вузли 5, 2, однак неможливо переїхати безпосередньо з дуги 6 на дугу 10, які не мають спільного вузла [89]. 8.8.4. Векторно-топологічна (лінійно-вузлова) модель Векторна модель, яка описує не тільки геометрію об’єктів, але й то- пологічні відношення між ними, отримала назву векторно-топологічної моделі. Елементами векторно-топологічної моделі даних (рис. 8.35 і 8.36) виступають: – внутрішній полігон (острів) – полігон, що знаходиться всередині іншого полігона; – складений полігон – містить внутрішні полігони; – простий полігон – не містить внутрішніх полігонів; д 298 – універсальний полігон – зовнішня область; полігон, зовнішній по відношенню до всіх інших полігонів шару. Рис. 8.35. Ілюстрація внутрішнього і складеного полігонів Рис. 8.36. Ілюстрація простого і універсального полігонів У більшості випадків сучасне математичне забезпечення ГІС базується саме на топологічних моделях. Топологія визначає всі об’єкти карти як набір ліній (дуг), міток і як просторові відношення між точками та лініями, що з’єднуються (рис. 8.37). Рис. 8.37. Топологічні відношення: • – вершина; ♦ – вузол; – лінія; + полігон 3 Внутрішній полігон Складений полігон Простий полігон Універсальний полігон 299 Така векторно-топологічна модель називається лінійно-вузловою. Ця модель визначає основні топологічні характеристики: – дуги з’єднуються між собою у вузлах (зв’язність); – дуги, обмежуючи фігуру, визначають полігон; – дуги мають напрямок, а також лівий і правий бік (безперервність). Кожна дуга має напрямок (початковий і кінцевий вузли), тобто можливість визначити список полігонів ліворуч і праворуч від дуги. Таким чином, полігони, які мають спільну дугу, є суміжними. Побудова топології має на меті подання основних топологічних характеристик для всіх об’єктів лінійно-вузлової моделі за допомогою декількох простих атрибутивних таблиць (рис. 8.38), які не містять координатних характеристик і називаються топологічними. Рис. 8.38. Характеристики лінійно-вузлової моделі Можна навести різні приклади топологічних властивостей для об’єктів лінійно-вузлової моделі, що будуть отримані з топологічних таблиць після побудови топології. Наприклад, дуга може бути замкненою чи незамкненою, висячою чи ні; полігон може мати острови, а може й не мати; дві дуги можуть не мати спільних точок, а можуть мати спільні вузли; два полігони можуть мати або не мати спільні дуги; характер сусідства двох полігонів: тільки за вузлами, тільки за дугами, одночасно і за вузлами, і за дугами, що не перетинаються. Топологічний розв’язок завдання ідентифікації всіх контурів даного полігона потребує розгляду топологічних зв’язків між дугами, що 300 утворюють межу тільки цього полігона. Визначення найбільш "великого" контуру серед усіх контурів даного полігона є складним топологічним завданням, розв’язання якого потребує залучення алгоритмів теорії графів та аналізу топологічних відношень між дугами не тільки кон- кретного полігона, але й між дугами інших полігонів лінійно-вузлової моделі. Лінійно-вузлова модель подання просторових об’єктів разом з топологічними таблицями дозволяють ефективно реалізувати специфічну просторово-аналітичну обробку даних, яка є ядром ГІС і становить набір функцій типу просторової вибірки, оверлейних операцій, вилучення дуг між сусідніми полігонами тощо. 8.8.5. DIME-структура Наприкінці 60-х років ХХ ст. у Бюро перепису США (US Bureau of the Census) при підготовці до чергового перепису населення було розроб- лено структуру збереження просторової інформації, названу за першими літерами слів Dual Independent Map Encoding (подвійне незалежне кодування карт) DIME-структурою. Ця структура відноситься до топологічних векторних структур даних. Основним елементом DIME-структури є дуга (arc), або сегмент (segment) – послідовність ліній, що починається і закінчується вузловими точками. Під вузловою точкою (node) розуміють точку перетину трьох або більше ліній. Однак на сучасному етапі розвитку ГІС як вузлова точка найчастіше розглядається будь-яка початкова або кінцева точка послі- довності ліній, що утворює сегмент або дугу. Так, зокрема, трактується поняття "вузлова точка" у рамках пакета IDRISI. Приклад формалізації просторових даних із використанням DIME- структури, наведений на рис. 8.39. У таблиці сегментів (в) і полігонів (ділянок) (г) додатково введені атрибутивні дані – довжини сегментів (дуг) і прізвища власників, площі та кадастрові номери ділянок. Введення топологічних характеристик у структуру векторних даних дозволяє уникнути основного недоліку, притаманного точковим полі- гональним структурам, – необхідності подвійного обведення спільних меж і похибок, які при цьому виникають. Кожна точка при цьому запам’ятовується тільки один раз у складі якого-небудь сегмента (дуги) і може використовуватися багаторазово – стільки разів, скільки це буде необхідно. 301 а б в Полігон (ділянка) Сегменти Власник Площа, га Кадастровий номер A I, II, III Прищик І. Ф. 154,3 Т-148442 B II, IV, V Хрущик С. О. 102 Т-148443 C III, V, VI Непийпиво О. А. 115,8 Г-446128 г Рис. 8.39. Представлення картографічних даних з використанням DIME-структури: а – формалізація вихідної карти (жирним шрифтом виділені номери вузлових точок); б – таблиця координат опорних точок; в – таблиця сегментів; г – таблиця полігонів 8.8.6. Структура "дуга-вузол" Наступним етапом DIME-структури є векторні топологічні структу- ри типу "дуга-вузол" (Arc-Node Structure), або лінійно-вузлові структури векторних даних, у яких об’єкт у базі даних структурований ієрархічно, а базовими елементарними графічними об’єктами, крім точки, лінії і полігона, є дуга (або сегмент). Опис метричного навантаження карти в базі даних із використанням лінійно-вузлової структури векторних даних, як і в DIME-структурі, складається з трьох наборів даних [86]: 1) таблиці пар координат (х, у) точок введення, які представляють геометрію дуг; 2) таблиці атрибутів дуг; 3) таблиці атрибутів полігонів. 302 Але на відміну від DIME-структури, в таблиці атрибутів дуг наво- дяться тільки початкова (from) і кінцева (to) точки (вузли) кожної дуги. Вказівки на лівий і правий полігони не наводяться. За потреби в структуру таблиць можуть бути введені атрибути, що характеризують точкові, лінійні або полігональні об’єкти. Це можуть бути, наприклад, характеристики початкових і кінцевих точок введення дуг, назви вулиць (лінійних об’єктів) і їх метричні характеристики, власники земельних ділянок (полігональних об’єктів), їхня площа й унікальні кадастрові номери (рис. 8.40). Рис. 8.40. Подання в базі даних фрагмента картографічної інформації, зображеного на рис. 8.31, з використанням структури "сегмент (дуга)-вузол": а – таблиця координат опорних точок; б – таблиця сегментів; в – таблиця полігонів Лінійно-вузлові (топологічні) структури векторних даних у ГІС представлені досить великою кількістю різновидів. Варто відзначити модель TIGER (The Topologically Integrated Geographic Encoding and Referencing data format), яку було розроблено в Бюро переписів США для заміни DIME–структури наприкінці 80-х років XX ст., а також DLG- структуру (Digital Line Graph Structure) – стандарт Геологічної служби США (USGS) для пошарового кодування інформації, що міститься на топографічних картах і DLG-Е – Digital Line Graph-Enhanced – розширену версію формату DLG, а також покриття (coverage) – топологічний векторний файл ГІС-пакетів фірми ESRI [86]. |