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

Мал. 1

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

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

Теорема про тріангуляцію набору точок.Припустимо, що набір точок S містить n>3 точок і не всі їх колінеарні. Крім того, i точок з них є внутрішніми (тобто лежать усередині опуклої оболонки CH(S). Тоді за будь-якого способу тріангуляції набору S буде отримано точно n + i - 2 трикутників.

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

Мал. 2

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

Мал. 3

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

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

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

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

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

• сплячі ребра: ребро тріангуляції Делоне є сплячим, якщо вона ще не була виявлена ​​алгоритмом;
• живі ребра: ребро живе, якщо воно виявлено, але відома тільки одна область, що примикає до нього;
• мертві ребра: ребро вважається мертвим, якщо воно виявлено і відомі обидві області, що примикають до нього.

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

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

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

Алгоритм реалізований у програмі delaunayTriangulate. Програмі задається масив s з n точок і вона повертає список трикутників, що становлять тріангуляцію Делоне. Реалізація використовує клас кільцевого списку та класи з розділу структури геометричних даних. Як клас Dictionary можна використовувати будь-який словник, що підтримує необхідні операції. Наприклад, можна перевизначити #define Dictionary RandomizedSearchTree .

List * (Point s, int n) (Point p; List *triangles = new List ; Dictionary frontier(edgeCmp); Edge * e = hullEdge (s, n); frontier.insert(e); while (!frontier.isEmpty()) ( e = frontier.removeMin(); if (mate(*e, s, n, p)) ( updateFrontier(frontier, p, e->org); updateFrontier(frontier, e) ->dest, p), triangles->insert(triangle(e->org, e->dest, p));) delete e;) return triangles; )

Мал. 4

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

Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) return 1; if (a->org > b->org) return 1; if (a->dest< b->dest) return -1; if (a->dest > b->dest) return 1; return 0; )

Як змінюється кордон від одного кроку до іншого і як функція updateFrontier змінює словник ребер кордону для відображення цих змін? При підключенні до межі нового трикутника t змінюються стани трьох ребер трикутника. Ребро трикутника t, яке примикає до кордону, з живого стає мертвим. Функція updateFrontier може ігнорувати це ребро, оскільки воно вже має бути видалено зі словника при зверненні до функції removeMin. Кожне з двох ребер трикутника t, що залишилися, змінюють свій стан зі сплячого на живе, якщо вони вже раніше не були записані в словник, або з живого в мертве, якщо ребро вже знаходиться в словнику. На рис. 5 показані обидва випадки. Відповідно до малюнка ми обробляємо живе ребро af і, після виявлення, що точка b є сполученою йому, додаємо трикутник afb до поточної тріангуляції. Потім шукаємо ребро fb у словнику і оскільки його там ще немає і воно виявлено вперше, його стан змінюється від сплячого до живого. Для редагування словника ми повернемо ребро fb так, щоб невідома область, що примикає до нього, лежала праворуч від нього і запишемо це ребро в словник. Потім знайдемо в словнику ребро ba - оскільки воно є в ньому, воно вже живе (відома область, що примикає до нього, - трикутник abc). Так як невідома для нього область, трикутник afb, щойно була виявлена, це ребро видаляється зі словника.

Функція updateFrontier редагує словник frontier, у якому змінюється стан ребра з точки а до точки b:

Мал. 5

Void updateFrontier (Dictionary &frontier, Point &a, Point &b) ( Edge *e = New Edge (a, b); if (frontier.find (e)) frontier.remove(e); else ( e->flip(); frontier.insert( e); ) )

Функція hullEdge виявляє ребро оболонки серед пунктів масиву s. У цій функції фактично застосовується етап ініціалізації та першої ітерації методу загортання подарунка:

Edge *hullEdge (Point s, int n) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }

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

Polygon *triangle (Point &а, Point &b, Point &c) ( Polygon *t = новий Polygon; t->insert (a); t->insert (b); t->insert (c); return t; )

GRID-моделі – моделі регулярних осередків.

Нехай введено систему координат
і і
. Користувач задає
та кроки дискретизації
.

,

- Фізичні координати точки.

Обчислюємо
і
,
- Розрядна сітка.

- квантовані значення. Реальні:

- Параметр алгоритму - кількість точок, - Вага. Чим ближче точка, тим більша вага.

- Ступінь відстані (1 або 2).

Нормувальний коефіцієнт:

Чим ближче до 1, тим більше обліковуються точки з великою вагою.

Це метод IDW - довгий, для кожної т. необхідно знайти сусідів. Набір сусідів може бути знайдено - найближчим. Кожна з точок продукує «кілочок» певної висоти. Від нерегулярності постановок точки багато залежить, для цього беруть
або
тобто. поділяють на сектори та в околиці точки будуємо.

Перевага- Простота

Недолік:

------Квиток 14. Tin-модель. Алгоритми тріангуляції Делоне------

1) Тріангуляційні (tin).

Тріангуляція- Побудова функції у вигляді сукупності шматково - лінійної функції

Тріангуляція- інтерполяція усередині опуклої області.

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

Потрібен алгоритм для побудови оптимальної тріангуляції.

Площина, що проходить через три точки.

1) Знайдемо трикутник, який
;

2)
- Будуємо рівняння площини.

Щоб перевірити чи знаходяться точки всередині трикутника чи ні, необхідно підставити значення рівняння ліній – ребер трикутника. Якщо всі 3 рівняння > 0, то усередині.

Структура подання:

Кожна тріангуляція містить однакову кількість трикутників.

, де - Кількість внутрішніх точок,
- Кількість точок.

Жадібний тріангуляція.

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

Тріангуляція Делоне.

Всередину кола, описаного навколо будь-якого трикутника, не потрапляють точки інших трикутників. Будується єдиним чином.

Фліпом називається перекидання ребер. Вона дозволяє перейти від звичайної тріангуляції до тріангуляції Делоне. Щоб перевірити належність точки до кола: підставити, якщо< R, то внутри.

Умова Делоне.

Рівняння кола, що проходить через три точки:

Якщо менше нуля, то зовнішня, інакше – внутрішня.

-Умова Делоне.

Алгоритм побудови тріангуляції Делоне:

1) Підслідного додавання точок- Простий ітеративний алгоритм:

Є набір
додаємо в трикутник, здійснюється побудова
розбиття трикутника
перебудова. На нульовому етапі додаємо 3-4 фіктивні точки, які свідомо покривають наш конверт, усі крапки всередині. Потім кидаємо крапку, дивимося в який трикутник потрапила, розбиваємо на 3, для кожного трикутника перевіряємо умову Делоне і здійснюємо фліп перекидання ребер. Середня кількість перебудов дорівнює трьом.

Теоретична складність

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

Переміщуємося з першої точки в іншу.

Основні визначення та властивості

Тріангуляція називається планарний граф, всі внутрішні області якого є трикутниками.

Властивості:

· Тріангуляція Делоне взаємно однозначно відповідає діаграмі Вороного для того ж набору крапок.

· Як наслідок: якщо жодні чотири точки не лежать на одному колі, тріангуляція Делоне єдина.

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

· Тріангуляція Делоне максимізує суму радіусів вписаних куль.

· Тріангуляція Делоне мінімізує дискретний функціонал Діріхле.

· Тріангуляція Делоне мінімізує максимальний радіус мінімальної об'ємної кулі.

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

Рис 1. Тріангуляція.

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

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

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

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

Рис 2. Тріангуляція Делоне.

Метод порожньої кулі Делоне. Побудова у загальному випадку

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

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

Рис.3

Симплекси Делоне заповнюють простір без щілин та накладень.

Описана сфера будь-якого симплексу не містить у собі інших точок системи.

Нехай це буде точка j. Продовжимо збільшувати радіус нашої кулі, зберігаючи обидві точки на його поверхні. Збільшуючись, куля досягне якоїсь третьої точки системи, точки k. У двовимірному випадку наш " порожнє коло " у цей час зафіксується, тобто. стане неможливим подальше збільшення його радіусу за збереження кола порожнім. При цьому ми виявляємо елементарну двовимірну конфігурацію трьох точок (i, j, k), що визначає якийсь трикутник, особливістю якого є те, що всередині його описаного кола немає інших точок системи (А). У тривимірному просторі куля не визначається трьома точками. Продовжимо збільшувати його радіус, зберігаючи всі три знайдені точки на поверхні. Це буде можливо, поки поверхня кулі не зустрінеться з четвертою точкою l системи. Після цього рух та зростання порожньої кулі стануть неможливими. Знайдені чотири точки (i,j,k,l) ​​визначають вершини тетраедра, який характерний тим, що всередині описаної сфери немає інших точок системи (А). Такий тетраедр називається симплекс Делоне.

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

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

Застосування тріангуляції Делоне

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

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

Ще одним завданням, що часто виникає в геоінформатиці, є побудова експозицій схилів. Тут потрібно визначити домінуючі напрямки схилів країнами світу і розбити поверхню на регіони, в яких домінує певний напрямок. Так як для горизонтальних ділянок поверхні визначення експозиції не має сенсу, то в окремий регіон виділяють області, що є горизонтальними або мають незначний ухил, наприклад, б<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Рис.4.

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

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

Просторова тріангуляція Делоне

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

Вперше завдання побудови мережі трикутників, що не перекриваються, була поставлена ​​в 1934 році в роботі радянського математика Б. Н. Делоне, який сформулював і відповідні умови.

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

Мережа таких трикутників називається тріангуляцією Делоне, якщо вона задовольняє деяким умовам:

Всередину кола, описаного навколо будь-якого трикутника, не потрапляє жодна з вихідних точок (рис. 5.3);

Тріангуляція є опуклою і задовольняє сформульованій вище умові Делоне;

Сума мінімальних кутів усіх трикутників максимальна із усіх можливих тріангуляцій;

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

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

(5.2)

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

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

Мал. 5.4. Тріангуляція Делоне

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

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

Теорема 1. Тріангуляцію Делоне можна отримати з будь-якої іншої тріангуляції за тією самою системою точок, послідовно перебудовуючи пари сусідніх трикутників ABC і BCD, які не задовольняють умові Делоне, до пари трикутників ABD і ACD (рис. 5.5).

Мал. 5.5.. Перебудова трикутників, що не задовольняють умові Делоне

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

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

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

– перевірка через рівняння описаного кола;

– перевірка із заздалегідь обчисленим описаним колом;

- Перевірка суми протилежних кутів;

- Модифікована перевірка суми протилежних кутів.

У багатьох системах виконується перевірка із заздалегідь обчисленим описаним колом. Основна ідея алгоритму перевірки через заздалегідь обчислені кола полягає в попередньому обчисленні для кожного побудованого трикутника центру та радіусу описаного навколо нього кола, після чого перевірка умови Делоне буде зводитися до обчислення відстані до центру цього кола та порівняння результату з радіусом. Центр і радіус r кола, описаного навколо, можна знайти як , , , r 2 = (b 2 + з 2 - 4аd)/4а 2 , де значення а, b, с, dвизначено за формулами (5.3)

(5.3)

Інший запис рівняння цього кола має вигляд:

(5.5.)

(5.6)

Тоді умова Делоне буде виконуватися тільки тоді, коли для будь-якої іншої точки тріангуляції буде:

(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)

Нині існує безліч алгоритмів побудови тріангуляції Делоне. Багато з відомих алгоритмів використовують визначення тріангуляції Делоне як вторинну ознаку тріангуляції. Тому в таких алгоритмах відзначаються такі слабкості:

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

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

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

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

– для кожної комбінації знаходиться описане коло та координати її центру;

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

До переваг цього алгоритму можна віднести:

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

- безпосередня побудова тріангуляції Делоне, без будь-яких попередніх побудов;

- Простота всіх обчислень і перетворень;

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

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

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

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

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

Злиття цих трикутників у єдину мережу виконується шляхом побудови двох базових ліній (P 0 P 1 та P 2 P 3, Мал. 5,7.а), проведенні кіл змінного радіуса з центром на серединному перпендикулярі до базової лінії (рис. 5.7, б), пошуку вузла, що потрапляє на окружність (точка A, Мал. 5.7. в) та побудові нового трикутника (P0P1A).При цьому може виникнути необхідність видалення трикутника, що вже існує (наприклад, P 0 AB).

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

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

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

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

Фрагмент тріангуляції Делоне з включеними до неї додатковими елементами наведено на рис. 5.9, де праворуч показані вузли, ребра, грані та структурні лінії, а ліворуч – структурні лінії місцевості (берегові лінії, брівки яру та ін.) та точки з відомими відмітками.

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

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

Про точність:

Маючи в своєму розпорядженні пікети на характерних елементах рельєфу (наприклад, вододілах і тальвегах), ми ігноруємо дрібніші елементи в проміжках. При побудові горизонталей1 по таких ребрах трикутників виникає помилка, яка залежить від величини нерівності рельєфу та кута нахилу місцевості. Наприклад, середня похибка зйомки рельєфу не повинна перевищувати 1/3 перерізу рельєфу при кутах нахилу поверхні від 2 до 10 градусів. Можна розрахувати, що при перерізі рельєфу 0,5 м гранична величина пропущеної нерівності (тобто відхилення поверхні землі від прямої, що проходить через сусідні пікети) не повинна перевищувати (0,5/3) * cos10 ° = 0,16 м.

Для точності визначення обсягу ґрунту, що переміщується, важлива також площа, що займається не враховується деталлю рельєфу. Припустимо, в квадраті 20х20 м між двома парами пікетів є циліндрична опуклість з максимальною висотою 0,15 м. Неважко підрахувати, що її неврахування при поданні даної поверхні лише двома трикутниками призведе до помилки приблизно 40 м3. Не так вже й багато, але для ділянки в 1 га, розташованого на пагорбі або верхній (як правило, опуклій) частині схилу, вийде вже 40*25=1000 м3 зайвого ґрунту. Якщо ж брати пікети вдвічі частіше (тобто через 10 м), помилка зменшиться вчетверо і становитиме 250 м3 на гектар. Цей чинник можна врахувати заздалегідь, оскільки позитивні форми рівнинного рельєфу мають опуклу форму, а негативні – увігнуту. Якщо на ділянку, що підлягає зйомці, є наближені дані про рельєф, то радіус кривизни поверхні і необхідну густоту пікетів легко розрахувати за величинами закладення горизонталів або окремим висотним відміткам.

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

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

Геометричний критерій заснований на різниці вписаного та описаного кола навколо розрахункового трикутного елемента. Геометричну оцінку отримаємо за допомогою формули (2), де - кількість трикутників, - радіус вписаного кола, - радіус описаного кола.

Алгоритми побудови тріангуляції

Для побудови тріангуляції існує велика кількість алгоритмів. Вони різняться між собою трудомісткістю, складністю реалізації на ЕОМ, підходами до побудови. Докладніше про алгоритми можна дізнатися у книзі А.В. Скворцова. Розглянемо деякі алгоритми.

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

Крок 1.Генерується список всіх можливих відрізків, що з'єднують пари вихідних точок, і сортується за довжинами відрізків.

Крок 2Починаючи з найкоротшого, послідовно виконується вставка відрізків у тріангуляцію. Якщо відрізок не перетинається з іншими раніше вставленими відрізками, він вставляється, інакше він відкидається.

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

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

Крок 1.На перших трьох вихідних точках будуємо трикутник.

Крок 2У циклі для всіх інших точок виконуємо кроки 3-5.

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

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

Крок 5.Проводяться локальні перевірки новостворених трикутників на відповідність умові Делоне та виконуються необхідні перебудови.

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

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

Крок 1.З множини вихідних структурних відрізків формуємо пов'язаний планарний граф (Малюнок 4,а).

Крок 2Виконується регуляризація графа, тобто. додаються нові ребра, що не перетинають інші, так що кожна вершина графа стає суміжною хоча б з однією вершиною вище за неї і однією нижче. Регуляризація виконується у два проходи за допомогою вертикального плоского замітання. У першому проході знизу нагору послідовно знаходяться всі вершини, з яких не виходять ребра, що ведуть нагору. Наприклад, на (Малюнок 4,б) такою є вершина B. Проводячи горизонтальну лінію, виявляємо найближчі ліворуч і праворуч, що перетинаються нею, ребра графа AD і EF. Потім у чотирикутнику DEHG знаходимо найнижчу вершину і проводимо в неї ребро з B. Аналогічно виконується другий прохід зверху донизу (Малюнок 4, в). У результаті цього кроку кожна область планарного графа стає монотонним багатокутником.

Крок 3Кожну область графа потрібно розбити на трикутники. Для цього можна скористатися алгоритмом неопуклого злиття двох тріангуляцій (Малюнок 4, г).

Малюнок 4. Схема роботи ланцюгового алгоритму тріангуляції: а) вихідні відрізки; б - прохід знизу догори регуляризації графа; в) – прохід зверху вниз; г) - тріангуляція монотонних багатокутників

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

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

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