Тріангуляція ділова побудова рівностороннього трикутників. Розробка та реалізація алгоритмів тривимірної тріангуляції складних просторів.
(Розробка та здійснення algorithms для обмежених volume triangulations: Iterative algorithms
Preprint, Inst. Appl. Math., Russian Academy of Science)
Галанін М.П., Щеглов І.А.
(M.P.Galanin, I.A.Sheglov)
ІПМ ім. М.В.Келдиша РАН
Москва, 2006
Роботу виконано за фінансової підтримки Російського фонду фундаментальних досліджень (проект № 06-01-00421)
Анотація
Розглянуто ітераційні методи тривимірної дискретизації просторових областей (побудови тетраедричних сіток): методи граничної корекції, методи на основі критерію Делоне та методи вичерпування. Наведено варіанти алгоритмів для кожного із зазначених методів. Обговорено особливості побудови сіток у складних сферах.
Abstract
Три основні сімейства ітеративних algoritms для вільного і поділеного високим обсягом тріангульації є описані: boundary correction (including "octree" algorithm), Delaunay-базовані методи і розширення front approach. Для кожного методу типу an example algorithm is given.
1. Вступ 3
2. Методи граничної корекції4
2.1 Побудова первинної сітки4
2.2 Корекція первинної сітки6
3. Методи на основі критерію Делоне9
3.1 Побудова тріангуляції Делоне на заданому наборі точок 12
3.2. Тріангуляція Делоне з обмеженнями17
3.3 Особливості технічної реалізації алгоритмів з урахуванням
критерію Делоне
22
4. Методи вичерпування23
4.1 Приклад алгоритму вичерпування26
Список литературы3 0
Серед двох класів методів тріангуляції - прямих та ітераційних - останні мають достатню універсальність і тому, на відміну від прямих, можуть бути використані для тріангуляції областей досить довільного вигляду. За цю універсальність доводиться розплачуватися значно більшим споживанням ресурсів і більш трудомісткою реалізацією методу у конкретному алгоритмі.
В даний час розроблено велику кількість програмних пакетів на основі того чи іншого ітераційного методу, що реалізують побудову сіток (частково або повністю) в автоматичному режимі. В основному ці пакети комерційні, що цілком виправдано з урахуванням витрачених на їх створення зусиль, адже тривимірний простір має низку неприємних особливостей, які суттєво ускладнюють життя розробнику.
Сітки, побудовані ітераційними методами, як правило, неструктуровані та неоднорідні. Неструктурованість обумовлена тим, що топологія сітки формується у процесі побудови, і тому природно може змінюватись навіть у межах однієї підобласті. З цієї причини однорідність якщо й може виникнути, лише випадково.
Оскільки перед побудовою сітки нічого не можна сказати про її майбутню структуру, не можна гарантувати її якості. Часто побудовану сітку можна суттєво покращити за допомогою одного із численних методів оптимізації. Цією можливістю зазвичай не нехтують, благо що час, що витрачається на оптимізацію, як правило, значно менше часу, що витрачається на побудову.
Метою даної є розгляд і класифікація існуючих методів побудови тетраедричних сіток в тривимірних областях. Через значний обсяг інформації нижче розглядаються лише звані " ітераційні методи " . Прямі методи описані у .
Робота виконана за часткової фінансової підтримки Російського фонду фундаментальних досліджень (проект №06-01-00421).
Рис. 11. Тріангуляція області, що є об'єднанням додекаедра та ікосаедра (тріангуляція Делоне з обмеженнями)
Якість сіток, побудованих даним методом, знаходиться на середньому рівні (тетраедри біля кордонів можуть мати дуже погану форму), тому зазвичай додатково вдаються до одного з методів оптимізації.
У роботах Б. Джо запропоновані інші варіанти алгоритму, що не використовують додаткові точки і повністю засновані на локальних трансформаціях, аналогічних "трейду".
4) обсяг тетраедра не більший за максимально допустимий ().
З усіх тетраедрів () вибирається тетраедр найкращої якості та здійснюється перехід до п. 5; якщо ж тетраедрів, що задовольняють зазначеним умовам, не виявилося, здійснюється перехід до п. 4.
4. Знаходиться така точка всередині ще невичерпаної області, що:
1) тетраедр () задовольняє всі умови п. 3;
2) у кулі немає жодної віддаленої точкиF(це запобігає розміщенню вузлаp надто близько від граней і вершин існуючих тетраедрів).
Варіант алгоритму пошуку вузлаpрозглянуто нижче.
5. Видаляються всі вершиниF, що потрапили всередину (і на межі) сформованого тетраедра Потім фронт оновлюється за такою схемою: розглядається кожна грань сформованого тетраедра та
1) якщо грань є гранню фронту, вона видаляється з фронту;
2) якщо грань НЕ є межею фронту, вона додається у фронт.
6. Якщо ще залишилися невіддалені точкиFабо (що еквівалентно) фронт не порожній (тобто область ще не вичерпана повністю), здійснюється перехід до п. 1, інакше процес закінчено.
Таким чином, масивFвикористовується відразу для кількох цілей: для оцінки величини тілесного кута, для контролю правильності побудови та контролю розміщення нових вузлів. Також масивFзручно використовуватиме індикації процесу виконання. Відношення числа віддалених під час роботи алгоритму точокFдо початкового числа існуючих точокFФактично показує, яка частина області вже вичерпана.
Повернемося до питання знаходження координат нового вузла для побудови тетраедра (п. 4 описаного алгоритму). Нехай задані три вузли - .
1. На першому кроці знаходяться центр мас трикутника (як середнє арифметичне координат його вузлів) і одинична нормаль до площини грані (через нормований векторний твір).
2. Далі визначається перше наближення для відстані до шуканої точкиp (H), з максимального обсягу тетраедра: . Зауважимо, що площа граніSфактично знайдено на попередньому кроці (результат векторного твору двох ребер дорівнює подвоєної площі грані), а максимальний обсяг обумовлений значенням контрольної функції.
3. Перевіряється точка. Якщо тетраедр () відповідає всім вимогам, відбувається перехід до п. 6, інакше - до п. 4.
4. Перевіряється точка. Якщо тетраедр () відповідає всім вимогам, відбувається перехід до п. 6, інакше - до п. 5.
5. Вважають та переходять до п. 3.
6. Шуканий вузол знайдено.
Зауважимо, що у 99% випадків шукана точка перебуває в 1 чи 2 ітерації даного алгоритму.
В описаному вище алгоритмі вичерпування на кожному кроці з дільниці вилучається один тетраедр. Співробітник НАСА Ш. Пірзаде ( Shahyar Pirzadeh ) Запропонував інший варіант алгоритму, в якому за один раз з області вилучається відразу цілий шар тетраедрів (тобто на кожній ітерації тетраедри будуються відразу для всіх граней поточного фронту). Всупереч очікуванню, цей варіант не дозволяє скільки-небудь суттєво прискорити процес побудови (бо все нові тетраедри все одно необхідно перевіряти на коректність), проте він позбавляє необхідності шукати найбільш підходящу для побудови тетраедра грань. Це, проте, швидше за мінус, ніж плюс, так як через цю особливість варіант Пірзаде менш надійний і може дати збій на геометрично складних областях. Разом з тим, на порівняно простих областях він показує непогані результати.
Сітки, побудовані методами вичерпування, як правило, мають непогану якість, а подальша оптимізація положення вузлів дає додатковий додаток до якості. Підсумовуючи, зауважимо, що методи вичерпування найефективніші, якщо спочатку задана тріангуляція межі області. У цьому полягає їх основна відмінність від методів з урахуванням критерію Делоне, котрим ситуація прямо зворотна.
Список літератури
1. Шайдур В.В. Багатосіточні методи кінцевих елементів. – М., Наука, 1989. – 288с.
2. Скворцов О.В. Огляд алгоритмів побудови тріангуляції Делоне // , 2002, №3, c. 14-39.
3. Скворцов О.В. Алгоритми побудови тріангуляції з обмеженнями // Обчислювальні методи та програмування, 2002, №3, c. 82-92.
4. I.Babushka, W.C. Rheinboldt. A-posteriori Error Estimates for Finite Element Method // Int. J. Numer. Meth. Eng., Vol. 12, pp. 1597-1615, 1978.
5. T.J. Baker. Automatic Mesh Generation for Complex Three-Dimensional Regions Using a Constrained Delaunay Triangulation // Engineering With Computers, Springer-Verlag, № 5, pp. 161-175, 1989.
6. M. Bern, D. Eppstein. Mesh Generation and Optimal Triangulation // Computing in Euclidean Geometry, World Scientific Publishing Co., pp. 23-90, 1995.
7. D.K. Blandford, G. Belloch, D. Cardoze, C. Kadow. Compact Representations of Simplicial Meshes In Two and Three Dimensions // Proceedings of 12th International Meshing Roundtable, Sandia National Laboratories, pp.135-146, Sept. 2003.
8. H. Borouchaki, S.H. Lo. Fast Delaunay Triangulation In Three Dimensions // Computer Methods In Applied Mechanics And Engineering, Elsevier, Vol. 128, pp. 153-167, 1995.
9. E.K. Buratynski. A Three-Dimensional Unstructured Mesh Generator for Arbitrary Internal Boundaries // Numerical Grid Generation in Computational Fluid Mechanics, Pineridge Press, pp. 621-631, 1988.
10. P.R. Cavalcanti, UT. Mello. Три-Dimensional Constrained Delaunay Triangulation: A Minimalist Approach // Proceedings of the 8th International Meshing Roundtable, p.p. 119-129, 1999.
11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Delaunay Triangulations In Three Dimensions With Finite Precision Arithmetic // Computer Aided Geometric Design, North-Holland, № 9, pp. 457-470, 1992.
12. H.N. Джидєв. Force-Directed Methods For Smoothing Unstructured Triangular And Tetrahedral Meshes // Proceedings of 9th International Meshing Roundtable, Sandia National Laboratories, pp. 395-406, жовтень 2000.
13. L. Durbeck. Evaporation: A Technique For Visualizing Mesh Quality // Proceedings of 8th International Meshing Roundtable, South Lake Tahoe, CA, U.S.A., pp. 259-265, жовтень 1999.
14. D.A. Field. Laplacian Smoothing And Delaunay Triangulations // , Vol. 4, pp. 709-712, 1988.
15. PJ. Frey, H. Borouchaki, P.-L. Джордж. Delaunay Tetrahedralization Using an Advancing-Front Approach // Proceedings of 5th International Meshing Roundtable, Sandia National Laboratories, pp. 31-46, жовтень 1996.
16. L.A. Freitag, C. Ollivier-Gooch. A Comparison of Tetrahedral Mesh Improvement Techniques // Proceedings of 5th International Meshing Roundtable, Sandia National Laboratories, pp. 87-106, жовтень 1996.
17. L.A. Freitag, C. Ollivier-Gooch. , Vol. 40, pp. 3979-4002, 1995.
18. L.A. Freitag, C. Ollivier-Gooch. The Effect Of Mesh Quality On Solution Efficiency // Proceedings of 6th International Meshing Roundtable, Sandia National Laboratories, p.p.249, October 1997.
19. P.L. Джордж. TET MESHING: Construction, Optimization and Adaptation // Proceedings of 8thInternational Meshing Roundtable, p.p.133-141, 1999.
20. N.A. Golias, T.D. Tsiboukis. An Approach to Refining Three-Dimensional Tetrahedral Meshes Based on Delaunay Transformations // , John Wiley, № 37, pp.793-812, 1994.
21. C. Hazlewood. Approximating Constrained Tetrahedralizations // Computer Aided Geometric Design, Vol. 10, pp. 67-87, 1993.
22. B. Joe. Delaunay Triangular Meshes в Convex polygons, SIAM J. Sci. Stat. Comput., Vol. 7, pp. 514-539, 1986.
23. B. Joe. Construction Of Three-Dimensional Delaunay Triangulations Using Local Transformations // Computer Aided Geometric Design, Vol. 8, pp. 123-142, 1991.
24. B. Joe. Construction of Three-Dimensional Improved-Quality Triangulations Using Local Transformations // Siam J. Sci. Comput., Vol. 16, pp. 1292-1307, 1995.
25. R.W. Lewis, Yao Zheng, D.T. Gethin. Three-Dimensional Unstructured Mesh Generation: Part 3. Volume Meshes // Computer Methods In Applied Mechanics And Engineering, Elsevier, Vol 134, pp.285-310, 1996.
26. A. Liu, B. Joe. On The Shape Of Tetrahedra From Bisection // Mathematics of Computation, Vol. 63, №207, 141-154, 1994.
27. S.H. Lo. Volume Discretization в Tetrahedra-I. Verification and Orientation of Boundary Surfaces // Комп'ютери та структури, Pergamon Press, Vol. 39, № 5, pp. 493-500, 1991.
28. S.H. Lo. Volume Discretization in Tetrahedra - II. 3D Triangulation by Advancing Front Approach // Комп'ютери та структури, Pergamon, Vol. 39, № 5, pp. 501-511, 1991.
29. R. Lohner. Generation Of Three-Dimensional Unstructured Grids By The Advancing Front Method // Proceedings of the 26th AIAA Aerospace Sciences Meeting, Reno, Nevada, 1988.
30. S.J. Owen. A Survey of Unstructured Mesh Generation Technology // Proceedings of 7th International Meshing Roundtable, p.p. 239-269, Dearborn, МІ, 1998.
31. V.N. Parthasarathy, C.M. Graichen, A.F. Hathaway. A Comparison of Tetrahedron Quality Measures // Finite Elements in Analysis and Design, Elsevier, №. 15, pp. 255-261, 1993.
32. S. Pirzadeh. Unstructured Viscous Grid Generation by Advancing-Layers Method // AIAA-93-3453-CP, AIAA, pp. 420-434, 1993.
33. V.T. Rajan. Optimality of Delaunay Triangulation in // Proc. 7th ACM Symp. Comp. Geometry, p.p. 357-363, 1991.
34. A.Rassineux. Generation and Optimization of Tetrahedral Meshes by Advancing Front Technique // International Journal for Numerical Methods in Engineering, Wiley, Vol. 41, pp. 651-674, 1998.
35. S. Rebay. Ефективний неструктурований мішень генерації засобами з Delaunay Triangulation and Bowyer-Watson Algorithm // Journal Of Computational Physics, Vol. 106, pp. 125-138, 1993.
36. M-C. Rivara. Selective Refinement/Derefinement Algorithms For Sequences Of Nested Triangulations // International Journal for Numerical Methods in Engineering, №28, pp. 2889-2906, 1998.
37. M-C. Rivara, C. Levin. A 3D Refinement Algorithm Suitable For Adaptive And Multigrid Techniques // Communications in Applied Numerical Methods, № 8, pp. 281-290, 1998.
38. J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation // Journal of Algorithms, №18, pp. 548-585, 1995.
39. M.S. Shephard, M.K. Georges. Three-Dimensional Mesh Generation by Finite Octree Technique // International Journal for Numerical Methods in Engineering, Vol. 32, pp. 709-749, 1991.
40. M.S. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Baehmann. Finite octree mesh generation for automated adaptive 3D Flow Analysis // Numerical grid generation in computational Fluid mechanics, Miami, 1988
41. K. Shimada, D.C. Gossard. Bubble Mesh: Automated Triangular Meshing of Non-manifold Geometry by Sphere Packing // Proceedings of 3rd Symposium on Solid Modeling and Applications , p.p. 409-419, 1995.
42. K. Shimada, A. Yamada, T. Itoh. Anisotropic Triangular Meshing of Parametric Surfaces via Close Packing of Ellipsoidal Bubbles // Proceedings of 6th International Meshing Roundtable, p.p. 375-390, 1997.
43. D.F. Watson. Computing the Delaunay Tessellation with Application до Voronoi Polytopes // The Computer Journal, Vol. 24(2), pp. 167-172, 1981.
44. M.A. Yerry, M.S. Shephard. Three-Dimensional Mesh Generation by Modified Octree Technique // International Journal for Numerical Methods in Engineering, Vol. 20, pp. 1965-1990, 1984.
45. Галанін М.П., Щеглов І.А. Розробка та реалізація алгоритмів тривимірної тріангуляції складних просторових областей: прямі методи. Препрінт ІПМ ім. М.В. Келдиша РАН, 2006, у пресі. points, тобто. вузли Штейнера - додаткові вузли, що не входили до початкового набору
Може здатися, що з умови 3 випливає умова 2, але насправді це не так. Наприклад, існуючий тетраедр може виявитися цілком всерединіТетраедра, що перевіряється.
Структура лекції Визначення Визначення Області застосування Області застосування Властивості тріангуляції Делоне Властивості тріангуляції Делоне Методи побудови тріангуляції Делоне Методи побудови тріангуляції Делоне Методи покрокового введення Методи покрокового введення Методи покрокової вибірки
Тріангуляція Тріангуляція – планарний граф, всі внутрішні області якого є трикутниками. Тріангуляція – планарний граф, всі внутрішні області якого є трикутниками. Термін «Тріангуляція» – це Термін «Тріангуляція» – це граф; граф; процес побудови графа. процес побудови графа. Завдання тріангуляції набору точок 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 Скворцов рекомендує: ітеративний алгоритм з динамічним кешуванням
А сьогодні про що? Про тріангуляцію Делон! Визначення Визначення Області застосування Області застосування Властивості тріангуляції Делоне Властивості тріангуляції Делоне Методи побудови тріангуляції Делоне Методи побудови тріангуляції Делоне Методи покрокового введення Методи покрокового введення Методи покрокової вибірки Методи покрокової вибірки Методи декомпозиції
Тріангуляція для кінцевого набору точок S є завданням тріангуляції опуклої оболонки CH(S), що охоплює всі точки набору S. Відрізки прямих ліній при тріангуляції не можуть перетинатися - вони можуть тільки зустрічатися в загальних точках, що належать набору S. Оскільки відрізки прямих ліній замикають трикутники ми вважатимемо їх ребрами. На рис. 1 показані два різні варіанти тріангуляції для одного і того ж набору точок (тимчасово проігноруємо кола, проведені на цих малюнках).
Рис. 1
Для даного набору точок S ми можемо бачити, що всі точки з набору S можуть бути поділені на граничні точки - ті точки, які лежать на межі опуклої оболонки CH(S), і внутрішні точки, що лежать усередині опуклої оболонки CH(S). Також можна класифікувати і ребра, отримані в результаті тріангуляції S, як ребра оболонкиі внутрішні ребра. До ребрів оболонки відносяться ребра, розташовані вздовж межі опуклої оболонки CH(S), а до внутрішніх ребрів - всі інші ребра, що утворюють мережу трикутників усередині опуклої оболонки. Зазначимо, що кожне ребро оболонки з'єднує дві сусідні граничні точки, тоді як внутрішні ребра можуть з'єднувати дві точки будь-якого типу. Зокрема, якщо внутрішнє ребро з'єднує дві граничні точки, воно є хордою опуклої оболонки CH(S). Зауважимо також, що кожне ребро тріангуляції є межею двох областей: кожне внутрішнє ребро знаходиться між двома трикутниками, а кожне ребро оболонки між трикутником і нескінченною площиною.
Будь-який набір точок, за винятком деяких тривіальних випадків, допускає більше одного способу тріангуляції. Але при цьому існує чудова властивість: будь-який спосіб тріангуляції для даного набору визначає однакову кількість трикутників, що випливає з теореми:
Теорема про тріангуляцію набору точок.Припустимо, що набір точок S містить n>3 точок і не всі їх колінеарні. Крім того, i точок з них є внутрішніми (тобто лежать усередині опуклої оболонки CH(S). Тоді за будь-якого способу тріангуляції набору S буде отримано точно n + i - 2 трикутників.
Для підтвердження теореми розглянемо спочатку тріангуляцію n-i граничних точок. Оскільки всі вони є вершинами опуклого полігону, то за такої тріангуляції буде отримано (n - i) - 2 трикутники. (У цьому неважко впевнитись і, більше того, можна показати, що будь-яка тріангуляція довільного m-стороннього полігону - опуклого або непуклого - містить m - 2 трикутники). Тепер перевіримо, що відбуватиметься з тріангуляцією при додаванні решти i внутрішніх точок, щоразу по одній. Ми стверджуємо, що додавання кожної такої точки призводить до збільшення числа трикутників на два. При додаванні внутрішньої точки можуть бути дві ситуації, показані на рис. 2. По-перше, точка може бути всередині деякого трикутника і тоді такий трикутник замінюється трьома новими трикутниками. По-друге, якщо точка збігається з одним з ребер тріангуляції, то кожен із двох трикутників, що примикають до цього ребра, замінюється двома новими трикутниками. З цього випливає, що після додавання всіх точок, загальна кількість трикутників складе (n - i - 2) + (2i), або просто n + i - 2.
Рис. 2
У цьому розділі ми представимо алгоритм формування спеціального виду тріангуляції відомий як тріангуляція Делоне. Ця тріангуляція добре збалансована в тому сенсі, що трикутники, що формуються, прагнуть рівнокутності. Так, наприклад, тріангуляцію, зображену на рис. 1а можна віднести до типу тріангуляції Делоне, а на рис. 1б тріангуляція містить кілька сильно витягнутих трикутників і її не можна зарахувати до типу Делоне. На рис. 3 показаний приклад тріангуляції Делоне для набору великої кількості точок.
Рис. 3
Для формування тріангуляції Делоне нам знадобиться кілька нових визначень. Набір точок вважається круговим, якщо існує деяке коло, на якому лежать усі точки набору. Таке коло буде описаним для даного набору точок. Описане коло для трикутника проходить через усі три її (не колінеарні) вершини. Кажуть, що коло буде вільним від точок у відношенні до заданого набору гочек S, якщо всередині кола немає жодної точки з набору S. Але, однак, точки з набору S можуть розташовуватися на вільній від точок кола.
Тріангуляція набору точок S буде тріангуляцією Делоне, якщо описане коло для кожного трикутника буде вільним від точок. На схемі тріангуляції рис. 1а показані два кола, які явно не містять в собі інших точок (можна провести кола і для інших трикутників, щоб переконатися, що вони також вільні від точок набору). Це правило не дотримується схеми рис. 16 - всередину проведеного кола потрапила одна точка іншого трикутника, отже, ця гріангуляція не відноситься до типу Делоне.
Можна зробити два припущення щодо точок у наборі S, щоб спростити алгоритм тріангуляції. По-перше, щоб взагалі існувала тріангуляція, ми повинні вважати, що набір S містить принаймні три точки і вони не є колінеарними. По-друге, для унікальності тріангуляції Делоне необхідно, щоб жодні чотири точки з набору S не лежали на одному описаному колі. Легко бачити, що без такого припущення гріангуляція Делоне не буде унікальною, бо 4 точки на одному описаному колі дозволяють реалізувати дві різні тріангуляції Делоне.
Наш алгоритм працює шляхом постійного нарощування поточної тріангуляції по одному трикутнику за один крок. Спочатку поточна тріангуляція складається з єдиного ребра оболонки, після роботи алгоритму поточна тріангуляція стає тріангуляцією Делоне. На кожній ітерації алгоритм шукає новий трикутник, який підключається до кордоніпоточної тріангуляції.
Визначення межі залежить від наступної схеми класифікації ребер тріангуляції Делоне щодо поточної тріангуляції. Кожне ребро може бути сплячим, живимабо мертвим:
- сплячі ребра: ребро тріангуляції Делоне є сплячим, якщо вона ще не була виявлена алгоритмом;
- живі ребра: ребро живе, якщо воно виявлено, але відома тільки одна область, що примикає до нього;
- мертві ребра: ребро вважається мертвим, якщо воно виявлено і відомі обидві області, що примикають до нього.
Спочатку живим є єдине ребро, що належить опуклій i лочці – до нього примикає необмежена площина, а решта всіх ребрів спить. У міру роботи алгоритму ребра зі сплячих стають живими, потім мертвими. Кордон кожному етапі складається з набору живих ребер.
На кожній ітерації вибирається будь-яке одне з ребері кордону і воно піддається обробці, що полягає в пошуку невідомої області, якій належить ребро е. Якщо ця область виявиться трикутником f, що визначається кінцевими точками ребра і деякою третьою вершин v, то ребро стає мертвим , оскільки тепер відомі обидві області, що примикають до нього. Кожне з двох інших ребер трикутника t переводяться в такий стан: зі сплячого в живе або живого в мертве. Тут вершина v називатиметься пов'язаноїз ребром е. інакше, якщо невідома область виявляється нескінченною площиною, то ребро е просто вмирає. У цьому випадку ребро не має сполученої вершини.
На рис. 4 показано роботу алгоритму, де дія відбувається зверху вниз і слава праворуч. Кордон на кожному етапі виділено товстою лінією.
Алгоритм реалізований у програмі delaunayTriangulate. Програмі задається масив s з n точок і вона повертає список трикутників, що становлять тріангуляцію Делоне. Реалізація використовує клас кільцевого списку та класи з розділу структури геометричних даних. Як клас Dictionary можна використовувати будь-який словник, що підтримує необхідні операції. Наприклад, можна перевизначити #define Dictionary RandomizedSearchTree .
List
Рис. 4
Трикутники, що утворюють тріангуляцію, записуються до списку triangles. Кордон представлений словником frontier живих ребер. Кожне ребро спрямоване, отже невідома область йому (підлягає визначенню) лежить праворуч від ребра. Функція порівняння edgeCmp використовується для перегляду словника. У ній порівнюються початкові точки двох ребер, якщо вони виявляються рівними, потім порівнюються їх кінцеві точки:
Int edgeCmp (Edge *a, Edge *b) ( if (a->org< b->org) return 1; if (a->org > b->org) return 1; if (a->dest< b->dest) return -1; if (a->dest > b->dest) return 1; return 0; )
Як змінюється кордон від одного кроку до іншого і як функція updateFrontier змінює словник ребер кордону для відображення цих змін? При підключенні до межі нового трикутника t змінюються стани трьох ребер трикутника. Ребро трикутника t, яке примикає до кордону, з живого стає мертвим. Функція updateFrontier може ігнорувати це ребро, оскільки воно вже має бути видалено зі словника при зверненні до функції removeMin. Кожне з двох ребер трикутника t, що залишилися, змінюють свій стан зі сплячого на живе, якщо вони вже раніше не були записані в словник, або з живого в мертве, якщо ребро вже знаходиться в словнику. На рис. 5 показані обидва випадки. Відповідно до малюнка ми обробляємо живе ребро af і, після виявлення, що точка b є сполученою йому, додаємо трикутник afb до поточної тріангуляції. Потім шукаємо ребро fb у словнику і оскільки його там ще немає і воно виявлено вперше, його стан змінюється від сплячого до живого. Для редагування словника ми повернемо ребро fb так, щоб невідома область, що примикає до нього, лежала праворуч від нього і запишемо це ребро в словник. Потім знайдемо в словнику ребро ba - оскільки воно є в ньому, воно вже живе (відома область, що примикає до нього, - трикутник abc). Так як невідома для нього область, трикутник afb, щойно була виявлена, це ребро видаляється зі словника.
Функція updateFrontier редагує словник frontier, у якому змінюється стан ребра з точки а до точки b:
Рис. 5
Void updateFrontier (Dictionary
Функція hullEdge виявляє ребро оболонки серед пунктів масиву s. У цій функції фактично застосовується етап ініціалізації та першої ітерації методу загортання подарунка:
Edge *hullEdge (Point s, int n) ( int m = 0; for (int i = 1; i< n; i++) if (s[i] < s[m]) m = i; swap(s, s[m]); for (m = 1, i = 2; i < n; i++) { int с = s[i].classify (s, s[m]); if ((c == LEFT) || (C == BETWEEN)) m = i; } return new Edge(s, s[m]); }
Функція triangle просто формує і повертає полігон для трьох точок, що передаються їй як параметри:
Polygon *triangle (Point &а, Point &b, Point &c) ( Polygon *t = новий Polygon; t->insert (a); t->insert (b); t->insert (c); return t; )
GRID-моделі – моделі регулярних осередків.
Нехай введено систему координат 
і 
і 
. Користувач задає 
та кроки дискретизації 
.
,
- Фізичні координати точки.
Обчислюємо 
і 
,
- Розрядна сітка.
- квантовані значення. Реальні:
- Параметр алгоритму - кількість точок, 
- Вага. Чим ближче точка, тим більша вага.
- Ступінь відстані (1 або 2).
Нормувальний коефіцієнт: 
Чим 
ближче до 1, тим більше обліковуються точки з великою вагою.
Це метод IDW - довгий, для кожної т. необхідно знайти сусідів. Набір сусідів може бути знайдено - найближчим. Кожна з точок продукує «кілочок» певної висоти. Від нерегулярності постановок точки багато залежить, для цього беруть 
або 
тобто. поділяють на сектори та в околиці точки будуємо.
Перевага- Простота
Недолік:
------Квиток 14. Tin-модель. Алгоритми тріангуляції Делоне------
1) Тріангуляційні (tin).
Тріангуляція- Побудова функції у вигляді сукупності шматково - лінійної функції
Тріангуляція- інтерполяція усередині опуклої області.
Тріангуляція– планарний граф, усі внутрішні ребра якого – трикутники; спосіб представлення простору у вигляді трикутників, що примикають один до одного, без перекриттів. На наборі точок тріангуляція будується кількома способами.
Потрібен алгоритм для побудови оптимальної тріангуляції.
Площина, що проходить через три точки.
1) Знайдемо трикутник, який 
;
2)
- Будуємо рівняння площини.
Щоб перевірити чи знаходяться точки всередині трикутника чи ні, необхідно підставити значення рівняння ліній – ребер трикутника. Якщо всі 3 рівняння > 0, то усередині.
Структура подання:
Кожна тріангуляція містить однакову кількість трикутників.
, де 
- Кількість внутрішніх точок, 
- Кількість точок.
Жадібний тріангуляція.
Усі точки з'єднуємо ребрами, вибираємо мінімум, додаємо в тріангуляцію. Далі беремо наступний мінімум, що не перетинається з попередніми тощо. В результаті отримано жадібну тріангуляцію.
Тріангуляція Делоне.
Всередину кола, описаного навколо будь-якого трикутника, не потрапляють точки інших трикутників. Будується єдиним чином.
Фліпом називається перекидання ребер. Вона дозволяє перейти від звичайної тріангуляції до тріангуляції Делоне. Щоб перевірити належність точки до кола: підставити, якщо< R, то внутри.
Умова Делоне.
Рівняння кола, що проходить через три точки:
Якщо менше нуля, то зовнішня, інакше – внутрішня.
-Умова Делоне.
Алгоритм побудови тріангуляції Делоне:
1) Підслідного додавання точок- Простий ітеративний алгоритм:
Є набір 
додаємо в трикутник, здійснюється побудова 
розбиття трикутника 
перебудова. На нульовому етапі додаємо 3-4 фіктивні точки, які свідомо покривають наш конверт, усі крапки всередині. Потім кидаємо крапку, дивимося в який трикутник потрапила, розбиваємо на 3, для кожного трикутника перевіряємо умову Делоне і здійснюємо фліп перекидання ребер. Середня кількість перебудов дорівнює трьом.
Теоретична складність 
2) Методи прискорення.Заснований на статистично залежних точках. Затравний трикутник – трикутник, у який потрапила попередня точка. Потім з'єднуємо дві точки – попередню та нову.
Переміщуємося з першої точки в іншу.
Загалом, усі алгоритми мають у своїй основі дуже просту ідею послідовного додавання точок у частково побудовану тріангуляцію Делоне. Формально це так.
Дано безліч N точок.
1. На перших трьох вихідних точках будуємо трикутник.
2. У циклі по n для всіх інших точок виконуємо кроки 3-5.
3. Чергова n-а точка додається до вже побудованої структури тріангуляції наступним чином. Спочатку виробляється локалізація точки, тобто. знаходиться трикутник (побудований раніше), до якого потрапляє чергова точка. Або якщо крапка не потрапляє всередину тріангуляції, знаходиться трикутник на межі тріангуляції, найближчий до чергової точки.
4. Якщо точка потрапила на раніше вставлений вузол тріангуляції, така точка зазвичай відкидається, інакше точка вставляється в тріангуляцію у вигляді нового вузла. При цьому якщо точка потрапила на деяке ребро, воно розбивається на два нових, а обидва суміжні з ребром трикутника також діляться на два менших. Якщо точка потрапила строго всередину якогось трикутника, він розбивається на три нових. Якщо точка потрапила поза тріангуляцією, то будується один чи більше трикутників.
5. Проводяться локальні перевірки новостворених трикутників на відповідність умові Делоне та виконуються необхідні перебудови.
Кінець алгоритму.
Нижче наводиться докладний опис кількох алгоритмів.
Жадібний алгоритм
Одним із перших було запропоновано наступний алгоритм побудови тріангуляції.
Жадібний метод- це такий метод, за якого ніколи не скасовується те, що вже було зроблено раніше. У алгоритмі послідовно виконуються такі кроки.
1. До множини вихідних точок поміщаються кінці всіх структурних відрізків.
2. Генеруються відрізки, що з'єднують усі пари точок, сортуються відрізки по довжині.
3. У тріангуляцію вставляють усі відрізки структурних ліній.
4. У тріангуляцію послідовно відбираються відрізки з безлічі відсортованих по довжині відрізків (від коротких до довших). Якщо відрізок перетинається з якимось із уже вставлених, він відкидається, інакше вставляється в тріангуляцію.
Крок 4 повторюється, доки не закінчаться відрізки.
Зауважимо, якщо всі можливі відрізки мають різну довжину, то результат роботи цього алгоритму однозначний, інакше він залежить від порядку вставки відрізків однакової довжини.
Тріангуляція називається жадібною, якщо вона побудована жадібним алгоритмом.
Алгоритм "Видаляй та будуй"
"Видаляй і буд" не виконується жодних перебудов. Натомість при кожній вставці нового вузла (а) відразу ж видаляються всі трикутники, у яких всередину описаних кіл потрапляє новий вузол (б). При цьому всі віддалені трикутники явно утворюють деякий багатокутник. Після цього на місці віддалених трикутників будується тріангуляція, що заповнює, шляхом з'єднання нового вузла з цим багатокутником (рис. в).
Рис. 4. Алгоритм "Видаляй і буд"
Даний алгоритм будує відразу всі необхідні трикутники на відміну від звичайного ітеративного алгоритму, де при вставці одного вузла можливі багаторазові перебудови одного й того трикутника. Проте тут першому плані виходить процедура виділення контуру віддаленого багатокутника, від ефективності роботи якого залежить загальна швидкість алгоритму. Загалом залежно від структури даних, що використовується, цей алгоритм може витрачати часу менше, ніж алгоритм з перебудовами, і навпаки.
Алгоритм "Буд, розбиваючи"
Алгоритм вставки структурних відрізків "Буд, розбиваючи" є найпростішим у реалізації та стійким у роботі.
У ньому необхідно, послідовно переходячи по трикутниках вздовж відрізка, що вставляється, знаходити точки його перетину з ребрами тріангуляції. У цих точках перетину потрібно поставити нові вузли тріангуляції, розбивши існуючі ребра і трикутники на частини. Після цього все новозбудовані трикутники повинні бути перевірені виконання умови Делоне і за необхідності перебудовані, не торкаючись фіксованих ребер.
Рис. 5. Алгоритм "Буд, розбиваючи"
У деяких випадках недоліком даного алгоритму вставки може бути створення великої кількості додаткових вузлів та ребер тріангуляції. В той же час в інших випадках цей недолік стає перевагою, не дозволяючи утворюватися вузьким довгим трикутникам, що особливо цінується при моделюванні рельєфу.
Інша перевага цього алгоритму вставки в порівнянні з наступними проявляється при спробі вставки структурного відрізка в тріангуляцію, в якій серед ребер, що перетинаються ним, є фіксовані. Такі ребра, як і решта, просто розбиваються на дві частини.
Алгоритм з індексуванням центрів трикутників k-D – деревом
В алгоритмі тріангуляції з індексування центрів трикутників k-D-деревом в k-D-дерево (при k = 2) поміщаються тільки центри трикутників. При видаленні старих трикутників необхідно видаляти центри з k-D-дерева, а при побудові нових - заносити.
Для пошуку трикутника, в який потрапляє поточна точка, що вставляється в тріангуляцію, необхідно виконати нестандартний точковий запит до k-D-дерева. Пошук у дереві необхідно починати з кореня та спускатися вниз до листя. Якщо нащадки поточного вузла k-D-дерева (що охоплює нащадки прямокутник) не покривають поточну точку, необхідно вибрати для подальшого спуску по дереву нащадка, найближчого до точки пошуку.
В результаті буде знайдено деякий трикутник, центр якого буде близьким до заданої точки. Якщо знайдений трикутник не потрапляє задана точка, далі необхідно використовувати звичайний алгоритм пошуку трикутника з простого ітеративного алгоритму побудови тріангуляції Делоне.
