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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Тріангуляція Делоне і описані навколо трикутників кола

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

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

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

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

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

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

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

d-вимірні тріангуляції[ред.ред. код]

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

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

Властивості[ред.ред. код]

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

  • Об'єднання всіх симплексів в тріангуляції - опукла оболонка точок.
  • Тріангуляція Делоне містить щонайбільше O(nd / 2⌉) симплексів.[3]
  • Якщо на площині (d = 2), b вершин входять до опуклої оболонки, то будь-яка тріангуляція точок має щонайбільше 2n - 2 - b трикутників, і ще одну зовнішню "грань" (див. характеристика Ейлера).
  • На площині, кожна вершина має в середньому шість інцидентних трикутників.
  • На площині, тріангуляція Делоне максимізує найменший кут. Найменший кут в тріангуляції Делоне, буде не меншим ніж в будь-якій іншій тріангуляції. Правда тріангуляція Делоне не обов'язково мінімізує максимальний кут.
  • Коло описане навколо довільного трикутника тріангуляції не містить всередині жодних інших вхідних вершин.
  • Якщо коло що проходить через дві вхідні точки не містить всередині жодних інших, тоді сегмент що з'єднує ці дві точки є ребром тріангуляції Делоне цих точок.
  • Тріангуляція Делоне множини точок в d-вимірному просторі є проекцією точок опуклої оболонки на (d+1)-вимірнний параболоїд.
  • Найближчий сусід b довільної точки p лежить на ребрі bp тріангуляції Делоне, бо граф найближчих сусідів (en:nearest neighbor graph) - підграф тріангуляції Делоне.

Заміна спільного ребра[ред.ред. код]

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

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

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

Алгоритми[ред.ред. код]

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

\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(n2) замін ребер, і не узагальнюється на три виміри і більші.[2]

Інкрементний[ред.ред. код]

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

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

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

Розділяй і владарюй[ред.ред. код]

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

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

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

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

Замітання[ред.ред. код]

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

Замітаюча оболонка[ред.ред. код]

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

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

Застосування[ред.ред. код]

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

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


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

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

Зноски[ред.ред. код]

  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. Springer-Verlag. ISBN 978-3-540-77973-5. 
  3. Seidel, R. (1995). «The upper bound theorem for polytopes: an easy proof of its asymptotic version». Computational Geometry 5. с. 115–116. 
  4. Guibas, Lenoidas; Stolfi, Jorge (1985-04-01). «Primitives for the manipulation of general subdivisions and the computation of Voronoi». ACM. с. 107. Процитовано 2009-08-01. 
  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. June 1992
  7. Cignoni, P.; C. Montani; R. Scopigno (1998). «DeWall: A fast divide and conquer Delaunay triangulation algorithm in Ed». 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
  9. http://www.cs.cmu.edu/~quake/tripaper/triangle2.html
  10. S-hull
  11. www.s-hull.org

Посилання[ред.ред. код]