2. Нерегулярні тріангуляційних мережі (tin)

Нерегулярні тріангуляційні мережі (Triangulation Irregular Network – TIN) є альтернативою растровим DEM і використовуються в багатьох геоінформаційних системах, системах автоматизованого картографування, пакетах побудови контурів. Моделі TIN розроблені в 1970-х роках як простий спосіб побудови поверхонь по нерегулярно розташованим точкам.

Модель TIN володіє деякими перевагами перед растровими DEM. У першу чергу, розташування точок адаптовано до місцевості: у рівнинних ділянках точки розташовані рідше, а гористих – частіше. Вибіркові точки з'єднуються прямими відрізками, що утворюють трикутники, всередині яких поверхня задається площиною. Поверхня безупинна, трикутники з'єднані між собою. Структури даних у TIN-моделях більш компактні і економічні: TIN-моделі з сотень точок може відповідати растрова DEM з десятків тисяч точок. Незважаючи не простоту моделі, створення TIN потребує вирішення низки складних завдань: як розміщувати вибіркові точки, як з'єднувати точки в трикутники, як моделювати поверхню всередині трикутника.

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

Алгоритм Фаулера – Літтла заснований на пошуку особливих точок поверхні – піків, хребтів, западин і т.п. Поверхня перевіряється ковзним вікном розміру 3x3. При цьому сусіди центральної комірки позначаються плюсом, якщо їх висота більше, і мінусом якщо менше. Очевидно, точка є піком, якщо всі вісім її сусідніх комірок позначені мінусом. Аналогічно, точка є западиною, якщо всі вісім її сусідніх комірок позначені плюсом. Точка є ущелиною або перевалом, якщо плюси і мінуси навколо точки утворюють хоча б два повних цикли:

{ + + – – – – + + } = 2 цикли; { + – + – + – + – } = 4 цикли.

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

Алгоритм VIP – (дуже важлива точка) на відміну від попереднього алгоритму, в якому ідентифікуються основні особливості місцевості, перевіряє поверхню локально, використовуючи вікно 3x3. Це спрощення вперше використано в ГІС ESRI Arc / Info. Комірка в растровій DEM має вісім сусідів, які утворюють чотири трійки (рис. 5.8, а).

Рисунок 5.8 – Алгоритм VIP:

а) чотири трійки комірок; б) розрахунок варіацій

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

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

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

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

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

Рисунок 5.9 – Алгоритм Уотсона: а) вихідне розбиття; б) вибір трикутників, описана навколо яких окружність містить нову точку,

в) видалення трикутників; г) розбиття опуклого багатокутника

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

Існує два основних способи зберігання TIN: за трикутниками і по точках. При кодуванні мережі по трикутниках для кожного трикутника в базі даних створюється запис, що містить його унікальний номер, координати трьох його вершин, а також номери трьох суміжних з ним трикутників (рис. 5.10, а). У другому способі (рис. 5.10, б) для кожної точки розбиття зберігається її унікальний номер, координати і список точок, з якими вона з'єднана прямими (за годинниковою стрілкою).

Розглянемо спосіб обчислення нахилу поверхні та експозиції схилу в TIN-моделі. Для цього обчислимо нормалі до кожного трикутнику розбиття.

Трикутник задається трьома точками , , .

Рисунок 5.10 – Моделі зберігання TIN: а) за трикутниками; б) за крапками

Тоді нормаль P до площини трикутника може бути виражена через векторний добуток двох його сторін як

Тепер обчислимо направляючі косинуси і проекцію нормалі P до горизонтальної площини:

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

, .

Рисунок 5.11 – Графічне представлення положення кута нахилу і

експозиції схилу трикутника

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

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

За растровим DEM і по тріангуляційним мережам можна побудувати карти розподілу характеристики по території. Для цього потрібно задати список значень z, за якими будуть проведені ізолінії. Наприклад, можна взяти максимальне і мінімальне значення характеристики, розділити отриманий інтервал на кілька частин і з отриманим кроком провести ізолінії.

Ізолінії заданої висоти будуються таким способом. Розглянемо всі комірки растрової DEM (або всі трикутники триангуляційної мережі). Будемо шукати перетини комірок (трикутників) з горизонтальною площиною Z = const. З отриманих відрізків потрібно зібрати полілінії. Для цього слід об'єднувати суміжні відрізки. Полілінії можуть бути згладжені, наприклад, за допомогою сплайн-функцій (рис. 5.12).

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

Рисунок 5.12 – Побудова ізоліній в растровій моделі рельєфу (а)

і в триангуляційній мережі (б)

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

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