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

Порожнину рота

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

20 серпня 2012 о 22:41

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

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

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

На вході

Після виявлення та обходу кордонів на виході я отримав безліч зовнішніх контурів. Кожні дотичні контури мають різні кольори. Усередині кожного такого контуру міститься також відома кількість внутрішніх контурів.
Таким чином, з погляду «замітання площини», якщо розглядати зовнішні контури окремо, маємо безліч точок, кожна з яких має по одному сусіду праворуч і ліворуч. Тобто. всі точки замкнуті в ланцюзі, немає жодної одиночної «висячої» точки, а так само в кожному з ланцюгів міститься не менше 3-х точок (Малюнок 1).

Малюнок 1

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

Потрібно замітати фігуру трикутниками.

Пошуки

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

Алгоритм

1) Допустимо, для початку, що в розглянутій фігурі всього одна послідовність. Тоді все зводиться до послідовного забирання трикутників. Беремо будь-яку точку і намагаємось побудувати трикутник із сусідніми точками. Якщо трикутник побудувати не вдалося (лінія зв'язує ці дві точки, перетинається з вже побудованими або лінія проходить у зоні відчуження (Малюнок 2), рухаємося до сусідньої точки, допустимо праворуч. Коли черговий трикутник знайдений, заносимо його до списку (Малюнок 3), а точку з якої він будувався видаляємо (Малюнок 4).

Малюнок 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) Перевірити суму протилежних кутів. Вона повинна бути меншою за 180. 2) Обчислити центр описаного кола і порахувати відстань до 4-ої точки. Всім відомо, що умова Делоне виконується, якщо точка знаходиться за межами описаного кола.

Потужність обчислень №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 операцій складання/віднімання.

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

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

1. Скворцов А.В. Тріангуляція Делоне та її застосування. - Томськ: Вид-во Том. ун-ту, 2002. - 128 с. ISBN 5-7511-1501-5

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

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

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

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

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

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

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

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

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

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

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

Недолік:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

20 серпня 2012 о 22:41

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

Обробка зображень ,
Програмування

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

На вході

Після виявлення та обходу кордонів на виході я отримав безліч зовнішніх контурів. Кожні контури, що стикаються, мають різні кольори. Усередині кожного такого контуру міститься також відома кількість внутрішніх контурів.
Таким чином, з погляду «замітання площини», якщо розглядати зовнішні контури окремо, маємо безліч точок, кожна з яких має по одному сусіду праворуч і ліворуч. Тобто. всі точки замкнуті в ланцюзі, немає жодної одиночної «висячої» точки, а так само в кожному з ланцюгів міститься не менше 3-х точок (Малюнок 1).

Малюнок 1

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

Потрібно замітати фігуру трикутниками.

Пошуки

Алгоритм

Малюнок 2

Малюнок 3

Малюнок 4

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

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

Зараз, наскільки я знаю, існують два можливі способи визначити задовольняють трикутники умові Делоне чи ні: 1) Перевірити суму протилежних кутів. Вона повинна бути меншою за 180. 2) Обчислити центр описаного кола і порахувати відстань до 4-ої точки. Всім відомо, що умова Делоне виконується, якщо точка знаходиться за межами описаного кола.

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

Малюнок 10

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

Далі – чиста математика.

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

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 операцій складання/віднімання.

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

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

1. Скворцов А.В. Тріангуляція Делоне та її застосування. - Томськ: Вид-во Том. ун-ту, 2002. - 128 с. ISBN 5-7511-1501-5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рис.3

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

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

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

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

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

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

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

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

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

Рис.4.

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

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

Тріангуляція являє собою апроксимацію поверхні об'єкта, що моделюється, трикутними пластинами, віддаленими від неї на відстані, що не перевищує деякої заданої величини 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).