Технології побудови тривимірних моделей у ГІС

Рис. 2.3 Різні варіанти перетину зі скануючи ми рядками (див. пояснення у тексті)

2.2 Задача вилучення невидимих ліній і поверхонь при відтворенні тривимірних моделей у ГІС

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

Необхідність видалення невидимих ліній, ребер, поверхонь або об'ємів проілюстрована мал. 2.5. На рис. 2.5, а наведене типове каркасне креслення куба. Його можна інтерпретувати подвійно: як вид куба зверху, ліворуч або знизу, праворуч. Видалення тих ліній або поверхонь, які невидимі з відповідної точки зору, дозволяють позбутися від неоднозначності. Результати показані на рис.2.5, b і c.

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

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

Алгоритми видалення невидимих ліній або поверхонь можна класифікувати за способом вибору системи координат або простору, у якому вони працюють. Алгоритми, що працюють в об'єктному просторі, мають справу з „фізичною” системою координат, у якій описані ці об'єкти. Геоінофрмаційні системи потім відтворюють тривимірні моделі місцевості у географічних чи прямокутних координатах, відповідно до обраної картографічної проекції [20].

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

Об'єм обчислень для будь-якого алгоритму, що працює в об'єктному просторі, і об'єкт, що порівнює кожний, сцени з усіма іншими об'єктами цієї сцени, росте теоретично як квадрат числа об'єктів (n²). Аналогічно, об'єм обчислень будь-якого алгоритму, що працює в просторі зображення й об'єкт, що порівнює кожний, сцени з позиціями всіх системе у системі координат екрана, росте теоретично, як n. Тут n - кількість об'єктів (тіл, площин або ребер) у сцені, а N - число пікселів. Теоретично трудомісткість алгоритмів, працюючих в об'єктному просторі, менше трудомісткості алгоритмів, що працюють у просторі зображення, при n < N. Оскільки N звичайно дорівнює ( 512 )², те теоретично більшість алгоритмів варто реалізовувати в об'єктному просторі [33].

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

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

F ( x, в, z ) = 0

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

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

На рис. 2.6 наведений приклад, де зазначені паралельні площини визначаються постійними значеннями z. Функція F ( x, у, z ) = 0 зводиться до послідовності кривих, що лежать у кожній із цих паралельних площин, наприклад до послідовності

y = f ( x, z ) або y = g ( y, z )

де z постійно на кожній із заданих паралельних площин (рис. 2.2).

Отже, поверхня тепер складається з послідовності кривих, що лежать у кожній із цих площин, як показано на рис. 2.7. Тут передбачається, що отримані криві є однозначними функціями незалежних змінних. Якщо спроецировать отримані криві на площину z = 0, то відразу стає ясна ідея алгоритму видалення невидимих ділянок вихідної поверхні. Алгоритм спочатку впорядковує площини z = const по зростанню відстані до них від точки спостереження. Потім для кожної площини, починаючи з найближчої до точки спостереження, будується крива, що лежить на ній. Алгоритм видалення невидимої лінії полягає в наступному: якщо на поточній площині при деякім заданому значенні x відповідне значення y на кривій більше значення y для всіх попередніх кривих при цьому значенні x, то поточна крива видима в цій точці; у противному випадку вона невидима (рис. 2.3).

Реалізація даного алгоритму досить проста. Для зберігання максимальних значень y при кожному значенні x використається масив, довжина якого дорівнює числу помітних крапок (дозволу) по осі x у просторі зображення. Значення, що збеігаюься в цьому масиві, являють собою поточні значення «обрію». Тому в міру малювання кожної черговий кривий цей обрій «спливає». Фактично цей алгоритм видалення невидимих ліній працює щораз із однією лінією.

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



Рис. 2.6 Січні площини з постійною координатою

Рис. 2.7 Криві в січних площинах з постійною

алгоритм буде вважати їх невидимими. Нижня сторона поверхні робиться видимої, якщо модифікувати цей алгоритм, включивши в нього нижній обрій, що опускається вниз по ходу роботи алгоритму (рис. 2.8) [22, 33].

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

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

У такому випадку використається лінійна інтерполяція значень у між відомими значеннями для того, щоб заповнити масиви верхніх і нижнього плаваючих обріїв, як показано на схемі (рис 2.9). Якщо видимість кривої міняється, то метод з такою простою інтерполяцією не дасть коректного результату. Припускаючи, що операція по заповненню масивів проводиться після перевірки видимості, одержуємо, що при переході поточної кривої від видимого до невидимого стану (сегмент АВ на рис. 2.9), точка (x_n+k, y_n+k ) вважається невидимою.

Рис. 2.8 Принцип „плаваючого горизонту”

Тоді ділянка кривої між точками (x_n, y_n) і (x_n+k, y_n+k) не зображується й операція по заповненню масивів не виконується.

Утвориться зазор між поточною й попередньою кривими Якщо на ділянці поточної кривої відбувається перехід від невидимого стану до видимого, то точка (x_m+k, y_m+k ) „оголошується” видимою, а ділянка кривої між крапками (x_m, y_m) і (x_m+k, y_m+k ) зображується й операція по заповненню масивів проводиться. Тому зображується й невидимий відрізок сегмента CD.

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

Отже, точне значення точки перетинання двох прямолінійних відрізків, які інтерполюють поточна й попередня криві, між точками (x_n, y_n) і (x_n+k, y_n+k ) (рис. 2.6) задається формулами [22, 33]:



Рис.2.9

де

а індекси c і p відповідають поточній і попередній кривим. Отриманий результат показаний на мал. 2.6. Тепер алгоритм викладається більш формально.

Якщо на поточній площині при деякім заданому значенні x відповідне значення y на кривій більше максимуму або менше мінімуму по y для всіх попередніх кривих при цьому x, то поточна крива видима. У противному випадку вона невидима.

Якщо на ділянці від попередні (x_n) до поточні (x_n+k) значення x видимість кривої змінюється, то обчислюється крапка перетинання (x_i).

Якщо на ділянці від x_n до x_n+k сегмент кривій повністю бачимо, то він зображується цілком; якщо він став невидимим, то зображується фрагмент від x_n до x_i; якщо ж він став видимим, то зображується фрагмент від x_i до x_n+k.

3. Моделювання рельєфу і операції з ЦМР із використанням методів растрової і векторної графіки

3.1 Застосування методів комп'ютерної графіки і обчислювальної геометрії для створення тривимірних карт

3.1.1 Растрові моделі

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

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

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

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

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

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

Зрозуміло, що чим більше розмір ячейки, тим більшу площу землі вона покриває, тобто, тим менше (грубіше) роздільна здатність (resolution) растра, тим менша точність положень точок, ліній і областей, представлених даною структурою [21].

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

Растрові структури мають суттєвий недолік - відсутність точної інформації про місцерозташування. Однак растрові структури геопросторових даних мають і багато переваг перед іншими. Зокрема, вони відносно легко розуміються як метод подання простору. Існує також багато спільного споріднення між пікселом, використовуваному в дистанційному зондуванні, і ячйкою растру, використовуваній у ГИС. Це забезпечує легкий перенос супутникових зображень у ГІС, що оперує растрами і це не вимагає яких-небудь змін форматів файлів. Ще однією важливою характеристикою растрових систем є те, що багато функцій, особливо пов'язаних з операціями з поверхнями й накладенням (overlay), легко виконуються за умови представлення даних як растрових файлів [21, 26].

Растрові файли даних при висоти земної поверхні використовуються у ГІС дуже широко. Практично всі сучасні багатофункціональні ГІС працюють з растровими файлами, що описують висоти земної поверхні. У деяких з них растрові моделі є основними для побудови ЦМР та візуалізації тривимірних карт (базові версії „MapInfo Professional”, „Панорама”, „Sufer”, “ПАРК”, „ER Mapper” та інші).

Для створення растрової карти ми збираємо дані у формі двомірного масиву ячейок, де кожна ячейка представляє атрибут окремої теми. Такий двомірний масив називається покриттям (coverage). Ми можемо використати покриття для подання різних типів тематичних даних (висота над рівнем моря, кут нахилу, землекористування, рослинність, тип грунту тощо). У ГІС - пакетах розробки компанії ESRI, починаючи з ArcInfo 3.0, використовується система подачі даних IMGRID [8].

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

Поряд з цим використовується модель МАР системи Пакета аналізу карт (Map Analysis Package, MAP). Вона розроблена Д.Томліном. У цій моделі даних кожне тематичне покриття записується й вибирається окремо по імені карти або назви, що досягається записом кожного показника („картографічної секції” - за Д.Томліном) теми покриття як окремого числового коду або мітки, що може бути доступна окремо при вибірці покриття. Мітка відповідає частині легенди, і з нею зв'язаний власний приписаний їй символ. Таким чином, легко виконуються операції над окремими комірками растру й групами схожих комірок, а результат змін величини вимагає перезапису тільки одного числа на картографічну секцію, спрощуючи тим самим обчислення. Головна перевага методу MAP полягає в тому, що він забезпечує легку маніпуляцію значеннями атрибутів і наборами осередків растра у відношенні "декілька в одному" [7].

Модель даних MAP - одна з найбільш використовуваних растрових моделей на ринку ГІС. Її можна знайти в багатьох формах, від її старої версії на великих машинах до варіантів для Macintosh і PC і сучасних робочих станцій, що працюють під UNIX. Гнучкість і легкість використання зробили її легкодоступним засобом для навчання геоінформатиці, вона може використатися в додаткових модулях комерційних ГІС-пакетів і навіть як основа для повнофункціональных растрових ГІС (приклад - деякі японські ГІС) [8, 10].

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

3.1.2 Векторні моделі

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

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

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

Однією з найбільш поширених векторних моделей для відображення рельєфу у 3D є модель TIN. Сутність моделі TIN у її найменуванні - “нерегулярна трикутна сітка” (Traingulated Irregular Network). У своєму просторовому вираженні - це сітка трикутників - елементів тріангуляції Делоне - з висотними відмітками в її вузлах, що дозволяє представити моделюючу поверхню як багатогранну [8].

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

Модель TIN підтримується багатьма потужними універсальними програмними засобами ГІС, модуль PC&TIN в програмних засобах ГІС „Arc Info”. Однак її використання у технологіях створення ЦМР на основі шару оцифрованих горизонталей цифрових карт, масове виробництво яких налагоджено більшістю національних топографо-картографічних служб, знайшло його суттєві недоліки. Головний із них - “ефект терас”, що виражається у появі морфологічних артефактів - в плоских ділянок у свідомо неможливій геоморфологічної ситуації ( наприклад, по лінії днища V- образних тальвегів). Одна із головних причин - у недостатньої відстані між точками цифрових записів горизонталей у порівнянні із відстанями між самими горизонталями, що характерно для більшості типів рельєфу у їх картографічному відображенні. Поява таких морфологічних артефактів порушує морфографію та морфометрію моделюючого рельєфу і знижує точність і якість самої моделі і її похідних. Один із способів значного покращення якості і морфологічної правдоподібності ЦМР полягає у розширенні моделі TIN шляхом її структурування - введення до неї сітки тальвегів, вододілів і лінії розривів ( брівок, уступів терас тощо ). У алгоритмічній суті це означає використання у “справжніх моделях рельєфу в ГІС” керуючою тріангуляції Делоне замість класичної. Можливі і інші підходи, але суть їх одна - структуризація ЦМР.

Найбільш кардинально цю проблему дослідив і вирішив І.Г.Черваньов (Харківський національний університет) у новому понятті “структурно-цифровій моделі рельєфу” (СЦМР), він розглядав її як сукупність двох точкових множин: базисної (що відповідає тальвегам) і вершинної (що відповідає вододілом), тобто системи інваріантних ліній рельєфу різного порядку, його “скелету”. Така модель, називається “структурно-лінгвістичною моделлю рельєфу”, не передбачає наявність висотних відміток поза сіткою інваріантних ліній і тим самим відрізняється від інших СЦМР. У рамках цієї моделі структура рельєфу визначається наступними складовими:

· “каркасом”, що утворилися решітками інваріантних ліній;

· вертикально складової структури чи порядками рельєфу, який утворює упорядкований набір структурних рівнів;

· горизонтальний складовий, який виражається як просторове сполучення на реальному рельєфі елементів різного порядку.

Можна припустити, останній із типів СЦМР вичерпує можливості покращення достовірності і точності ЦМР на деякій множині вихідних даних, до того ж забезпечує розширення можливості її аналізу. На основі такого підходу створений програмний продукт для створення і обробки ЦМР “Рельєф-Процесор” [8, 28].

Подальший розвиток цифрового моделювання рельєфу пов'язується з новими трьохвимірними моделями просторових даних. Ці моделі засновані на тьохвимірному розширенні “планіметричних” двовимірних моделей. До них належить модель об'ємних пікселів - “векселів” ( тьохвимірне розширення растрової моделі даних ) і трьохвимірне розширення моделі TIN - тетраєдична модель. Два типи “істинно-трьохмірних” моделей здатні описати не тільки поверхню, а і тіла, запозичив підходи і алгоритми так званого “твердотілого моделювання” з комп'ютерної графіки.

3.2 Інтерполяція геопросторових даних при створенні тривимірних моделей у файлах векторної графіки

В даній роботі застосовувалися методики побудови тривимріних моделей рельєфу за допомогою ArcInfo / ArcTIN, ArcGIS / 3D Analyst, MapInfo з модулем «Поверхность». У першому та другому випадку будувалися файли векторної графіки TIN, у другому - полігони Вороного. Також проводилися побудови полігонів Тіссена. Тому дуже важливо розглянути, яким чиному будуються ці зображення, щоб в подальшому оцінити точність зображень і вказати на способи усунення недоліків тривимріних карт. Розглянемо, яким чином утворюються фігури, з яких складаються тривимірні карти, що будуються у ГІС. Для цього розглянемо основні перетворення, які виконуються у ГІС при тріангуляції Делоне і подальшій побудові мережі трикутників і полігонів.

Дані алгоритмт детально описані у роботах О.Р.Мусіна, Л.М.Нестернкa, О.Muller та J.Preparata [10, 36, 38].

Тріангуляція множини точок на площині

Нехай V - множина п різних точок на площині, п > 3, які не всі колінеарні, і Р -множина з п (п - 1) / 2 прямолінійних відрізків (ребер) між точками (вершинами) V. Два ребра p₁, p₂ P, p₁ ? p₂ будемо називати у тому смислі, якщо вони перетинаються в точці, відмінної від їхніх кінцевих точок.

Тріангуляція множини V - це планарный прямолінійний граф G(V, Е), для якого Е - це максимальна підмножина в Р, таке, що ніякі два ребра з Е не перетинаються.

Будь-яка планарная тріангуляція множини В з і крапок, п_b з яких належать границі опуклої оболонки множини V, має 2(і - 1) - п_b трикутників і 3(п - 1) - п_b ребер.

Тріангуляція множини точок у просторі

Нехай Р - множина з п крапок у просторі Е , де d - розмірність простору. Р називається множиною в загальному положенні, якщо розмірність лінійного простору, натягнутого на будь-яку його підмножину з (d + 1) крапок, дорівнює d. Симплексом називається опукла оболонка множини з (d + 1)-ой точки в загальному положенні. Тріангуляцією множини Р називається розбивка внутрішності опуклої оболонки Р на симплекси, вершинами яких є крапки з Р.

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

Структури подання тріангуляції поверхні

Між основними об'єктами, що визначають будь-яку тріангуляцію поверхні - вершинами, ребрами й трикутниками - може бути визначено 9 можливих відносин взаємної суміжності, як показано на схемі (рис. 3.1), де кожна стрілка позначає впорядковане відношення між парою об'єктів, V - вершини, Е -ребра, T -трикутники [37].

Кожне ребро тріангуляції однозначно визначається двома своїми кінцями, кожна двовимірна грань обмежена трьома ребрами й трьома вершинами. Структура даних для кодування тріангуляції звичайно містить список основних об'єктів - одне або трохи із множин Е, V, Т - і деяка множина відносин суміжності.

Рис.3.1

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

Відомо, що кожне з п'яти відносин взаємної суміжності V-E, E-E, T-E, V-V і T-V досить для однозначного подання плоскої тріангуляції. Найбільше часто для кодування тріангуляції використаються структури, засновані на вершинах (vertex-based) і структури, засновані на трикутниках. Vertex застосвуються у ГІС “Arc Info” і зберігаються при використанні файлів *.e00.

Структура, заснована на вершинах, кодує V-V відношення суміжності й містить два списки: список верхової суміжності й список вершин, у якому для кожної вершини v, утримується покажчик на елемент списку верхової суміжності, з якого починається подсписок суміжності вершини V_i. Список суміжності складається з „підсписків” суміжності вершин, розташованих один за одним у порядку зростання номерів вершин. Кожний елемент списку суміжності вершини v_i відповідає ребру тріангуляції v_i, v_j. Перше поле в записі цього ребра - номер вершини v_i, друге поле - покажчик на елемент структури, що відповідає ребру тріангуляції v_i, v_k, що випливає за ребром v_i, v_j, при обході навколо вершини v_i, проти вартовий стрілки. Кожному ребру тріангуляції відповідають два елементи списку верхової суміжності.

Ємнісна складність цієї структури S₁(n) = 4 |Е\ +п ? 13, де |Е\ - кількість ребер тріангуляції. При цьому, якщо списки суміжності зберігаються як двусвязные структури, то S_l (і) = 19n.

На рис. 3.2 приводиться приклад структури, заснованої на вершинах, для тріангуляції множини з 7 точок [37].

Структура, заснована на трикутниках, кодує Т - V і Т - Т відносини суміжності й містить список трикутників. Кожний елемент цього списку відповідає деякому трикутнику t і містить номера вершин трикутника t і номера трикутників, суміжних з t по ребру. Обоє ці множини, вершин і трикутників, упорядковуються в напрямку проти вартовий стрілки. Номер трикутника, розташованого напроти першої вершини, вказується першим. Ємнісна складність цієї структури S_n (n) = 12n.

Засноване на ребрах подання тріангуляції - MWER (modified winged-edge representation) -містить три списки: ребер, вершин і трикутників. Кожний елемент реберного списку, що відповідає деякому ребру е, містить номера двох вершин - кінців цього ребра, номера двох трикутників, суміжних по цьому ребру, і номера двох ребер edge[0] і edge[l]. Якщо P₁ і Р₂ -вершини ребра е, то edge[0] - це перше зустрінуте після е ребро тріангуляції при обертанні навколо pi проти вартовий стрілки; і edge[l] - це перше, зустрінуте після е ребро тріангуляції при обертанні навколо Р₂ проти вартовий стрілки.

У списку вершин для кожної вершини v_i зберігається покажчик на перший з елементів реберного списку, у який входить v_i. У списку трикутників для кожного трикутника t зберігається покажчик на деякий елемент реберного списку, у який входить t. Таким чином, список вершин кодує часткове V - E відношення суміжності, список трикутників кодує часткове Т - E відношення.



Делоне -тріангуляція

Делоне -тріангуляцією DT (V) множини V називається граф, двоїчний діаграмі Вороного для V. Інакше кажучи, це тріангуляція G (V, Е), для якої е = (v_i, v_j) E тоді й тільки тоді, коли полігони Вороного, відповідні v_i, та v_j, суміжні по ребру ("сусіди Вороного"). На схемі наведена діаграма множини Вороного V для n = 16 і двоїчна до неї Делоне-триангуляція (рис. 3.3) [10].

Трикутники Делоне-триангуляции мають наступні властивості: по-перше, окружність, описана навколо будь-якого трикутника TR (v_i, v_j ,v_k), не містить усередині себе точок з V; по-друге, мінімальний розмір кутів всіх трикутників максимізований. Перша властивість називається критерієм кола (circle criterion). Друга властивість називається критерієм мінімаксу кута (МАХ-MIN angle criterion). Доведено, що обидва критерії еквівалентні й будь-який TR (v_i, v_j ,v_k) є Делоне-трикутником (належить Делоне-триангуляції) тоді й тільки тоді, коли він задовольняє критерію кола.

Процедурою локальної оптимізації LOP (local optimization) називається наступна процедура. Нехай е - внутрішнє ребро (на противагу ребру на границі опуклої оболонки) деякої тріангуляції, Q - чотирикутник, що складається із двох трикутників, для якого е - діагональ. Якщо усередину окружності, описаної навколо одного із цих трикутників, попадає четверта вершина чотирикутника Q, то ребро е в тріангуляції заміняється на іншу діагональ, у противному випадку ребро е залишається в тріангуляції і таке ребро називається локально-оптимальним. Доведено, що ітераційним застосуванням LOP до ребер довільної тріангуляції може бути отримана Делоне-тріангуляція (процес збіжний).

Описаний вище алгоритм реалізований у програмних продуктах, випущених ESRI та Mapinfo Corp. У наступному розділі спеціально наводяться карти, які показують планове розташування полігонів Вороного і етапи Делоне-триангуляції, закінчуючи побудовою TIN (мережі нерівних трикутників).

3.3 Операції з моделями рельєфу, побудова карт, профілів, відмивки рельєфу

Розрахунок кутів нахилу та експозиція схилів. Використання ЦМР забезпечує розрахунок різноманітних “часткових характеристик” рельєфу, під яким розуміють похідні від функції висот значень кутів нахилу, експозиція і форми схилів. В першу чергу з'явилися алгоритми розрахунку кутів нахилу та експозиції, які паралельно і незалежно розроблялися в самих різноманітних цілях, ввійшли в інструментарій практично усіх програмних засобах ГІС, використовуються для рішення багатьох задач. Під кутом нахилу розуміється одна із характеристик просторової орієнтації елементарного схилу - кут, що утворюється напрямком ската з горизонтальною площиною, що виражається у градусах чи у безрозмірних величинах схилів, рівних тангенсів кутів нахилу, а також у відсотках чи проміле. Експозиція схилу чисельно рівна азимуту проекції нормалі схилу на горизонтальну площину та виражається в градусах чи по 4, 8, 16 чи 32 румбам [21].

Запропоновано багато формул і алгоритмів розрахунку кутів нахилу і експозицію схилів, що використовуються при обробки растрових ЦМР у вигляді квадратної матриці висот. Всі вони основані на методі сковуючого вікна розміром 2х2 чи 3х3 точки з висотними відмітками у вузлах регулярної квадратної сітки.

Оцінка форми схилів. У продовженні аналізу геометричних властивостей околиці точки на заданій криволінійній поверхні, відповідаючи елементарному схилу, можна оцінити його форму. Методи такої оцінки пропонувалися неодноразово. Наприклад, у роботі, автоматизації побудови карт орієнтації, форми і відносної освітленості схилів, був запропонований алгоритм класифікації елементарних схилів по типам їх поперечних і подовжених профілів у відповідності з підходом до типології елементарних форм При цьому під профілем схилу розумілася величина (чи знак) радіуса кривизни нормального перетину схилу у направленні лінії найбільшого скату (поперечний профіль) чи в перпендикулярному його направленні (повздовжній профіль). С точки зору формалізму диференційної геометрії їм будуть відповідати часткові похідні другого порядку від функції рельєфу (градієнти ізоградієнтної поверхні). Приклад розрахунку форми схилів у середовищі ГІС, заснований на вихідній типології елементарних форм, приводить Р. Дикау [R. Dikau, 1989] у раках запропонованої їм “цифрової геоморфологічної моделі рельєфу”, включаючи не тільки ЦМР, але і й процедури її обробки і розрахункові результати у формі набору 30 морфометричних характеристик рельєфу [21].

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

Автоматизація світлотіньової відмітки рельєфу - найбільш пластичного і широко розповсюдженого способу картографічного зображення рельєфу на середньо- та дрібномасштабних топографічних і загальногеографічних картах у сполученні з гіпсометричній його характеристикою чи зображенням в горизонталях ( ізобатах ) - одна із прикладних задач, поставлених і вирішених уже в перших експериментах по обробці ЦМР у 60-х роках, в умовах використання сучасних програмних засобах ГІС стала рутинною процедурою. Її реалізація заснована АН розрахунках відносної освітленості схилів, точніше ділянок схилів, “елементарних схилів”, утворених трикутними гранями моделі TIN чи площинами комірок матриці висот. Освітленість обчислюється за формулою

I = cosц,

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

I = si nв,

де в - кут падіння променя на площину елементарного схилу; або

I = sin{arctg[tgбcos(A_е - A₀)] + в₀ },

де б - кут нахилу елементарного схилу; A_е - експозиція схилу, яка виміряна істинним ( астрономічним ) азимутом; в₀ - висота джерела світла ( Сонця ) над горизонтом; A₀ - істинний азимут джерела світла Освітленість прирівнюється до нуля, якщо джерело освітленості знаходиться під площиною елементарного схилу ( ц ? 90^_ чи в ? 0^_ ).

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

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

У сполученні з “драпіровкою” цифровим зображенням місцевості таке трьохмірне зображення рельєфу здатна дати їй високореалістичний вигляд із висоти “ пташиного польоту”. Динамічна серія таких зображень, імітуючи політ літального апарату, що належить до класу віртуально-реалістичних зображень, широко використовується в оборонних додатках при навчанні авіаекіпажу. Сторінки багатьох наукових і технічних журналів обійшов приклад із недавньої військової історії, коли ГИС військового призначення Powerscene з трьохмірним віртуально-реалістичним імітатором польотів, створена для тренування екіпажем бомбардировщиків у ході виконанні миротворчої місії НАТО в Боснії (затрати на її створення склали 4 млн. долл. США), була використана в період підготовки дейтонських угод [31].

Аналіз видимості/невидимості. Ця операція обробка ЦМР, практично не виконана у неавтимотазованому режимі, забезпечують оцінку поверхню з точки зору видимості чи невидимості спостерігаючи її частин з деякої точки огляду, розташований , як правило, “над” спостерігаючою поверхнею. Може розглядатися випадок видимості із множин точок ( джерел вивчення ), заданих положенням у просторі.

Сучасні додатки функції аналізу видимості/невидимості пов'язані з оцінкою впливу рельєфу ( в особливості горного ) чи “рельєфоидов” міської забудови на величину зони стійкого радіоприйома (радіовидимості) при проектуванні і оптиматизації розміщення радио- та станцій телемовлення, радіорелейних сіток та систем мобільного радіозв'язку [29].

Побудова профілів. І растрові, і векторні ЦМР дозволяють легко створювати профілі рельєфу місцевості у будь-якому напрямку. Системи типу ArcGIS / 3DAnalyst або ArcGRID дозволяють створювати також профілі, які не просто відображають криву висот земної поверхні, але й показують особливості залягання верств гірських порід, рівень грунтових вод, проходження комунікацій тощо.

4. Створення і візуалізація тривимірної моделі рельєфу тестової ділянки засобами ГІС „ArcGIS/3D Analyst» та «MapInfo»/»Поверхность»

4.1 Підготовка вихідних даних для побудови ЦМР

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

Причинами вибору цієї ділянки були:

1) наявність детальних топографічних карт, зокрема карти районного відділу земельних ресурсів (в умовній місцевій проекції) масштабу 1:10 000 та карти масштабу 1:25 000 видавництва Польщі, рік складання 1939 (проекція Гауса-Крюгера DHDN 1927 р.); незважаючи на те, що топографічна карта стоврена майже 70 років тому, на ній з усією детальністю показаний рельєф Чорткова і прилеглої території, достовірно показані урвища, детально відображена долина р. Дупка, на берегах якої розташоване місто;

2) наявність космічного знімку на територію міста та іншої геопросторової інофрмації по ньому,

3) різкий, контрастний рельєф з перепадом висот майже 200 м;

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

У якості вихідної інформації для побудови тривимірних моделей використовувалися топографічна карта з перерізом горизонталей 20 м (допоміжних горизонталей - 10 м) і карта земель на територію міськради з перерізом горизонталей 10 м. У якості додаткового джерела інформації ми також користувалися космічним знімком „Quick Bird» з роздільною здатністю 61 см.

Тривимірні моделі будувалися у програмних пакетах:

· „ArcGIS 9.1” з модулями „3D Analyst 9.0” та „Spatial Analyst 9.x”;

· „MapInfo professional 6.0» з модулем «Поверхность».

Векторизація ізоліній (тобто горизонталей) виконувалася автоматично, із застосуванням програмного пакету MapEdit (тріал-версія з терміном використання 1 місяць, доступна на сайті компанії-розробника цього векторизатора).

Першим завданням роботи на тестовій ділянці було отримання вихідних даних для аналізу - сканування і оцифровка векторних карт.

Вихідний матеріал вводився за допомогою звичайного планшетного сканера “MUSTEK Bear Paw 2448 CU” та перетворювався у формат TIFF. Далі виконувалалася векторизація растрового зображення. Процес введення інформації розподілявся на декілька етапів. Традиційний технологічний процес, застосовуваний для векторизации ізолінійного матеріалу:

- виділення тематичного шару ізоліній з вихідного растра;

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

- фільтрація чорно-білого растра (видалення випадкового шуму);

- автоматична векторизация;

- зшивка кінців поліліній;

- видалення векторного "сміття";

- оптимізація форми ліній і зменшення числа вершин;

- виявлення помилок автовекторизации;

- корекція помилок;

- присвоєння значень висот ізолініям.

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

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

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

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

Фільтрація чорно-білого растра (видалення випадкового шуму). Для видалення випадкового шуму звичайно використовуються фільтри - математичні процедури. Алгоритми фільтрації, використовуємі у векторизаторі Easy Trace, не тільки видаляють шум, зберігаючи при цьому тонкі лінії, але і частково відновлюють розірвані лінії. При цьому користувач може створювати набори фільтрів, оптимізовані для конкретних растрів.

Неправильний вибір фільтрів може привести до втрати частини інформації, такої, як тонкі лінії і т.п.

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

Видалення векторного "сміття". Ця процедура полягає у видаленні коротких поліліній, утворених при автоматичної векторизации шумів на растрі.

У деяких векторизаторах реалізована можливість побудови запитів на вибір поліліній для видалення за різними критеріями, у тому числі по кількості вершин. Після вибору виробляється видалення обраних об'єктів [10].

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

Контроль помилок топології. Топологічна коректність має на увазі виконання таких умов, як відсутність самоперетинань, перетинань внутрішніх областей замкнутих поліліній (полігонів) з одного шару, відсутність „перехрестів” чи „недоводів” у таких об'єктів, як озера і ріки, що впадають у них, і т.д.

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

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

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

Рис. 4.2 Визначення висот за сіткою квадратів і отримання регулярного масиву точок для подальшої інтерпретації і побудови GRID та ЦМР. На схилах точки навмисно проставлялися частіше

4.2 Створення і візуалізація тривимірної моделі рельєфу засобами ГІС „ArcGIS/3D Analyst»

Для відтворення поверхонь в „3D Analyst” використовуються два типи моделей: Grid (грід) і TIN.

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

Гріди, таким чином, це поверхні по регулярно розподілених точках. Оцінка значень поверхні між цими точками проводиться шляхом осереднення значень у навколишніх точках з урахуванням ступеня їхньої близькості до даної точки (вагою), на основі одного з методів інтерполяції [1].

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