Векторні структури даних

Визначення. Вектор - величина з початковою точкою, асоційованим з нею зсувом та напрямком.

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

У більшості ГІС координати даних кодуються й зберігаються, як деякі комбінації точок, ліній, площ та полігонів. Декілька видів векторних СД знаходяться у загальному користуванні, замість засобів представлення БД всередині ГІС, так і замість стандартів обміну даними між системами. Це:

1) (цілісна) непросіяна полігональна структура (whole polygon structure),

2) подвійне незалежне кодування карт (Dual Independent Map Encoding (DIME)) файлова структура,

3) дуга-вузол (arc-node) структура,

4) реляційна (relational) структура,

5) цифрові лінійні графіки (digital line graphs або DLG).

Непросіяна полігональна структура (НПС)

У НПС кожен шар бази даних розділений на багато полігонів. Кожен полігон кодується у БД, як послідовність розміщень, що визначають границі кожної замкненої області у певній координатній системі (що іноді називають - "гранична петля"). Кожен полігон тоді зберігається як незалежна властивість (об’єкт).

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

Атрибути полігонів - такі, як тип ґрунту або власник, можуть зберігатись з координатним списком. Коли кожен полігон підтримується як окрема сутність, топологічна організація не підтримується.

Під топологією ми розуміємо співвідношення між різними просторовими об`єктами: які полігони розділяють границю, які точки влучають на границю окремого полігону і т.д. У НПС лінійні сегменти, що визначають границі полігонів, кодуються двічі - по одному разу для полігону по кожен бік лінії. Аналогічно, точки, що розподіляють декілька полігонів також будуть представлені кілька разів у БД. При такій організації дуже важко виконати редагування та оновлення БД без пошкодження структури даних.

DIME структура

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

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

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

Додаткові поля атрибутів, відмічені номерами заголовків, наявні для груп сегментів таких, як телефонний комутатор, виборчі дільниці, чи код поштової адреси (ZIP-коди у США або аналогічні поштові коди у Великобританії, або Канаді). Окремо є множина полів, призначена для логічного групування й відмітки сегментів.

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

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

Структура дуга-вузол

У дуга-вузол структурі даних об`єкти у базі даних структуруються ієрархічно. У цій системі точки є елементарними базовими компонентами.

Дуги - це індивідуальні лінійні сегменти, визначені множиною пар координат x,y. Вузли є кінцями дуг й утворюють точки їх перетину. Може розрізняти вузли на кінцях ліній й точками, які не пов`язані з лініями. Полігони - це площі, повністю обмежені множиною дуг. Тобто вузли одночасно відносяться і до дуг і до полігонів.

Структури “Дуга-вузол” дозволяють кодувати геометрію даних без надлишків. На відміну від непросіяної полігональної структури (whole polygon structure), точки зберігаються лише один раз. Вони з`являються стільки разів, скільки необхідно.

У базу даних “Дуга-вузол” можна легко включати атрибути різних якостей. На прикладі вулиці та контролю руху атрибути явно прив`язані до геометрії. Так, опис засобів контролю руху зберігається з відповідними вузлами, а довжини доріг та якість тротуарів зберігаються разом з відповідними дугами.

Зауважимо, що у цьому дуга-вузол транспортному прикладі зберігаються довжини дуг. Щоправда, збереження цієї інформації в базі даних - надлишкове, оскільки теоретично ці довжини можуть бути обчислені з координат вузлів на кінцях дуг. Але, якщо у додатках інтенсивно використовуються довжини дуг, то може бути більш ефективним визначити довжини один раз при конструюванні бази даних, ніж обчислювати кожного разу при використанні даних. Це приклад класичної проблеми у системах баз даних (СБД) досягнення балансу між вартістю зберігання, редагування та обробки. У сучасних ГІС користувач повинен бути в змозі впливати на цей баланс, базуючись на певних вимогах застосувань.

Реляційна структура

Іншу форму векторної організації даних “Дуга-вузол” називають ще іноді реляційною структурою даних. У останньому прикладі значення атрибутивних даних зберігаються вкупі з топологічною інформацією. У реляційній структурі даних атрибутивна інформація зберігається окремо.

Топологічні дані у реляційній структурі організовані так само, як і у структурі “Дуга-вузол”. Принципові відмінності є в атрибутивних значеннях. Вони зберігаються у реляційних таблицях.

Ці таблиці прямі: рядок таблиці представляє один запис, а стовпчики представляють різні поля або атрибути.

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

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

DLG структура

DLG - (Digital Line Graph) - один з найпопулярніших форматів, розроблених у U.S. Geogical Survey. Очевидно, саме на його основі були розроблені радянські класифікатори картографічної інформації.

Дані, що містяться у DLG файлах, розділені на різні тематичні шари. Перший шар містить адміністративні границі регіону. Другий шар призначений для гідрографічних об`єктів. Третій призначений для зберігання інформації про транспортну мережу. Нарешті, четвертий шар базується на громадській земельній реєстраційній системі (Public Land Survey System), що підпорядковується Бюро земельного управління США.

Істотні елементи даних рівня 3 DLG структури аналогічні до інших векторних структур (DIME, дуга-вузол, реляційна). Вузли представляють кінцеві точки ліній або їх перетини, тоді, як додаткові точки використовуються для відображення важливих властивостей уздовж ліній. Лінії мають початковий та кінцевий вузли, що, дозволяє визначити їх напрямок, і області, що знаходяться від неї ліворуч та праворуч. Спеціальна вироджена лінія позначена як лінія нульової довжини і використовується для визначення точкових об’єктів карти. Вироджені лінії легко впізнати, оскільки вони мають однакові початковий і кінцевий вузли. Площі (області) в DLG форматі повністю обмежуються лінійними сегментами. Кожна область може мати асоційовану точку, що представляє характеристики області; розміщення точки довільне, і може бути навіть не всередині області.

Токовий, лінійний і площинний елементи забезпечують інформацію про топологію і розташування. Нарешті, створена розвинута система для кодування атрибутної інформації елементів. Коди атрибутів базуються на властивостях, що представлені на USGS топографічних картах. Коди атрибутів структуруються визначеним способом при допомозі головної і другорядної компонент кодування. Головний код складається із 3-х цифр. Перші дві цифри позначають загальну категорію елемента, тоді як третя представляє додаткові деталі. Кілька головних кодованих категорій:

Головний кодКатегорія

020 гіпсографія (hypsography)

050 гідрографія

070 покриття поверхні (surface cover)

Другорядні коди складаються з чотирьох цифр. Перша цифра звичайно нуль. Решта три забезпечують подальші деталі:

Другорядний кодОпис

001-099 вузли

100-199 області

200-299 лінії

300-399 вирождені лінії

400-499 загальноцільові коди

500-599 описові коди

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

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

Вузли(Nods)

050 0001 Верхній кінець потоку

050 0004 Потік, що входить в основне русло

050 0005 Потік, що виходить з основного русла

Області(Area)

050 0101 Резервуар

050 0103 Льодовик

050 0106 Рибний розсадник (fish hatchery)

Лінії(Lines)

050 0200 Берегова лінія

050 0201 Рукотворна берегова лінія

Загальноцільові атрибути

050 0400 Пороги

050 0401 Водоспади

050 0406 Дамба або гребля

Загальні описові атрибути

050 0601 Підземний

050 0603 Підвищений

050 0604 Тунельний

DLG файл даних третього рівня містить кілька записів заголовків, та відповідних записів даних.

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

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

Є також, щоправда, необов'язковий кінцевий запис з інформацією про оціночну точність даних. Треба відмітити, що вже існує нова розробка, що, як очікується, замінить DLG і DIME структури даних для використання в Бюро перепису США, названа TIGER: (Topologically Integrated Geographic Encoding and Referencing).