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

Тріангуляція Делоне і описані навколо трикутників кола

Тріангуля́ція Делоне́ для множини точок P на площині — це така тріангуляція DT(P), що жодна точка множини P не знаходиться всередині описаних довкола трикутників кіл в множині DT(P). Тріангуляція Делоне дозволяє якомога зменшити кількість малих кутів. Цей спосіб тріангуляції був винайдений Борисом Делоне в 1934 році[1].

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

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

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

Зв'язок з діаграмою Вороного

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

Тріангуляція Делоне зі всіма колами та їх центрами (червоні).

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

d-вимірні тріангуляції

Для множини P точок d-вимірного Евклідового простору, тріангуляція Делоне це тріангуляція DT(P) така що жодна з точок з P не лежить всередині гіперсфери описаної навколо будь-якого симплекса з DT(P). Відомо що[2] існує єдина тріангуляція Делоне для P, якщо P множина точок в загальній позиції; така що не існує підпростору розмірності k що містить ${\displaystyle k+2}$ точок ні k-сфери що містить ${\displaystyle k+3}$ точок, для ${\displaystyle 1\leq k\leq d-1}$ (тобто, наприклад для множини точок в ${\displaystyle \mathbb {R} ^{3}}$ не існує трьох точок що лежать на одній прямій, не існує чотирьох що лежать в одній площині, і жодні п'ять точок не лежать на одній сфері).

Задача знаходження тріангуляції Делоне для множини точок в d-вимірному просторі може бути зведена до задачі знаходження опуклої оболонки множини точок в ${\displaystyle (d+1)}$-вимірному просторі, додаючи кожній точці p додаткову координату яка дорівнює ${\displaystyle |p|^{2}}$, беручи нижню частину опуклої оболонки, і відображаючи її назад в d-вимірний простір видаленням останньої координати. Так як опукла оболонка єдина, то тріангуляція теж, вважаючи, що всі сегменти опуклої оболонки — симплекси. Не симплексні сегменти з'являються лише коли ${\displaystyle d+2}$ різних точок лежить на одній d-гіперсфері, тобто точки не знаходяться в загальній позиції.

Властивості

Нехай n — кількість точок, а d — розмірність.

• Об'єднання всіх симплексів в тріангуляції — опукла оболонка точок.
• Тріангуляція Делоне містить щонайбільше O(n^⌈d / 2⌉) симплексів.[3]
• Якщо на площині (d = 2), b вершин входять до опуклої оболонки, то будь-яка тріангуляція точок має щонайбільше ${\displaystyle 2n-2-b}$ трикутників, і ще одну зовнішню «грань» (див. характеристика Ейлера).
• На площині, кожна вершина має в середньому шість інцидентних трикутників.
• На площині, тріангуляція Делоне максимізує найменший кут. Найменший кут в тріангуляції Делоне, буде не меншим ніж в будь-якій іншій тріангуляції. Правда тріангуляція Делоне не обов'язково мінімізує максимальний кут.
• Коло описане навколо довільного трикутника тріангуляції не містить всередині жодних інших вхідних вершин.
• Якщо коло що проходить через дві вхідні точки не містить всередині жодних інших, тоді сегмент що з'єднує ці дві точки є ребром тріангуляції Делоне цих точок.
• Тріангуляція Делоне множини точок в d-вимірному просторі є проєкцією точок опуклої оболонки на (${\displaystyle d+1}$)-мірний параболоїд.
• Найближчий сусід b довільної точки p лежить на ребрі bp тріангуляції Делоне, бо граф найближчих сусідів — підграф тріангуляції Делоне.

Заміна спільного ребра

Якщо розглядати два трикутники ABD та BCD зі спільним ребром BD (див. малюнки), якщо ${\displaystyle \alpha +\gamma \leq 180^{\circ }}$, трикутники задовольняють умові Делоне.

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

• 
  Тріангуляція не відповідає умові Делоне бо ${\displaystyle \alpha +\gamma >180^{\circ }}$.
• 
  І описані навколо трикутників кола містять більше трьох точок.
• 
  Заміна спільного ребра створює для чотирьох точок тріангуляцію що відповідає умові Делоне.

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

Алгоритми

Багато алгоритмів для обчислення тріангуляції Делоне спираються на швидкі операції для визначення того, чи точка знаходиться всередині описаного навколо трикутника кола, і ефективних структур даних для зберігання трикутників та ребер. В двовимірному випадку, якщо D знаходиться всередині кола описаного навколо A, B, C треба перевірити чи визначник:[4]

${\displaystyle {\begin{vmatrix}A_{x}&A_{y},&A_{x}^{2}+A_{y}^{2},&1\\[6pt]B_{x}&B_{y},&B_{x}^{2}+B_{y}^{2},&1\\[6pt]C_{x}&C_{y},&C_{x}^{2}+C_{y}^{2},&1\\[6pt]D_{x}&D_{y},&D_{x}^{2}+D_{y}^{2},&1\end{vmatrix}}={\begin{vmatrix}A_{x}-D_{x},&A_{y}-D_{y},&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\[6pt]B_{x}-D_{x},&B_{y}-D_{y},&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\[6pt]C_{x}-D_{x},&C_{y}-D_{y},&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\\[6pt]\end{vmatrix}}>0}$

Коли A, B та C впорядковані проти годинникової стрілки визначник додатній тоді і тільки тоді, коли D знаходиться всередині описаного кола.

Алгоритм заміни ребра

Як вже згадувалось вище, якщо трикутники не задовольняють умові Делоне, ми можемо замінити ребро. З цього можна вивести очевидний алгоритм: побудувати хоч якусь тріангуляцію, а потім замінювати ребра аж поки вона не буде задовольняти умові Делоне. На жаль, це може зайняти O(n^2) замін ребер, і не узагальнюється на три виміри і більші.[2]

Інкрементний

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

Якщо ми будемо додавати вершини в випадковому порядку, виявиться (через дещо складне доведення), що кожна вставка буде замінювати в середньому лише O(1) трикутників, хоча іноді й більше.[5] Це залишає можливість оптимізувати час виявлення точки. Ми можемо зберігати історію поділів та замін ребер: кожен трикутник зберігає вказівник на два, чи три трикутники що його замінили. Щоб виявити який трикутник містить v, ми починаємо з кореневого трикутника, і ідемо по вказівнику який показує на менший трикутник що міститьv, поки не знайдемо трикутника якого ще не замінювали. В середньому, це займе час O(log n). Загалом для всіх вершин це займе час O(n log n).[2].

Алгоритм Бов'єра-Ватсона (Bowyer–Watson algorithm^[en]) описує інший підхід до інкрементної побудови, без необхідності заміни ребер.

Розділяй і володарюй

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

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

Парадигма «розділяй і володарюй» для виконання тріангуляцій в d вимірах описується в «DeWall: A fast divide and conquer Delaunay triangulation algorithm in E^d».[7]

Показано що «розділяй та володарюй» є найшвидшою технікою генерації триангуляції Делоне.[8][9]

Замітання

Алгоритм Форчуна використовує прийом замітальної прямої щоб досягти часу O(n log n) у плоскому випадку.

Замітальна оболонка

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

Емпіричні результати показують що алгоритм працює приблизно вдвічі швидше ніж Qhull. Він має вільні реалізації на C++ та C#.[11]

Застосування

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

Для моделювання місцевості, чи інших об'єктів що задані множиною вибраних точок, тріангуляція Делоне дає гарний набір трикутників для використання як полігони моделі. Зокрема, тріангуляція Делоне уникає вузьких трикутників (з маленькими кутами, бо вони мають великі описані кола, порівняно з власною площею). Дивіться статтю тріангульована нерегулярна мережа (triangulated irregular network^[en]).

Тріангуляція Делоне для випадкового набору 100 точок площини.

Тріангуляції Делоне часто використовуються для побудови мешів для методу скінченних елементів, через гарні кути, та швидкі алгоритми побудови. Зазвичай, об'єкт для якого потрібно побудувати меш, грубо задається як симпліційний комплекс; щоб він був чисельно стабільним він має бути уточненим, наприклад за допомого алгоритму Руперта (Ruppert's algorithm^[en]). Це було реалізовано Джонатаном Шевчуком, і вільно доступно в пакеті Triangle [Архівовано 10 квітня 2011 у Wayback Machine.].

Див. також

• Геометричний кістяк
• Граф відносних околів
• Граф Уркгарта
• Множина Делоне

Примітки

1. B. Delaunay: Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793-800, 1934
2. de Berg, Mark; Otfried Cheong, Marc van Kreveld, Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5. Архів оригіналу (PDF) за 28 жовтня 2009. Процитовано 17 квітня 2011. 
3. Seidel, R. (1995). The upper bound theorem for polytopes: an easy proof of its asymptotic version. Computational Geometry. 5: 115—116. ^[недоступне посилання з липня 2019]
4. Guibas, Lenoidas; Stolfi, Jorge (1 квітня 1985). Primitives for the manipulation of general subdivisions and the computation of Voronoi. ACM. с. 107. Процитовано 1 серпня 2009. 
5. Guibas, L.; D. Knuth; M. Sharir (1992). Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithmica. 7: 381—413. doi:10.1007/BF01758770. ^[недоступне посилання]
6. G. Leach: Improving Worst-Case Optimal Delaunay Triangulation Algorithms. [Архівовано 7 жовтня 2012 у Wayback Machine.] June 1992
7. Cignoni, P.; C. Montani; R. Scopigno (1998). DeWall: A fast divide and conquer Delaunay triangulation algorithm in E^d. Computer-Aided Design. 30 (5): 333—341. doi:10.1016/S0010-4485(97)00082-1. 
8. A Comparison of Sequential Delaunay Triangulation Algorithms http://www.cs.berkeley.edu/~jrs/meshpapers/SuDrysdale.pdf [Архівовано 8 березня 2012 у Wayback Machine.]
9. Архівована копія. Архів оригіналу за 10 жовтня 2017. Процитовано 17 квітня 2011. 
10. S-hull (PDF). Архів оригіналу (PDF) за 27 жовтня 2013. Процитовано 17 квітня 2011. 
11. www.s-hull.org. Архів оригіналу за 22 липня 2011. Процитовано 17 квітня 2011. 

Посилання

• Тріангуляція Делоне в Computational Geometry Algorithms Library:
  • Yvinec, Mariette. 2D Triangulation. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011. 
  • Pion, Sylvain; Teillaud, Monique. 3D Triangulations. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011. 
  • Hert, Susan; Seel, Michael. dD Convex Hulls and Delaunay Triangulations. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011. 
• Delaunay triangulation. Wolfram MathWorld. Архів оригіналу за 2 січня 2021. Процитовано 14 квітня 2011. 
• Qhull. Архів оригіналу за 26 червня 2013. Процитовано 9 травня 2019.  — Код для побудови опуклої оболонки, тріангуляції Делоне, діаграми Вороного та перетину півпросторів
• Shewchuk, Jonathan Richard. Triangle. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011.  — Генератор двовимірного мешу, та тріангулятор Делоне
• Kumar, Piyush; Mohanty, Somya. Triangle++. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011.  — Triangle пристосований до C++
• Poly2Tri. Google Code. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011.  — Бібліотека тріангуляцій Делоне методом замітання, доступна на ActionScript 3, C++, C#, Java, Javascript, Python та Ruby.