Метод тріангуляції ділоне. Критерії якості трикутних елементів

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.3

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

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

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

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

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

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

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

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

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

Рис.4.

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

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

Оптимізація алгоритму перевірки умови Делоне через рівняння описаного кола та його застосування

Розповім секрет про те, як швидко перевірити виконання умови Делоне для двох трикутників.
Власне сама оптимізація описана трохи нижче (див. "Оптимізація алгоритму перевірки умови Делоне через рівняння описаного кола"), але розповім про все по порядку.

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

На вході

Малюнок 1

Що треба зробити

Пошуки

Алгоритм

Малюнок 2

Малюнок 3

Малюнок 4

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

2) Повторюємо крок 1, поки не замітаємо всю площину.

3) Якщо послідовностей кілька, тобто. одна, а всередині її ще один або більше внутрішніх контурів (Малюнок 1). Тут потрібно розглянути кожну послідовність окремо. Візьмемо черговий внутрішній контур. З одного зовнішнього та одного внутрішнього зробимо два одиночні контури. Для цього потрібно знайти два «порти» з одного контуру до іншого. Умова для портів: вони не повинні перетинатися між собою (не повинні стикатися навіть кінцями), не повинні перетинатися з лініями контурів (Малюнок 5).

Малюнок 5

Малюнок 6
4) Далі слід ввести по черзі всі внутрішні послідовності вже освічені, відокремлені один від одного (пункт 3) послідовності. Зливати потрібно з тієї, що містить нову. За визначенням, жодна внутрішня послідовність не стосується і не перетинається з іншими (як однією зовнішньою, так і всіма можливими внутрішніми), так що все пройде гладко.
Знайшовши порти (Малюнок 6) легко побудувати нові послідовності та обійти їх пунктами 1 та 2 поточного алгоритму (Малюнок 7).

Малюнок 7

5) Після 4-го етапу маємо список трикутників (Малюнок 8). Як би із завданням уже впоралися, але залишилося зробити картинку красивою: перевірити виконання умови Делоне (Малюнок 9).

Малюнок 8

Малюнок 9

6) Забігаючи наперед розповім про шостий пункт. Він полягає у послідовному прогоні за списком отриманих трикутників пунктом №5. Спочатку мітимо всі трикутники «брудними». У кожному циклі перевіряємо для кожного трикутника умову Делоне. Якщо умова не виконується, то робимо перебудову та помічаємо сусідів та поточний трикутник «брудними». Якщо умова виконується, то мітимо її чистою. У моїй реалізації алгоритму кожен трикутник має посилання на сусідів. У цьому випадку шостий пункт працює найбільш швидко.

Докладніше про п'ятий етап

Потужність обчислень №1: 10 операцій множення/розподілу та 13 операцій складання/віднімання.
Потужність обчислень №2: 29 операцій множення/розподілу та 24 операцій складання/віднімання.

З погляду обчислювальної потужності, яка обчислюється наприклад у книзі , вигідніше варіант №1. Його й реалізував, якби не… (Малюнок 10). Як виявилося після встановлення даного методу на «конвеєр», вийшла невизначеність. Це варіант, коли сам кут А більший за 180 градусів. Він у книзі як із окремих приватних методів. А з цим зникає вся його елегантність, прозорість та продуктивність. А також згодом виявилося, що метод №2 можна дуже суттєво оптимізувати.

Малюнок 10

Оптимізація алгоритму перевірки умови Делоне через рівняння описаного кола

Отже маємо:
Перевірка умови для точки M(X, Y) рівнянням кола, що проходить через точки A(x1, y1), B(x2, y2), C(x3, y3), можна записати у вигляді:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ sign a ≥ 0

Подробиці можна взяти у чудовій книзі. (Ні, не я її автор)
Отже, sign a - це знак напряму обходу, від початку я будував трикутники за годинниковою стрілкою, отже його можна опустити (він дорівнює одиниці).

A(x1-X, y1-Y), B(x2-X, y2-Y), B(x3-X, y3-Y);

D >= 0

Малюнок 11

Просто чи не так?

Згідно з книгою, знову ж таки,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Маємо: 15 операцій множення/розподілу та 14 операцій складання/віднімання.

Дякую за увагу. Чекаю на критику.

Список використаної літератури

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

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

Вперше завдання побудови мережі трикутників, що не перекриваються, була поставлена ​​в 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.

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

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

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

Модель 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 на гектар. Цей чинник можна врахувати заздалегідь, оскільки позитивні форми рівнинного рельєфу мають опуклу форму, а негативні – увігнуту. Якщо на ділянку, що підлягає зйомці, є наближені дані про рельєф, то радіус кривизни поверхні і необхідну густоту пікетів легко розрахувати за величинами закладення горизонталів або окремим висотним відміткам.

Структура лекції Визначення Визначення Області застосування Області застосування Властивості тріангуляції Делоне Властивості тріангуляції Делоне Методи побудови тріангуляції Делоне Методи побудови тріангуляції Делоне Методи покрокового введення Методи покрокового введення Методи покрокової вибірки

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

Оптимальна тріангуляція - тріангуляція з мінімальною сумою довжин усіх ребер графа. Оптимальна тріангуляція - тріангуляція з мінімальною сумою довжин усіх ребер графа. ! Затребувана, але дуже трудомістка задача O(2 n)! На практиці використовують апроксимації (наближення до) оптимальної тріангуляції: «Жадібна» тріангуляція O(N 2 *logN) «Жадібна» тріангуляція O(N 2 *logN) Тріангуляція Делоне O(N*logN) Тріангуляція Делоне O(N*logN) Визначення оптимальної тріангуляції

Тріангуляція Делоне (DT(S)) – опукла тріангуляція, що задовольняє умові Делоне: Тріангуляція Делоне (DT(S)) – опукла тріангуляція, що задовольняє умові Делоне: всередину кола описаного навколо будь-якого її трикутника не повинна потрапляти жодна з вершин. всередину кола описаного навколо будь-якого її трикутника не повинна потрапляти жодна з вершин графа. Визначення тріангуляції Делоне У слові Делоне виконується У слові Делоні не виконується Б.М. Делоне ()

Застосування тріангуляції Делоне В інших задачах ВГ В інших задачах ВГ Мінімальний кістяк набору точок Мінімальний кістяк набору точок Побудова буферних зон Побудова буферних зон Побудова діаграми Вороного (зон близькості) Побудова діаграми Вороного (зон близькості) Знаходження максимального порожнього оточення. та ін У додатках у КГ, ГІС, ГМ у САПР У додатках у КГ, ГІС, ГМ у САПР Полігональні моделі поверхонь Полігональні моделі поверхонь Рельєфи у ГІС, скульптури, пром.моделі, моделі в іграх, Рельєфи у ГІС, скульптури, пром .моделі, моделі в іграх, Чисельний аналіз моделей Чисельний аналіз моделей Ізолінії, Ізокліни, МКЕ. Ізолінії, Ізокліни, МКЕ.

Властивості будь-якої опуклої тріангуляції 1. Для набору n точок з яких m - внутрішні Кількість трикутників тріангуляції = n + m – 2 Кількість трикутників тріангуляції = n + m – 2 Кількість ребер тріангуляції 3n – 6 Кількість ребер тріангуляції 3n – 6Приклад: – 13 Точок (n) – 13 Внутрішніх (m) – 4 Внутрішніх (m) – 4 Трикутників – 15 = Трикутників – 15 = Ребер – 26 3*13-6 = 33 Ребер – 26 3*13-6 = 33

Властивості тріангуляції Делоне 2. Тріангуляція Делоне має максимальну суму мінімальних кутів всіх трикутників серед усіх можливих тріангуляцій. 3. Тріангуляція Делоне має мінімальну суму радіусів кіл, описаних біля трикутників, серед усіх можливих тріангуляцій. Тріангуляція Делоне НЕ тріангуляція Делоне

Методи побудови тріангуляції Делоне Методи покрокового введення Методи покрокового введення Ітеративні алгоритми () Ітеративні алгоритми () Методи покрокової вибірки Методи покрокової вибірки Алгоритми прямої (покрокової) побудови (3) Алгоритми прямої (покрокової) побудови (3) ) Алгоритми злиття (2) Методи сканування Методи сканування Ітеративні алгоритми зі зміненим порядком додавання точок (1.4) Ітеративні алгоритми зі зміненим порядком додавання точок (1.4) Двопрохідні алгоритми (4) Двопрохідні алгоритми (4)

Методи покрокового введення Ітеративні алгоритми () Загальна схема ітеративних алгоритмів побудови тріангуляції Делоне 1. На перших трьох точках побудувати один трикутник 2. Цикл по всіх точках, що залишилися, p i набору S 3. Знайти найближчий до точки p i трикутник i три трикутник t j. трикутника t j, то побудувати трикутники до найближчого ребра. 5. Якщо точка p i усередині трикутника t j то розбити трикутник на три. 6. Якщо точка p i на ребрі, то розбити прилеглі трикутники на пари. 7. Якщо умова Делоне для сусідів порушилася, то перебудувати сусідні трикутники. Варіанти прискорення пошуку трикутників: Індексування трикутників (дерева) – O(log n) Індексування трикутників (дерева) – O(log n) Кешування трикутників (сітки) – O(с) Кешування трикутників (сітки) – O(с)

Методи покрокової вибірки Алгоритми прямого (покрокового) побудови (3) Будувати одразу потрібні трикутники, не перебудовуючи що вже побудовано. Загальна схема алгоритмів прямої побудови тріангуляції Зручно використовувати стек ще необроблених ребер. 1. Знайти будь-яке ребро q опуклої оболонки набору точок S. 2. Занести ребро q у стек необроблених ребер. 3. Цикл поки стек необроблених ребер не порожній. 4. Витягти ребро v зі стека. 5. Для ребра v знайти точку p, яка відповідає умові Делоне (сусіда Делоне) 6. Якщо сусід Делоне p знайдено, то 7. Побудувати трикутник від ребра v до точки p. 8. Занести нові ребра нового трикутника у стек необроблених ребер. Варіанти прискорення пошуку сусіда Делоне: Індексування точок k-D-деревом – O(log n) Індексування точок k-D-деревом – O(log n) Клітинне індексування точок – O(с) Клітинне індексування точок – O(с)

Процес роботи жадібного алгоритму тріангуляції Делоне

Методи декомпозиції Алгоритми злиття (2) Розбиття на підмножини, незалежна обробка, злиття результатів. Загальна схема алгоритмів злиття 0. Якщо точок в наборі S не більше 3 шт, побудувати інакше 1. Розбити набір точок S на приблизно рівні підмножини. 1. Розбити набір точок S на приблизно рівні підмножини. 2. Побудова тріангуляції для підмножин. 2. Побудова тріангуляції для підмножин. 3. Злиття отриманих тріангуляцій в одну. 3. Злиття отриманих тріангуляцій в одну. Способи поділу на підмножини Ортогональними прямими По діаметру опуклої оболонки По діаметру опуклої оболонки Полосами Смугами

Алгоритми злиття (2) Способи злиття тріангуляцій «Видаляй і буд» (перевірка до побудови) «Видаляй і буд» (перевірка до побудови) «Буд і перебудовуй» (перевірка після побудови) «Буд і перебудовуй» (перевірка після побудови) «Буд , перебудовуючи» (перевірка під час побудови) «Буд, перебудовуючи» (перевірка під час побудови)

Загальна схема ітеративних методів із зміненим порядком додавання точок 1. Упорядкувати точки (побудувати перелік точок подій) 2. Цикл сканування по всіх точках-подіях 3. Для кожної точки p i побудувати трикутники до попереднього трикутника. 4. Якщо умова Делоне для сусідів порушилася, перебудувати сусідні трикутники. Методи сканування Ітеративні алгоритми зі зміненим порядком додавання точок (1.4)

Методи сканування Способи впорядкування точок подій Прямолінійне Прямолінійне Полярне (кругове, віялоподібне) Полярне (кругове, віялоподібне) Смужене Смужене Квадратне Квадратне По кривій Гільберта По кривій Гільберта По Z-коду По Z-коду Потрібно Мінімізувати кількість перебудов Мінімізувати кількість перебудов

Зведені характеристики методів тріангуляції Делоне Метод тріангуляції Час у середньому Час у гіршому Час сек/т Простотареалізація. Методи покрокового введення Методи покрокового введення Ітеративні алгоритми () O(n)- O(n 3/2) O(n 2) 1,5-9,2 2-5 Методи покрокової вибірки Методи покрокової вибірки Метод прямої побудови (3) Метод прямої побудови (3) O(n)- O(n 2) O(n 2) -2 Методи декомпозиції Методи декомпозиції Методи злиття (2) Методи злиття (2) O(n)- O(nlogn) O (nlogn)- O(n 2) 2,5-4,52-3 Методи сканування Методи сканування Ітеративні із зміненим порядком додавання точок (1.4) Ітеративні із зміненим порядком додавання точок (1.4)O(n) O(n 2) 1 ,9-5,34-5 Двопрохідні методи (4) Двопрохідні методи (4) O(n)- O(n 2) O(nlogn)- O(n 2) 2,2-15,41-5 Скворцов рекомендує: ітеративний алгоритм з динамічним кешуванням

А сьогодні про що? Про тріангуляцію Делон! Визначення Визначення Області застосування Області застосування Властивості тріангуляції Делоне Властивості тріангуляції Делоне Методи побудови тріангуляції Делоне Методи побудови тріангуляції Делоне Методи покрокового введення Методи покрокового введення Методи покрокової вибірки Методи покрокової вибірки Методи декомпозиції

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

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

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

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

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

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

Мал. 9.7.1. Випукла область із заданими точками всередині

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

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

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

Мал. 9.7.2. Вибір третьої точки алгоритму Делоне

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

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

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

Через вершини А, В і будь-яку, що не лежать з ними на одній прямій, вершину можна провести коло. Як третя вершина трикутника виберемо вершину V, відповідна якій коло, не містить інших вершин з тієї ж сторони щодо відрізка АВ, з якої лежить точка V. Для граничного ребра в загальному випадку можна знайти одну таку вершину. Будемо називати її найближчою. Центр кола, що проходить через точки А, В та V, лежить на перетині перпендикулярів до середин відрізків АВ, BV і VА. Положення центру кола характеризуватимемо параметром t відрізка MN, перпендикулярного ребру АВ, що дорівнює з ним по довжині і проходить через середину ребра АВ.

Мал. 9.7.3. Процес тріангуляції Делоне

Для всіх вершин, що лежать ліворуч від відрізка АВ, найближча вершина має найменший параметр t. Відповідна найближчій вершині коло не містить інших вершин зліва від відрізка АВ. Нехай вершини А, В та V описуються двомірними радіус-векторами відповідно. Радіус-вектори середин відрізків АВ і BV дорівнюватимуть

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

Для найближчої ліворуч до відрізка АВ вершини параметр t має мінімальне значення.

Зорієнтуємо всі граничні ребра так, щоб область, що підлягає тріангуляції, лежала зліва від кожного з них. Побудову трикутників розпочнемо з будь-якого граничного ребра. Знайдемо для нього найближчу вершину, відповідне коло якої не містить інших вершин. Нехай для граничного ребра АВ знайдено найближчу вершину V. Тоді побудуємо трикутник ABV і переведемо ребро АВ у розряд неактивних. Неактивними будемо називати ребра та вершини, які не беруть участь у алгоритмі тріангуляції. Якщо серед граничних ребер немає ребро BV, то на відрізку VB побудуємо нове граничне ребро. Якщо ж серед граничних ребер є ребро BV, то переведемо його і вершину в розряд неактивних. Якщо серед граничних ребер відсутня ребро VA, то на відрізку AV збудуємо нове граничне ребро. Якщо серед граничних ребер є ребро VA, то переведемо його і вершину А в розряд неактивних. Процес тріангуляції показано на рис. 9.7.3.

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

Тріангуляцію закінчимо, коли всі вершини та ребра стануть неактивними. Результат тріангуляції заданої області наведено на рис. 9.7.4.

Тріангуляція шляхом корекції.

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

Параметричні відстані між сусідніми лініями відповідно до формули (9.4.8) візьмемо рівними

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

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

Мал. 9.7.5. Тріангуляція поверхні з прямокутною областю визначення параметрів

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

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

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

Мал. 9.7.6. Незакінчена тріангуляція поверхні

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

На непересічених сторонах осередків другої групи побудуємо граничні ребра і направимо їх так, щоб відповідний осередок знаходився ліворуч від ребра. Навколо осередків першої групи побудуємо замкнуту ламану лінію (можливо кілька замкнутих ліній) так, щоб при русі нею не розбита на трикутники частина області лежала зліва, якщо дивитися назустріч нормалі поверхні. Прямолінійні ділянки цієї ламаної лінії також будемо використовувати як граничні ребра. Ми вважатимемо всі ребра рівноправними. Для завершення тріангуляції нам необхідно збудувати трикутники між граничними ребрами. Для кожного ребра шукатимемо вершину, яка лежить зліва від нього і може бути використана для побудови трикутника. Пошук вершини здійснюватимемо лише серед тих вершин, які лежать в одному осередку з ребром. Для вибору вершини використовуємо метод Делоне, описаний вище, та проілюстрований на рис. 9.7.2. Якщо така вершина знайдена, слід перевірити, чи не перетинаються два нових ребра трикутника з якимось граничним ребром. Нехай для граничного ребра АВ знайдено найближчу вершину V і перевірено, що відрізки BV та VА не перетинають інші граничні ребра. Тоді збудуємо трикутник ABV і переведемо ребро АВ у розряд неактивних. Якщо серед граничних ребер відсутнє ребро BV, то на відрізку VВ побудуємо нове граничне ребро, якщо серед граничних ребер є ребро BV, то переведемо його і вершину В в розряд неактивних. Якщо серед граничних ребер відсутня ребро VA, то на відрізку AV побудуємо нове граничне ребро, якщо серед граничних ребер є ребро VA, то переведемо його і вершину А в розряд неактивних.

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

Мал. 9.7.7. Тріангуляція методом корекції

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

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

Тріангуляція методом поглинання.

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

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

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

Якщо потрібно на площині знайти точку поруч із точкою в напрямку, заданому кутом з віссю і, то її параметрами будуть

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

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

Координати точки Р визначаються через координати точок ВС

Кут відрізка ОР з горизонталлю визначається рівністю

(9.7.8)

Ці дані дозволяють визначити положення точки Р щодо еліпса (9.7.5).

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

Мал. 9.7.9. Побудова трикутника

Мал. 9.7.10. Результуючий полігон

Мал. 9.7.11. Побудова двох трикутників

Мал. 9.7.12. Результуючий полігон

Такі ситуації показано на рис. 9.7.13. Вони можуть виникнути, коли сторони збудованих трикутників перетнуть несуміжні з ними сторони робочого полігону. Перед побудовою нового трикутника, як у випадку, показаному на рис. 9.7.9, так і у випадку, показаному на рис. 9.7.11 повинна бути виконана перевірка на відсутність самоперетину результуючого полігону.

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

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

Мал. 9.7.13. У цьому кутку будувати трикутники не можна

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

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

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

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

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

Побудуємо трикутники на точках OCF і CEF і між точками Про і З робочого полігону вставимо точки внутрішнього полігону, починаючи з точки F і закінчуючи точкою Е. Тим самим ми розірвемо робочий полігон на відрізку ОС, розірвемо внутрішній полігон на відрізку EF і об'єднаємо їх та ЄС.

Мал. 9.7.14. Побудова двох трикутників

Мал. 9.7.15. Злиття зовнішнього та внутрішнього полігонів

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

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

Мал. 9.7.16. У цьому кутку будувати трикутники не можна

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

Інші способи тріангуляції.

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

Тріангуляція тіла.

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

Мал. 9.7.17. Узгодженість граничних полігонів граней тіла

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

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

Побудовані триангуляції трикутники використовуються для отримання тонових зображень. На рис. 9.7.18 та 9.7.19 наведено тріангуляцію грані листового тіла, тонове зображення якого показано на рис. 6.5.1.

Мал. 9.7.18. Тріангуляція грані тіла методом корекції

Розбиття області визначення параметрів поверхні на трикутники може бути використане в інтегралах (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) при обчисленні геометричних характеристик тел. При чисельному інтегруванні параметричний крок для кривих слід обчислювати за формулою (8.11.5), а поверхонь параметричні кроки слід обчислювати за формулами (8.11.1) і (8.11.2).