Конспект лекцій

з дисципліни

“Геоінформаційні системи”

Харків 2012

МІНІСТЕРСТВО ОСВІТИ І НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ

ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

КОНСПЕКТ ЛЕКЦІЙ

з дисципліни “ГЕОІНФОРМАЦІЙНІ СИСТЕМИ”

для студентів денної форми навчання

напряму 6.040303 – системний аналіз

ЗАТВЕРДЖЕНО

кафедрою ПМ

Протокол № __ від _____________

Харків 2012

Конспект лекцій з дисципліни “Геоінформаційні системи” для студентів денної форми навчання напряму 6.040303 “Системний аналіз”/ Упоряд.: С.М. Ієвлєва, – Харків: ХНУРЕ, 2012 – 128 с.

Упорядник: С.М. Ієвлєва

Рецензент: В.П. Ткаченко, к–т техн. наук, проф. каф. МСТ

Зміст

Вступ. 6

1 Загальні відомості про ГІС.. 7

1.1 Визначення ГІС.. 7

1.2 «Дані», «інформація», «знання» у геоінформаційних системах. 8

1.3 Узагальнені функції ГІС-систем.. 9

1.4 Класифікація ГІС.. 10

1.5 Джерела даних та їх типи. 11

1.6 Способи введення даних. 11

1.7 Перетворення вихідних даних. 12

1.8 Основні компоненти ГІС.. 13

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

2 Основні поняття ГІС. Моделі даних. 16

2.1 Відображення об'єктів реального світу в ГІС.. 16

2.2 Структури даних. 17

2.3 Моделі даних. 19

2.4 Формати даних. 21

2.5 Бази даних і керування ними. 22

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

3 Структури просторових даних ГІС.. 24

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

3.2 Ієрархічні структури даних. 26

3.3 Алгоритми на квадродеревах. 28

3.4 Просторові індекси. 30

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

4 Алгоритми обчислювальної геометрії 32

4.1 Перетин ліній. 32

4.2 Операції з полігонами. 34

4.3 Оверлей полігонів. 38

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

5 Моделювання поверхонь. 42

5.1 Растрові цифрові моделі місцевості 43

5.2 Нерегулярні тріангуляційних мережі (TIN) 47

5.3 GRID-, TGRID моделі 53

5.4 Інтерполяції 54

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

6 Геодезія та цифрова фотограмметрія в ГІС.. 57

6.1 Визначення прямокутних координат точок. 57

6.2 Геодезичні засічки. 59

6.2.1 Полярна засічка. 59

6.2.2 Пряма кутова засічка. 60

6.2.3 Лінійна засічка. 61

6.3 Фотограмметрія. 62

6.3.1 Системи координат.. 63

6.3.2 Внутрішнє орієнтування знімка. 63

6.3.3 Зовнішнє орієнтування знімка. 65

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

7 Фізична поверхню Землі і референцної системи координат. 67

7.1 Геодезичні системи координат і висот. 67

7.2 Системи координат, які використовуються в Україні 69

7.3 Місцеві системи координат. 70

7.4 Системи координат, що використовуються в європейській та світовій практиці 71

7.5 Зв'язок УСК-2000 з іншими системами координат. 72

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

8. Загальна теорія картографічних проекцій. 74

8.1 Системи координат прийняті в ГІС.. 74

8.2 Визначення картографічних проекцій, картографічні мережі 77

8.3 Нескінченно мала сфероїдинчна трапеція. 77

8.4 Масштаби. 79

8.5 Умови відображення поверхні еліпсоїда (сфери) на площині 80

8.6 Спотворення картографічних проекцій. 80

8.7 Методи перетворення картографічних проекцій під час створення карт геоінформаційних систем 83

8.8 Фактори і способи вибору картографічних проекцій. 84

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

9 Масштаби. Картографічні проекції. 86

9.1 Головні масштаби, компонування та розграфлення карт, координатні сітки та номенклатури 86

9.2 Теорія класів і окремих варіантів картографічних проекцій. 88

9.3 Циліндричні проекції 89

9.4 Псевдоциліндричні проекції 90

9.5 Конічні проекції 91

9.6 Азимутальні проекції 91

9.7 Перспективні азимутальні проекції 92

9.8 Псевдоконічні проекції 94

9.9 Псевдоазимутальні проекції 95

9.10 Поліконічна проекції 96

9.11 Проекції Гауса-Крюгера і UТМ... 97

9.12 Проекція Чебишева. Проблема вибору найкращих проекцій. 98

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

Розробка системного проекту ГІС.. 99

10.1. Інформаційно-керуючі системи. 99

10.2. Визначення вхідних і вихідних даних системи. 101

10.3. Вибір програмного забезпечення ГІС.. 107

10.3.1. Підсистема введення даних. 107

10.3.2. Підсистема зберігання даних. 108

10.3.3. Підсистема просторового аналізу та візуалізації результатів. 109

10.4. Контрольні питання. 112

Повнофункціональні ГІС.. 113

11.1. Огляд існуючих геоінформаційних систем.. 113

11.2. GeoGraph. 114

11.3. GeoLink. 115

11.4. Maplnfo Professional 116

11.5. WinGIS. 118

11.6. Zulu. 118

11.7. «Горизонт». 119

11.8. «ИнГео». 119

11.9. Парк. 120

11.10. ArcGIS. 120

11.10.1. ArcGIS Arclnfo. 120

11.10.2. ArcGIS ArcEditor 121

11.10.3. ArcGIS ArcView.. 122

11.10.4. ArcView GIS. 123

11.11. Autodesk Map. 123

11.12. GeoMedia/GeoMedia Professional 123

11.13. Manifold System Professional 124

11.14. MicroStation/J. 124

11.15. WinPlan. 125

ПЕРЕЛІК ПОСИЛАНЬ. 126

Вступ

Дисципліна “Геоінформаційні системи” займає важливе місце в системі прикладних математичних дисциплін, що вивчаються студентами спеціальності «Системний аналіз».

Розвиток інформаційних технологій на базі обчислювальної техніки, створення автоматизованих, високопродуктивних робочих станцій, банків даних і баз знань, а також обчислювальних мереж привело до появи геоінформатики, в основі якої лежать геоінфрмаційні системи і геоінформаційні технології. (ГІС).

ГІС забезпечує могутній інструментарій, для вирішення проблем, зв'язаних з географією і навколишнім середовищем. ГІС дозволяє упорядковувати інформацію про дану місцевість чи місто у вигляді комплекту карт. Головним у ГІС є "природне" представлення інформації (як власне просторової інформації, так і іншої – тематичної тощо), що має відношення до об'єктів, розташованим "у просторі".

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

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

Вивченню методів теорії оптимального керування присвячено багато літератури, зокрема, роботи [1–14]. Під час викладення матеріалу автор дотримувався, в основному, робіт [1–4].

1 Загальні відомості про ГІС

План лекції. Визначення ГІС. «Дані», «інформація», «знання» у геоінформаційних системах. Узагальнені функції ГІС-систем. Класифікація ГІС. Джерела даних та їх типи. Способи введення даних. Перетворення вихідних даних. Основні компоненти ГІС.

1.1 Визначення ГІС

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

Гео (географічні) – тобто, пов'язані з просторовими даними, які отримують шляхом переходу вручну або напівавтоматично від паперових карт до комп'ютерного картографування, з використанням інструментарію математичного картографування.

Інформаційні – тобто, використовуються терміни інформаційних систем і баз даних.

Системи – тобто, використовуються властивості і терміни системного аналізу. Враховуючи вищезазначене, можна виділити два основних визначення ГІС, що наведено в літературі.

«ГІС – автоматизована інформаційна система, призначена для збору, обробки, аналізу, моделювання і зображення даних, а також для вирішення інформаційних завдань з використанням цифрової, картографічної, аналогової і текстової інформації» (ГОСТ 28441-99).

«ГІС – автоматизована інформаційна система, призначена для обробки просторово-часових даних, основою яких є географічна інформація і має спеціальний картографічний інтерфейс».

Таким чином, можна виділити ряд характерних особливостей ГІС:

- автоматизована система;

- виконує обробку (аналіз, моделювання, обчислення різних залежностей і.т.д.);

- оперує просторово-тимчасовими даними (дані прив'язані до місця і до часу);

- основа інтеграції даних – просторова, а не часова;

- картографічний інтерфейс.

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

«Родичами» ГІС є різні CAD системи, електронні карти і електронні таблиці з можливостями побудови планів.

Найбільш важливим критерієм віднесення до ГІС є розвиненість спеціалізованого картографічного інтерфейсу і інструментів просторового аналізу даних.

Хоча історія розробки ГІС охоплює вже більше 5 десятиліть, їх активний «наступ» на ринку комерційних програмних засобів почався 15-20 років тому і пов'язаний з масовою появою комп'ютерів, що мають високу продуктивність, необхідну для обробки графічної інформації.

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

Найбільш поширені ГІС – настільні ГІС, коли й сама ГІС-програма і дані, які оброблюються знаходяться на одному комп'ютері або в локальній мережі.

Можна говорити також про корпоративні ГІС, а Google Earth назвати «Всесвітньою ГІС».

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

До найвідоміших настільних ГІС можна віднести програми ArcView, ArcGis (компанія ESRI), МарInfo (компанія МарInfo), з вітчизняних можна виділити сімейство програм «Панорама» (КБ Панорама).

1.2 «Дані», «інформація», «знання» у геоінформаційних системах

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

Під даними розуміється сукупність фактів, відомих про об'єкти, або результати вимірювання цих об'єктів. Дані, що використовуються в ГІС, відрізняються високим ступенем формалізації. Дані – це нібито будівельний елемент у процесі створення інформації, яка отримується у процесі обробки даних.

Стосовно до ГІС під інформацією розуміється сукупність відомостей, що визначають міру наших знань про об'єкт.

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

Інформаційні системи можна розглядати як ефективний інструмент отримання знань.

Відмінності між термінами «дані», «інформація» і «знання» простежуються в історії розвитку технічних систем, так спочатку з'явилися банки даних, пізніше інформаційні системи, потім з'явилися системи, засновані на знаннях – інтелектуальні системи (експертні системи).

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

1.3 Узагальнені функції ГІС-систем

Схематично функції ГІС представлені на рис. 1.1.

Рисунок 1.1 – Функції ГІС

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

1) введення і редагування даних;

2) зберігання, контроль якості (цілісності);

3) підтримка моделей просторових даних;

4) перетворення систем координат і трансформація картографічних проекцій;

5) растрово-векторні операції;

6) вимірювальні операції;

7) полігональні операції;

8) операції просторового аналізу;

9) різні види прогнозування та просторового моделювання;

10) цифрове моделювання рельєфу та аналіз поверхонь;

11) відображення (на екрані, для друку)

12) вивід результатів у різних формах.

1.4 Класифікація ГІС

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

Безліч завдань, що виникають у житті, призвели до створення різних ГІС, які можуть класифікуватися за такими ознаками:

За функціональним можливостям:

- повнофункціональні ГІС загального призначення;

- спеціалізовані ГІС орієнтовані на рішення конкретної задачі в будь-якій предметній області;

- інформаційно-довідкові системи для домашнього та інформаційно-довідкового користування.

Функціональні можливості ГІС визначаються також архітектурним принципом їх побудови:

- закриті системи – не мають можливостей розширення, вони здатні виконувати тільки той набір функцій, який однозначно визначений на момент покупки;

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

За просторовим (територіальним) охопленням:

- глобальні (планетарні);

- загальнонаціональні;

- регіональні;

- локальні (у тому числі муніципальні).

За проблемно-тематичною орієнтацією:

- загальногеографічні;

- екологічні та природокористувальницькі;

- галузеві (водних ресурсів, лісокористування, геологічні, туризму і т.д.).

За способом організації географічних даних:

- векторні;

- растрові;

- векторно-растрові.

1.5 Джерела даних та їх типи

В якості джерел даних для формування ГІС служать:

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

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

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

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

- літературні дані (довідкові видання, книги, монографії та статті, що містять різноманітні відомості за окремими типами географічних об'єктів).

У ГІС рідко використовується тільки один вид даних, частіше за все це поєднання різноманітних даних на будь-яку територію.

1.6 Способи введення даних

Відповідно до технічних засобів, які використовуються для введення даних розрізняють два способи: дігіталізацію і векторизацію. Для ручного введення просторових даних застосовується дігітайзер. Він складається з планшета (столика) з електронною сіткою, до якого приєднано пристрій, який має назву курсор. Курсор являє собою подобу графічного маніпулятора – миші, має візир, нанесений на прозору пластину з допомогою якого оператор виконує точне наведення на окремі елементи карти. На курсорі поміщені кнопки, які дозволяють фіксувати початок і кінець лінії або межі області, кількість кнопок залежить від рівня складності дігітайзера. Дігітайзери бувають різних форматів і забезпечують роздільність 0,03 мм із загальною точністю 0,08 мм на відстані 1,5 м. Існують автоматизовані дігітайзери, щоб забезпечити автоматичне відстеження ліній.

Найбільше поширення для введення даних одержали сканери. Вони дозволяють вводити растрове зображення карти в комп'ютер. Існують різні типи сканерів, які розрізняються: за способом подачі вихідного матеріалу (планшетні і протяжні (барабанного типу); за способом зчитування інформації (працюють на просвіт або на відображення); по радіометричній роздільності або глибині кольору; по оптичній (або геометричній) роздільності.

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

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

1.7 Перетворення вихідних даних

Відскановані вихідні карти створювалися в певній картографічній проекції і системі координат. При оцифровуванні ця складна проекція зводиться до набору просторових координат. Тому необхідно перетворити карту до її вихідної проекції. Для цього в ГІС вводяться відомості про проекції, які були використані (зазвичай ГІС дозволяє працювати з великим числом проекцій) та здійснюється ряд перетворень. Три із основних перетворень, які найчастіше виконуються одночасно, це перенесення, поворот і масштабування.

Перенесення – це просто переміщення всього графічного об'єкта в інше місце на координатній площині. Воно виконується додаванням певних величин до координат Х і У об'єкту:

.

Масштабування теж дуже корисно, так як часто скануються карти різних масштабів, для цього використовують співвідношення:

.

Поворот виконується з використанням тригонометричних функцій:

.

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

1.8 Основні компоненти ГІС

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

Технічне забезпечення – це комплекс апаратних засобів, що застосовуються при функціонуванні ГІС: робоча станція або персональний комп'ютер (ПК), пристрої введення-виведення інформації, пристрої обробки і зберігання даних, засоби телекомунікації.

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

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

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

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

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

Структурно програмне забезпечення ГІС включає базові та прикладні програмні засоби.

Базові програмні засоби включають: операційні системи (ОС), програмні середовища, мережне програмне забезпечення і системи управління базами даних. Операційні системи призначені для управління ресурсами ЕОМ і процесами, які використовують ці ресурси. На даний час основні ОС: Windows і Unix подібні системи.

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

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

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

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

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

1. Дайте визначення та основні характерні особливості ГІС.

2. Дайте визначення таким термінам: "дані", "інформація", "знання".

3. Назвіть функції ГІС.

4. Які узагальнені функції ГІС?

5. Дайте класифікацію ГІС.

6. Які джерела даних та їх типи у ГІС?

7. Наведіть способи введення та виведення даних у ГІС.

8. Наведіть визначення поняттям «перенесення», «масштабування», «поворот».

9. Наведіть основні компоненти ГІС.

2 Основні поняття ГІС. Моделі даних

План лекції. Відображення об'єктів реального світу в ГІС. Структури даних. Моделі даних. Формати даних. Бази даних і керування ними.

2.1 Відображення об'єктів реального світу в ГІС

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

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

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

Тематичні характеристики описують різні властивості об'єкта, включаючи економічні, статистичні, технічні та інші властивості, основна вимога – повнота.

Для представлення просторових об'єктів в ГІС використовують просторові та атрибутивні типи даних.

Просторові дані – відомості, які характеризують місце розташування об'єктів у просторі відносно один до одного і їх геометрію.

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

Опис об'єктів здійснюється шляхом зазначення координат об'єктів і їх складових частин.

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

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

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

Поверхня – при її описі потрібне додавання до майданних об'єктів значень висот. Відновлення поверхонь здійснюється за допомогою використання математичних алгоритмів (інтерполяції та апроксимації) за вихідним набором координат .

Додаткові непросторові дані про об'єкти утворюють набір атрибутів. Атрибутивні дані – це якісні або кількісні характеристики просторових об'єктів, що виражаються, як правило, в алфавітно-цифровому вигляді. Приклади таких даних: географічна назва, видовий склад рослинності і т.п.

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

Загальний цифровий опис просторового об'єкта включає: найменування; вказівку місця розташування; набір властивостей; відносини з іншими об'єктами. Найменуванням об'єкта служить його географічна назва (якщо вона є), його умовний код або ідентифікатор, які привласнюється користувачем або системою.

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

2.2 Структури даних

Геоінформаційна структура даних у ГІС представлена на рис. 2.1.

Рисунок 2.1 – Геоінформаційна структура даних у ГІС

Для графічного представлення просторових об'єктів та їх атрибутів в ГІС застосовують векторне і растрове представлення даних.

Векторна структура – це уявлення просторових об'єктів у вигляді набору координатних пар (векторів), що описують геометрію об'єктів (рис. 2.2).

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

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

Рисунок 2.2 – Векторне подання просторових даних

Рисунок 2.3. Растрова структура даних

Для реалізації растрових і векторних структур розроблені різні моделі даних.

2.3 Моделі даних

Моделі просторових даних – логічні правила для формалізованого цифрового опису просторових об'єктів.

Векторні моделі даних. Існує кілька способів об'єднання векторних структур даних у векторну модель даних, що дозволяє досліджувати взаємозв'язки між об'єктами одного шару або між об'єктами різних шарів. Найпростішою векторною моделлю даних є «спагеті»-модель (рис. 2.4). У цьому випадку перекладається «один в один» графічне зображення карти.

	Паперова карта

Цифрова карта у декартових координатах (модель даних)

Об’єкт	Номер	Положення
Точка		Одна пара координат
Лінія		Набір пар координат , – кількість точок
Область		Набір пар координат , перша та остання координати збігаються

Рисунок 2.4 – «Спагетті»-модель

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

Векторні топологічні моделі (рис. 2.5) містять відомості про сусідство, близькість об'єктів та інші, характеристики взаємного розташування векторних об'єктів.

Файл вузлів
Номер вузла	Координата	Координата

Файл дуг
Номер дуги	Правий полігон	Лівий полігон	Початковий вузол	Кінцевий вузол

Файл областей
Номер області	Список дуг
	1,3,9
	2,3,6,7
	4,5,9
	5,7,8

Рисунок 2.5 – Векторна топологічна модель даних

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

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

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

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

2.4 Формати даних

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

Існує велика кількість форматів даних. Можна відзначити, що в багатьох ГІС підтримуються основні формати зберігання растрових даних (TIFF, JPEG, GIF, BMP, WMF, PCX), а також GeoSpot, GeoTIFF, що дозволяють передавати інформацію про прив'язку растрового зображення до реальних географічних координат, і MrSID для стискання інформації. Найбільш поширеним серед векторних форматів є DXF.

Всі системи підтримують обмін просторовою інформацією (експорт та імпорт) з багатьма ГІС та САПР через основні обмінні формати: SHP, E00, GEN (ESRI), VEC (IDRISI), MIF (MapInfo Corp.), DWG, DXF (Autodesk), WMF (Microsoft), DGN (Bentley). Тільки деякі, в основному вітчизняні системи, підтримують російські обмінні формати – F1M (Роскартографія), SXF (Військово-топографічна служба).

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

2.5 Бази даних і керування ними

Сукупність цифрових даних о просторових об'єктах утворює безліч просторових даних і становить зміст баз даних.

База даних (БД) – сукупність даних організованих за певними правилами, які встановлює загальні принципи опису, зберігання і маніпулювання даними. Створення БД і звернення до неї (за запитами) здійснюється за допомогою системи управління базами даних (СУБД).

Логічна структура елементів бази даних визначається обраною моделлю БД. Найбільш поширеними моделями БД є ієрархічні, мережні, реляційні та об'єктно-орієнтовані.

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

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

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

Реляційні моделі збирають дані в уніфіковані таблиці. Таблицям присвоюється унікальне ім'я усередині БД. Кожен стовпець у таблиці – це поле, що має ім'я, яке відповідає значенню атрибута. Кожен рядок у таблиці відповідає запису у файлі. Одне і теж поле може бути присутнім в декількох таблицях. Так як рядки в таблиці не упорядковані, визначається один або декілька стовпців, значення яких однозначно ідентифікують кожний рядок. Такий стовпець називається первинним ключем. Взаємозв'язок таблиць підтримується зовнішніми ключами. Маніпулювання даними здійснюється за допомогою операцій, які породжують таблиці. Користувач може легко заносити в базу нові дані, комбінувати таблиці, вибираючи окремі поля та записи, і формувати нові таблиці для відображення на екрані.

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

Для обробки даних, розміщених у таблицях, необхідні додаткові відомості про дані, їх називають метаданими.

Метадані – дані про дані: каталоги, довідники, реєстри та інші форми опису наборів цифрових даних.

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

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

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

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

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

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

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

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

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

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

3 Структури просторових даних ГІС

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

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 – Порядок сканування растра Пеано

3.2 Ієрархічні структури даних

Розглянуті вище порядки сканування растрових зображень дають незначні відмінності в стисканні даних. Основна перевага Мортон-сканування та інших ієрархічних структур даних полягає у більш швидкому доступі до даних.

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

Далі піде мова про адаптивні методи подання растрових даних з різною щільністю інформації. На рис. 3.4 зображена растрова матриця розміру 16 x 16, у якій містяться 255 значень "A" і одне "B". Індексуємо растр наступним чином. Розділимо матрицю на чотири підматриці розміру 8 x 8 і нумеруємо їх 0, 1, 2, 3 в порядку Мортона. Назвемо підматрицю гомогенної, якщо в ній містяться однакові значення. Будемо рекурсивно розбивати негомогенні підматриці до тих пір, поки не досягнемо гомогенності всіх підматриць. Таким чином отримаємо растрове зображення, де ділянки з меншою щільністю інформації представлені великими блоками комірок, а з більшою щільністю – дрібними блоками комірок. Ідея виділення гомогенних блоків растра тотожна кодуванню растра за Мортоном. Гомогенний блок растра розміру при скануванні за Мортоном відповідає коду .

Рисунок 3.4 – Розбиття растра на гомогенні блоки

Відповідність двовимірних растрових координат комірки і адреси клітинки в послідовному файлі схоже на аналогічне перетворення при кодуванні растра за Мортоном. Єдина відмінність в тому, що використовується система числення з основою чотири. У прикладі на рис. 3.4 комірка "B" має код 0311. У двійковій системі числення . Розділимо біти між растровими координатами і з'ясуємо, що комірка лежить в четвертому рядку () і сьомому стовпці ().

Представлені таким способом растрові дані відповідають квадродереву, вершина якого – вихідне зображення, а листя – гомогенні блоки комірок. При кодуванні квадродерева комірки на кожному рівні можуть містити або значення гомогенного блоку, або вказівник на наступний рівень. Дерево, показане на рис. 3.4 може бути представлено у вигляді лінійної послідовності (рис. 3.5).

Рисунок 3.5 – Кодування квадродерева

Як вже зазначалося вище, основна перевага ієрархічної організації даних у ГІС полягає в просторовому впорядкування інформації та більш швидкому її пошуку. Тому розглядаються два завдання ГІС, пов'язані з індексацією квадродерева: перша – пошук всіх частин карти із заданим значенням і друга – визначення вмісту деякої комірки. Позначимо n – число рівнів квадродерева (тоді розмір растра 2n х 2n) і через m – число листків у дереві. Щоб знайти частини карти з деяким значенням «B», необхідно перевірити кожен лист дерева, що займе m кроків. Визначення значення комірки відбувається шляхом спуску по квадродереву до тих пір, поки не буде отриманий гомогенний блок. У гіршому разі, коли клітинка знаходиться на самій вершині дерева (як, наприклад, комірка «B» на рис. 3.4), пошук займе n кроків. Порівняємо тепер трудомісткості обох завдань на квадродереві з трудомісткостями цих завдань при різних варіантах сканування растра (табл. 3.1).

Таблиця 3.1 – Трудомісткість алгоритмів при різній організації растрів

Структура даних	Пошук частин із заданим значенням	Визначення значення клітинки
Квадродерево
Звичайний порядок
Boustrophedon
Мортон

Примітка: * – перевіряється кожна клітинка матриці, ** – безпосереднє обчислення позиції клітинки, *** – кількість ланцюжків приблизно відповідає кількості листя, **** – перевіряється кожен ланцюжок.

Існують різні модифікації квадродерев, що дозволяють, наприклад, ефективно індексувати тривимірні дані (при цьому куб рекурсивно ділиться на вісім частин). При кодуванні глобальних даних в проекції Меркатора, представлених в растровій формі, існує проблема різниці у формі та розмірах комірок, що призводить до відхилень в моделі. Проблема може бути вирішена шляхом подання даних в ієрархічній формі. Для цього будується глобальна тесселяція: земна поверхня проектується на октаедр, що містить вісім пронумерованих трикутників. Далі кожен трикутник ділиться на чотири трикутника з'єднанням відрізків середин його сторін. Отримана модифікація квадродерева дозволяє отримувати дозвіл 1 метр при рівні вкладеності дерева, рівному 20.

3.3 Алгоритми на квадродеревах

Розглянемо тепер деякі алгоритми ГІС на квадродеревах: обчислення площі, оверлейний алгоритм і алгоритми визначення суміжності комірок. Щоб визначити площу комірок з деяким значенням в растровому шарі, необхідно обійти дерево і підрахувати кількість комірок, кодованих цим значенням, зважене площею комірки на даному рівні дерева. Обчислимо, наприклад, на карті 1 (рис. 3.6) площу комірок зі значенням "A". Площа SA = 1 * (Count leaf (00,02,03,32)) 4 * (Count leaf (2)) = 8.

Рисунок 3.6 – Оверлейна операція на квадродереві

Оверлейна задача на квадродереві полягає в поєднанні квадродерев двох карт і отриманні нового квадродерева. Для цього потрібно одночасно обійти обидва дерева, слідуючи гілкам, існуючим в обох деревах. У тих вузлах, де в одного з дерев буде відсутнє розгалуження, значення атрибуту переноситься на всі наступні підрівні. У результаті утворюється "широке" дерево, що містить обидва атрибуту (рис. 3.6). Багато операцій ГІС, що працюють з ієрархічними структурами даних, вимагають наявності способів визначення суміжності комірок. Для цього будемо використовувати представлення координат комірок у системі числення з основою 4 і розділяти біти так, як це робилося в скануванні растру за Мортоном. При цьому використовується tesseral-арифметика, в якій перенесення між розрядами здійснюється через дві позиції. Наприклад, різниця 1000 – 1 = 0010, а сума 1 + 0001 = 0100. Будемо розрізняти два випадки: коли комірки, які перевіряються мають коди однакової і різної довжини. Блоки однакового розміру є суміжними, якщо їх подання до tesseral – арифметики відрізняються на 1 або 10. Наприклад, блоки 01 і 03 є суміжними, так як 0011 – 0001 = 10. Блоки 033 і 211 також суміжні, так як 001 111 + 10 = 100 101. Блоки 01 і 30 не є суміжними, так як 1100 – 0001 = 1001. Для визначення суміжності блоків різного розміру коди приводяться до основи 2. Далі з кодом більшої довжини підсумовуються ± 01 і ± 10. З одержаних чотирьох кодів відкидаються як неможливі всі негативні (за переносом). Решта кодів переносом вправо зводяться до меншої довжини. Два блоки є суміжними, якщо трансформований і обрізаний код більшої довжини дорівнює короткому коду. Наприклад, потрібно визначити, є комірки 02 і 2 суміжними. Наведемо коди в двійковій системі 024 = 00102, 24 = 102. Додамо до довгого коду ± 01 і ± 10. Отримаємо 0010 +1 = 00 01, 0010 +10 = 10 00, 0010-10 = 00 00. Різниця 0010-1 негативна, ця комбінація відкидається як неможлива. Вибравши два старших розряди з решти результатів, отримаємо коди 002=04 и 102=24. Один з одержаних кодів дорівнює короткому коду, тому комірки 2 і 02 є суміжними.

3.4 Просторові індекси

У векторних ГІС просторові індекси використовуються для більш швидкого доступу до об'єктів на певній ділянці карти. Індексування просторових об'єктів дозволяє зменшити обчислювальну складність процедур пошуку вкладених об'єктів та об'єктів, що перетинаються, тому індекси є важливою частиною алгоритмів оверлея полігонів. Процес побудови індексу для цифрової карти включає наступні кроки. Спочатку для кожного об'єкта бази даних знаходиться найменший лист квадродерева, що повністю включає об'єкт. Деякі великі об'єкти можуть лежати більш ніж в одному квадранті першого рівня квадродерева. У цьому випадку об'єкти позначаються значенням "NULL". Інші об'єкти позначаються кодом листа, який належить квадродереву. Потім об'єкти сортуються за зростанням отриманого ключа, а сам індексний файл у свою чергу індексується звичайним способом (рис. 3.7). Побудовані таким способом індекси використовуються для пошуку об'єктів, які перетинають заданий полігон або лінію. Для цього визначається мінімальний лист квадродерева, що включає заданий об'єкт. Піднявшись з отриманого вузла до вершини дерева і виконавши обхід піддерева, коренем якого є цей вузол, отримуємо список листя дерева, всередині яких об'єкти можуть перетинатися із заданим об'єктом. Очевидно, просторові індекси, побудовані на квадродеревах, більш ефективні в порівнянні з незалежним впорядкуванням об'єктів по x та y, так як в цьому випадку враховується просторовий характер даних. Індексування квадродеревами найбільш доцільно для дрібних об'єктів (особливо для точок). Великим об'єктам зазвичай відповідають великі блоки. Для них часто потрібно визначати перетин з іншими об'єктами.

Рисунок 3.7 – Індексування цифрової карти квадродеревом

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

Рисунок 3.8 – Індексування цифрової карти R-деревом

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

1. Які порядки сканування растрів Ви знаєте?

2. Дайте визначення, що таке «гомогенний блок».

3. Як відбувається розбиття растра на гомогенні блоки?

4. Наведіть приклад кодування квадродеревом.

5. У чому суть оверлейних операцій на квадродеревах?

6. Наведіть приклад індексування цифрової карти квадродеревом.

4 Алгоритми обчислювальної геометрії

План лекції. Перетин ліній. Операції з полігонами. Оверлей полігонів

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

4.1 Перетин ліній

Операція знаходження перетину ліній є однією з базових у ГІС-аналізі. Вона використовується в оверлейних операціях з полігонами, при з'єднанні і роз'єднання (merge і dissolve) ліній і полігонів. Ця операція є базисною при визначенні знаходження точки в полігоні, при видаленні розщеплених полігонів. Тому ефективні алгоритми визначення перетину ліній важливі в будь-якій векторній ГІС.

Розглянемо найпростіший приклад: потрібно визначити, чи перетинається відрізок AB (4, 2) – (2, 0) з відрізком CD (0, 4) – (4, 0) і якщо так, то в якій точці? Для цього потрібно знайти рівняння прямих AB і CD і вирішити їх спільно (рис. 4.1, а).

Дата добавления: 2014-01-07