Дипломная (вкр): Технології побудови тривимірних моделей у ГІС

Растрові файли даних при висоти земної поверхні використовуються у ГІС дуже широко. Практично всі сучасні багатофункціональні ГІС працюють з растровими файлами, що описують висоти земної поверхні. У деяких з них растрові моделі є основними для побудови ЦМР та візуалізації тривимірних карт (базові версії „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].

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

.1.2 Векторні моделі

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

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

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

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

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

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

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

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

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

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

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

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

.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) є Делоне-трикутником (належить Делоне-триангуляції) тоді й тільки тоді, коли він задовольняє критерію кола.