Триангуляция делоне построение равностороннего треугольников. Разработка и реализация алгоритмов трехмерной триангуляции сложных пространств.областей
(Development and Implementation of Algorithms for Constrained Volume Triangulations:
Iterative Algorithms
Preprint, Inst. Appl. Math., the Russian Academy of Science)
Галанин М.П., Щеглов И.А.
(M.P.Galanin, I.A.Sheglov)
ИПМ им. М.В.Келдыша РАН
Москва, 2006
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований
(проект № 06-01-00421)
Аннотация
Рассмотрены итерационные методы трехмерной дискретизации пространственных областей (построения тетраэдрических сеток): методы граничной коррекции, методы на основе критерия Делоне и методы исчерпывания. Приведены варианты алгоритмов для каждого из указанных методов. Обсуждены особенности построения сеток в сложных областях.
Abstract
Three main families of iterative algorithms for free and constrained simplicial volume triangulation are described: boundary correction (including "octree" algorithm), Delaunay-based methods and advancing front approach. For each method type 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, p.p. 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, p.p. 161-175, 1989.
6. M. Bern, D. Eppstein. Mesh Generation and Optimal Triangulation // Computing in Euclidean Geometry , World Scientific Publishing Co., p.p. 23-90, 1995.
7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Compact Representations of Simplicial Meshes In Two and Three Dimensions // Proceedings of 12th International Meshing Roundtable , Sandia National Laboratories, p.p.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, p.p. 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, p.p. 621-631, 1988.
10. P.R. Cavalcanti, U.T. Mello. Three-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, p.p. 457-470, 1992.
12. H.N. Djidjev. Force-Directed Methods For Smoothing Unstructured Triangular And Tetrahedral Meshes // Proceedings of 9th International Meshing Roundtable , Sandia National Laboratories, p.p. 395-406, October 2000.
13. L. Durbeck. Evaporation: A Technique For Visualizing Mesh Quality // Proceedings of 8th International Meshing Roundtable , South Lake Tahoe, CA, U.S.A., p.p. 259-265, October 1999.
14. D.A. Field. Laplacian Smoothing And Delaunay Triangulations // , vol. 4, p.p. 709-712, 1988.
15. P.J. Frey, H. Borouchaki, P.-L. George. Delaunay Tetrahedralization Using an Advancing-Front Approach // Proceedings of 5th International Meshing Roundtable , Sandia National Laboratories, p.p. 31-46, October 1996.
16. L.A. Freitag, C. Ollivier-Gooch. A Comparison of Tetrahedral Mesh Improvement Techniques // Proceedings of 5th International Meshing Roundtable , Sandia National Laboratories, p.p. 87-106, October 1996.
17. L.A. Freitag, C. Ollivier-Gooch.Tetrahedral Mesh Improvement Using Swapping and Smoothing // , vol. 40, p.p. 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. George. TET MESHING: Construction, Optimization and Adaptation // Proceedings of 8th International 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, p.p.793-812, 1994.
21. C. Hazlewood. Approximating Constrained Tetrahedralizations // Computer Aided Geometric Design , vol. 10, p.p. 67–87, 1993.
22. B. Joe. Delaunay Triangular Meshes in Convex polygons, SIAM J. Sci. Stat. Comput ., Vol. 7, p.p. 514-539, 1986.
23. B. Joe. Construction Of Three-Dimensional Delaunay Triangulations Using Local Transformations // Computer Aided Geometric Design , Vol. 8, p.p. 123-142, 1991.
24. B. Joe. Construction of Three-Dimensional Improved-Quality Triangulations Using Local Transformations // Siam J. Sci. Comput. , vol. 16, p.p. 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, p.p.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 into Tetrahedra-I. Verification and Orientation of Boundary Surfaces // Computers and Structures , Pergamon Press, Vol. 39, № 5, p.p. 493-500, 1991.
28. S.H. Lo. Volume Discretization into Tetrahedra - II. 3D Triangulation by Advancing Front Approach // Computers and Structures , Pergamon, Vol. 39, № 5, p.p. 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, MI, 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, p.p. 255-261, 1993.
32. S. Pirzadeh. Unstructured Viscous Grid Generation by Advancing-Layers Method // AIAA-93-3453-CP, AIAA, p.p. 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, p.p. 651-674, 1998.
35. S. Rebay. Efficient Unstructured Mesh Generation by Means of Delaunay Triangulation and Bowyer-Watson Algorithm // Journal Of Computational Physics , vol. 106, p.p. 125-138, 1993.
36. M.-C. Rivara. Selective Refinement/Derefinement Algorithms For Sequences Of Nested Triangulations // International Journal for Numerical Methods in Engineering , №28, p.p. 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, p.p. 281-290, 1998.
38. J. Ruppert. A Delaunay refinement algorithm for quality 2-dimensional mesh generation // Journal of Algorithms , №18, p.p. 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, p.p. 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 to Voronoi Polytopes // The Computer Journal , Vol. 24(2), p.p. 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, p.p. 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Пример: Точек (n) – 13 Точек (n) – 13 Внутренних (m) – 4 Внутренних (m) – 4 Треугольников – 15 = Треугольников – 15 = Ребер – 26 3*13-6 = 33 Ребер – 26 3*13-6 = 33
Свойства триангуляции Делоне 2. Триангуляция Делоне обладает максимальной суммой минимальных углов всех треугольников среди всех возможных триангуляций. 3. Триангуляция Делоне обладает минимальной суммой радиусов окружностей, описанных около треугольников, среди всех возможных триангуляций. Триангуляция Делоне НЕ триангуляция Делоне
Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Итеративные алгоритмы () Итеративные алгоритмы () Методы пошаговой выборки Методы пошаговой выборки Алгоритмы прямого (пошагового) построения (3) Алгоритмы прямого (пошагового) построения (3) Методы декомпозиции Методы декомпозиции Алгоритмы слияния (2) Алгоритмы слияния (2) Методы сканирования Методы сканирования Итеративные алгоритмы с измененным порядком добавления точек (1.4) Итеративные алгоритмы с измененным порядком добавления точек (1.4) Двухпроходные алгоритмы (4) Двухпроходные алгоритмы (4)
Методы пошагового ввода Итеративные алгоритмы () Общая схема итеративных алгоритмов построения триангуляции Делоне 1. На первых трех точках построить один треугольник 2. Цикл по всем оставшимся точкам p i набора S 3. Найти ближайший к точке p i треугольник t j текущей триангуляции 4. Если точка p i снаружи треугольника 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 = new Polygon; t->insert (a); t->insert (b); t->insert (c); return t; }
GRID- модели – модели регулярных ячеек.
Пусть
введена система координат
и
и
.
Пользователь задает
и шаги дискретизации
.
,
-
физические координаты точки.
Вычисляем
и
,
- разрядная сетка.
-
квантованные значения. Реальные:
-
параметр алгоритма – количество точек,
- вес. Чем ближе точка, тем больше вес.
-
степень расстояния (1 или 2).
Нормировочный
коэффициент: 
Чем
ближе к 1, тем больше учитываются точки
с большим весом.
Это
метод IDW – долгий, для каждой т. необходимо
найти соседей. Набор соседей может быть
эффективно найден - ближайшим. Каждая
из точек продуцирует «колышек»
определенной высоты. От нерегулярности
постановок точки многое зависит, для
этого берут
или
т.е. разделяют на сектора и в окрестности
точки строим.
Преимущество – простота
Недостаток:
------Билет 14. Tin-модель. Алгоритмы триангуляции Делоне------
1) Триангуляционные (tin).
Триангуляция – построение функции в виде совокупности кусочно - линейной функции
Триангуляция – интерполяция внутри выпуклой области.
Триангуляция – планарный граф, все внутренние ребра которого – треугольники; способ представления пространства в виде примыкающих друг к другу треугольников без перекрытий. На наборе точек триангуляция строится несколькими способами.
Нужен алгоритм для построения оптимальной триангуляции.
Плоскость, проходящая через 3 точки.
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-дерева (охватывающий потомки прямоугольник) не покрывают текущую точку, то необходимо выбрать для дальнейшего спуска по дереву потомка, ближайшего к точке поиска.
В результате будет найден некоторый треугольник, центр которого будет близок к заданной точке. Если в найденный треугольник не попадает заданная точка, то далее необходимо использовать обычный алгоритм поиска треугольника из простого итеративного алгоритма построения триангуляции Делоне.
