Модифицированный алгоритм триангуляции делоне. Критерии качества треугольных элементов

Основные определения и свойства

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

Свойства:

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

· Как следствие: если никакие четыре точки не лежат на одной окружности, триангуляция Делоне единственна.

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

· Триангуляция Делоне максимизирует сумму радиусов вписанных шаров.

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

· Триангуляция Делоне минимизирует максимальный радиус минимального объемлющего шара.

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

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

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

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

Говорят, что триангуляция удовлетворяет условию Делоне, если внутрь окружности, описанной вокруг любого построенного треугольника, не попадает ни одна из заданных точек триангуляции.

Триангуляция называется триангуляцией Делоне, если она является выпуклой и удовлетворяет условию Делоне.

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

Метод пустого шара Делоне. Построение в общем случае

Воспользуемся пустым шаром, который мы будем перемещать, изменяя его размер так, чтобы он мог касаться точек системы {А}, но всегда оставался пустым.

Итак, поместим в систему точек {А} пустой шар Делоне. Это всегда возможно, если выбрать шар достаточно малым. Начнем увеличивать его радиус, оставляя центр шара на месте. В какой-то момент поверхность шара встретит некоторую точку i системы {А}. Это обязательно произойдет, ибо в нашей системе нет неограниченно больших пустот. Будем продолжать увеличивать радиус пустого шара так, чтобы точка i оставалась на его поверхности. Для этого придется двигать центр шара от точки i. Рано или поздно шар достигнет своей поверхностью другой точки системы {А}.

Рис.3

Симплексы Делоне заполняют пространство без щелей и наложений.

Описанная сфера любого симплекса не содержит внутри себя других точек системы.

Пусть это будет точка j. Продолжим увеличивать радиус нашего шара, сохраняя уже обе точки на его поверхности. Увеличиваясь, шар достигнет какой-то третьей точки системы, точки k. В двумерном случае наш "пустой круг" в этот момент зафиксируется, т.е. станет невозможным дальнейшее увеличение его радиуса при сохранении круга пустым. При этом мы выявляем элементарную двумерную конфигурацию трех точек (i,j,k), определяющую некий треугольник, особенностью которого является то, что внутри его описанной окружности нет других точек системы {А}. В трехмерном пространстве шар не определяется тремя точками. Продолжим увеличивать его радиус, сохраняя все три найденные точки на его поверхности. Это будет возможно до тех пор, пока поверхность шара не встретится с четвертой точкой l системы. После этого движение и рост пустого шара станут невозможными. Найденные четыре точки (i,j,k,l) определяют вершины тетраэдра, который характерен тем, что внутри его описанной сферы нет других точек системы {А}. Такой тетраэдр называется симплексом Делоне.

Симплексом в математике называют простейшую фигуру в пространстве данной размерности: тетраэдр - в трехмерном пространстве; треугольник - в двумерном. Произвольная тройка (четверка) точек системы, не лежащих в одной плоскости, всегда определяет некий симплекс. Однако он будет симплексом Делоне только с том случае, если его описанная сфера пуста. Другими словами, симплексы Делоне определяются особым выбором троек (четверок) точек в системе {А}.

Мы построили один симплекс Делоне, однако, помещая пустой шар в различные места и повторяя ту же процедуру, можно определить и другие. Утверждается, что совокупность всех симплексов Делоне системы {А} заполняет пространство без наложений и щелей, т.е. реализует разбиение пространства, но на этот раз на тетраэдры. Это разбиение называется разбиением Делоне (рис.3).

Применение триангуляции Делоне

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

В двумерной интерполяции триангуляция Делоне разбивает плоскость на самые "толстые" треугольники, насколько это возможно, избегая слишком острых и слишком тупых углов. По этим треугольникам можно строить, например, билинейную интерполяцию.

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

Рис.4.

Задача расчета экспозиций склонов обычно используется для анализа освещенности Земли. В связи с этим часто возникает потребность дополнительного учета текущего положения Солнца, т.е. экспозиция вычисляется как направление между нормалью к треугольнику и направлением на Солнце.

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

Структура лекции Определения Определения Области применения Области применения Свойства триангуляции Делоне Свойства триангуляции Делоне Методы построения триангуляции Делоне Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования Двухпроходные методы Двухпроходные методы

Триангуляция Триангуляция – планарный граф все внутренние области которого являются треугольниками. Триангуляция – планарный граф все внутренние области которого являются треугольниками. Термин «Триангуляция» - это Термин «Триангуляция» - это граф; граф; процесс построения графа. процесс построения графа. Задача триангуляции набора точек 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 Скворцов рекомендует: итеративный алгоритм с динамическим кэшированием

А сегодня о чем? О триангуляции Делоне! Определение Определение Области применения Области применения Свойства триангуляции Делоне Свойства триангуляции Делоне Методы построения триангуляции Делоне Методы построения триангуляции Делоне Методы пошагового ввода Методы пошагового ввода Методы пошаговой выборки Методы пошаговой выборки Методы декомпозиции Методы декомпозиции Методы сканирования Методы сканирования Двухпроходные методы Двухпроходные методы

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

Расскажу секрет о том, как быстро проверить выполнение условия Делоне для двух треугольников.
Собственно сама оптимизация описана немного ниже(см.«Оптимизация алгоритма проверки условия Делоне через уравнение описанной окружности»), но расскажу обо всем по порядку.

В моем случае триангуляция применяется в трассировке изображения, для разбиения плоскости на примитивные сектора (треугольники). Как известно, она делится также на несколько этапов: корректировка, выявление границ, обход границ, заметание контуров. Это в самом общем виде. Я бы хотел остановиться, думаю, на самом сложном этапе: заметание плоскости.

На входе

Рисунок 1

Что надо сделать

Поиски

Алгоритм

Рисунок 2

Рисунок 3

Рисунок 4

Еще одно но: при сохранении очередного треугольника необходимо записывать вершины в обходе по часовой стрелке (в правой системе координат). Это пригодится в дальнейшем для уменьшения вычислительных ресурсов.

2) Повторяем шаг 1 пока не заметаем всю плоскость.

3) Если последовательностей несколько, т.е. одна, а внутри её еще одна или более внутренних контуров (Рисунок 1). Тут необходимо рассмотреть каждую последовательность отдельно. Возьмем очередной внутренний контур. Из одного внешнего и одного внутреннего сделаем два одиночных контура. Для этого нужно найти два «порта» из одного контура в другой. Условие для «портов»: они не должны пересекаться между собой(не должны соприкасаться даже концами), не должны пересекаться с линиями контуров (Рисунок 5).

Рисунок 5

Рисунок 6
4) Далее следует ввести поочередно все внутренние последовательности в уже образованные, отделенные друг от друга (пункт 3) последовательности. Сливать нужно с той, которая содержит новую. По определению ни одна внутренняя последовательность не касается и не пересекается с другими(как одной внешней, так и всеми возможными внутренними), так что все пройдет гладко.
Найдя порты (Рисунок 6) легко построить новые последовательности и обойти их пунктами 1 и 2 текущего алгоритма (Рисунок 7).

Рисунок 7

5) После 4-его этапа имеем список треугольников(Рисунок 8). Как бы с задачей уже справились, но осталось сделать картинку красивой: проверить выполнение условия Делоне (Рисунок 9).

Рисунок 8

Рисунок 9

6) Забегая вперед расскажу про шестой пункт. Он заключается в последовательном прогоне по списку полученных треугольников пунктом №5. Сначала метим все треугольники «грязными». В каждом цикле проверяем для каждого треугольника условие Делоне. Если условие не выполняется, то делаем перестроение и помечаем соседей и текущий треугольник «грязными». Если условие выполняется, то метим его чистым. В моей реализации алгоритма, каждый треугольник имеет ссылку на соседей. В этом случае 6-ой пункт работает наиболее быстро.

Подробнее о пятом этапе

Мощность вычислений №1: 10 операций умножения/деления и 13 операций сложения/вычитания.
Мощность вычислений №2: 29 операций умножения/деления и 24 операций сложения/вычитания.

С точки зрения вычислительной мощности, которая высчитывается к примеру в книге , выгоднее вариант №1. Его и реализовал, если бы не… (Рисунок 10). Как оказалось после постановки данного метода на «конвейер», получилась неопределенность. Это вариант, когда сам угол А больше 180 градусов. Он рассматривается в книге как один из отдельных частных методов. А с этим пропадает вся его элегантность, прозрачность и производительность. А так же в последствии оказалось, что метод №2 можно очень существенно оптимизировать.

Рисунок 10

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

Итак имеем:
Проверка условия для точки M(X, Y) уравнением окружности, проходящей через точки A(x1, y1), B(x2, y2), C(x3, y3), можно записать в виде:

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

Подробности можно взять в великолепной книге . (Нет, не я ее автор)
Итак, sign a - это знак направления обхода, с самого начала я строил треугольники по часовой стрелке, так что его можно опустить (он равен единице).

A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);

D >= 0

Рисунок 11

Просто не правда ли?

Согласно книге, опять же,

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)*(y1*x2 - x1*y2) <= 0

Имеем: 15 операций умножения/деления и 14 операций сложения/вычитания.

Спасибо за внимание. Жду критики.

Список используемой литературы

Пространственная триангуляция Делоне

Задача построение сети неперекрывающихся треугольников является одной из базовых в вычислительной геометрии и широко используется в машинной графике и геоинформационных системах для моделирования поверхности и решения пространственных задач.

Впервые задача построения сети неперекрывающихся треуголь­ников была поставлена в 1934 году в работе советского математика Б. Н. Делоне, который сформулировал и соответствующие условия.

В математике задачей построения триангуляции по заданным точкам называют задачу их попарного соединений непересекающимися отрезками так, чтобы образовалась сеть треугольников. Основными ее элементами являются (рис.5.3): узлы (вершины треугольников), ребра (стороны) и грани (собственно треугольники). Построенная три­ан­гуляция может быть выпуклой (если таковым будет минимальный многоугольник, охватывающий область моделирования), невыпуклой (если триангуляция не является выпуклой) и оптимальной (если сумма длин всех ребер минимальна).

Сеть таких треугольников называется триангуляцией Делоне, если она удовлетворяет некоторым условиям:

Внутрь окружности, описанной вокруг любого треугольника, не попадает ни одна из исходных точек (рис. 5.3);

Триангуляция является выпуклой и удовлетворяет сформулиро­ванному выше условию Делоне;

Сумма минимальных углов всех треугольников максимальна из всех возможных триангуляций;

Сумма радиусов окружностей, описанных около треугольников, минимальна среди всех возможных триангуляций .

Первый из названных выше критериев построения триангуляции Делоне, называемый круговым, является одним из основных и проверяется для любой пары треугольников с общими гранями. Математическая интерпретация критерия вытекает из рис. 5.3:

(5.2)

Существует множество способов построения триангуляции Делоне, которая является одним из самых популярных в последнее время способов построения триангуляционной сетки. Она применяется во многих ГИС системах для построения моделей рельефа.

В приложении к двумерному пространству она формулируется следующим образом: система взаимосвязанных неперекрывающихся треугольников имеет наименьший периметр, если ни одна из вершин не попадает внутрь ни одной из окружностей, описанных вокруг образованных треугольников (рис. 5.4).

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

Это означает, что образовавшиеся треугольники при такой триангуляции максимально приближаются к равносторонним, а каждая из сторон образовавшихся треугольников из противолежащей вершины видна под максимальным углом из всех возможных точек соответствующей полуплоскости. Это именно та оптимальная триангуляция, по ребрам которой делается обычно линейная интерполяция для построения изолиний.

Многие алгоритмы построения триангуляции Делоне используют следующую теорему .

Теорема 1. Триангуляцию Делоне можно получить из любой другой триангуляции по той же си­стеме точек, последовательно перестраивая пары соседних треугольников ABC и BCD, не удовлетво­ряющих условию Делоне, в пары треугольников ABD и ACD (рис. 5.5).

Рис. 5.5.. Перестроение треугольников, не удовлетворяющих условию Делоне

Такую операцию перестроения часто называют флипом. Данная теорема позволяет строить три­ангуляцию Делоне последовательно, вначале строя некоторую триангуляцию, а потом последовательно улучшая ее в смысле условия Делоне. При проверке условия Делоне для пар соседних треугольников можно использовать непосредственно определение, но иногда используются другие способы, основанные на условиях, перечисленных выше.

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

Как было сказано выше одна из важнейших операций, выполняемых при построении три­ангуляции, является проверка условия Делоне для заданных пар треугольников. На основе определения триангуляции Делоне и соответствующих условий на практике обычно используют несколько способов проверки:

– проверка через уравнение описанной окружности;

– проверка с заранее вычисленной описанной окружностью;

– проверка суммы противолежащих углов;

– модифицированная проверка суммы противолежащих углов.

В многих системах выполняется проверка с заранее вычисленной описанной окружностью. Основная идея алгоритма проверки через за­ранее вычисленные окружности заключается в предварительном вычислении для каждого построенного треугольника центра и радиуса описанной вокруг него окружности, после чего проверка условия Делоне будет сводиться к вычислению расстояния до центра этой окружности и сравнению результата с ради­усом. Центр и радиус r окружности, описанной вокруг можно найти как , , , r 2 = (b 2 + с 2 - 4аd)/4а 2 , где значения а, b, с, d определены по формулам (5.3)

(5.3)

Другая запись уравнения этой окружности имеет вид:

(5.5.)

(5.6)

Тогда условие Делоне для будет выполняться только тогда, когда для любой другой точки триангуляции будет:

(x 0 – x C) 2 + (y 0 – y C) 2 ≥ r 2 . (5.7)

В настоящее время существует множество алгоритмов построения триангуляции Делоне. Многие из известных алгоритмов используют определение триангуляции Делоне как вторичный признак триангуляции. Поэтому в таких алгоритмах отмечаются следующие слабости:

– алгоритмы используют постоянно вычисляемые тригонометрические функции, что резко замедляет процесс;

– при исследовании взаимоотношения точек и базового отрезка возникают очень малые углы, и при использовании тригонометрических функций постоянно появляется опасность исчезновения порядка и деления на 0 в связи с ограниченной точностью представлений данных в компьютере, эта ситуация требует постоянной дополнительной обработки .

Наиболее известные программные продукты строят триангуляцию Делоне, используя теорему о пустом шаре как основной, первичный принцип построения треугольников. Алгоритм выглядит так:

– все множество точек делится на треугольники, т.е. создаются комбинации из трех точек;

– для каждой комбинации находится описанная окружность и координаты ее центра;

– если внутри окружности текущей комбинации не находится ни одной точки из оставшихся то эта комбинация есть треугольник – часть триангуляции Делоне.

К достоинствам этого алгоритма можно отнести:

– отсутствие использования тригонометрических функций, что не замедляет процесс построений;

– непосредственное построение триангуляции Делоне, без каких – либо предварительных построений;

– простота всех вычислений и преобразований;

– в итоге триангуляционная сетка представлена множеством треугольников, а не отдельных линий.

Построенная таким образом триангуляция является геометрической основой для построения изолиний.

Алгоритмы построения триан­гу­ляции Делоне можно разделить на ряд групп, различающиеся структурой используемых входных данных, объемом вычис­ли­тель­ных операций, исходными пред­по­сылками и др. Рассмотрим некоторые из них.

Алгоритмы слияния предполагают разбиение множества исход­ных точек на подмножества, построение на каждом из них триан­гуляции и последующее их объединение в единую сеть. Сущ­ность одного из таких алгоритмов сводится к следующему.

Множество исходных точек делится вертикальными линиями на две или более частей, после чего каждая из них разделяются горизонтальными и вертикаль­ными линиями на примерно равные части. В результате вся область исходных точек оказывается разделенной на примитивы по три – четыре точки (рис. 2.4), по которым строятся один – два треугольника.

Слияние этих треугольников в единую сеть выполняется путем построения двух базовых линий (P 0 P 1 и P 2 P 3 , рис. 5,7.а), проведении окружностей переменного радиуса с центром на серединном перпендикуляре к базовой линии (рис. 5.7, б), поиску попадающего на окружность узла (точка A , рис. 5.7. в) и построению нового треугольника (P 0 P 1 A). При этом может возникнуть необходимость удаления уже существующего треугольника (например, P 0 AB) .

Итеративные алгоритмы основаны на идее последовательного добавления точек в частично построенную триангуляцию с одновременным ее улучшением и перестроением в соответствии с критериями Делоне. В общем виде они включают несколько шагов и сводятся к построению треугольника на первых трех исходных точках и исследованию нескольких вариантов размещения очередной точки. В частности, рассматриваются варианты ее попадания за границу области моделирования, на существующий узел или ребро, внутрь построенного треугольника и др. Каждый из этих вариантов предполагает выполнение определенной операции: разбивки ребра на два, грани – на три и т.д.; после чего выполняется проверка полученных треу­голь­ников на соответствие условию Делоне и необходимые перестроения.

Двухпроходные алгоритмы, предусматривают вначале построение некоторой триангуляции, игнорируя условия Делоне, а затем – ее перестроение в соответствии с этими условиями. Пример при­менения алгоритма приведен на рис. 5.8.

Для приближения создаваемой модели рельефа к реальной в нее внедряются дополнительные элементы, обеспечивающие учет и отображение ее линейных и площадных структурных элементов. Такими дополнительными элементами являются широко используе­мые в топографии структурные линии, определяющие «скелет рельефа»: водоразделы, тальвеги, хребты, обрывы, уступы, озера, овраги, береговые линии, границы искусственных сооружений и др., совокупность которых создает как бы каркас триангуляции Делоне. Эти структурные линии внедряются в триангуляцию в качестве ребер треугольников, чем и достигается моделирование реальных элементов рельефа на фоне общих неровностей земной поверхности. Такие ребра называются структурными (фиксированными, неперестраиваемыми), не пересекают ребра других треугольников и в последующем не изменяются.

Задача построения модели поверхности с учетом структурных линий называется триангуляцией Делоне с ограничениями, если условия Делоне выполняются для любой пары смежных треугольников, которые не разделяются структурными линиями. Наиболее эффективно, считают исследователи, выполняется построение такой триангуляции с помощью итеративных алгоритмов.

Алгоритмы построения триангуляции Делоне реализуются с вещественным или целочисленным представлением координат узлов, что позволяет существенно повысить скорость и точность обработки, но порождает проблемы поиска и исключения совпадающих узлов.

Модель TIN легко редактируется путем перемещения узлов, вставки новых, удаления имеющихся, изменения положения одного или нескольких ребер, внедрения новых структурных линий и др. Такие изменения всегда затрагивают небольшую группу смежных треугольников, не требуют перестроения всей сети и осуществляются в режиме on-line, по указанию курсором на соответствующий элемент .

О точности:

Располагая пикеты на характерных элементах рельефа (например, водоразделах и тальвегах), мы игнорируем более мелкие элементы в промежутках. При построении горизонталей1 по таким ребрам треугольников возникает ошибка, которая зависит от величины неровности рельефа и угла наклона местности. Например, средняя погрешность съемки рельефа, не должна превышать 1/3 сечения рельефа при углах наклона поверхности от 2 до 10 градусов. Можно рассчитать, что при сечении рельефа 0,5 м предельная величина пропущенной неровности (то есть отклонения поверхности земли от прямой, проходящей через соседние пикеты) не должна превышать (0,5/3)*cos10°=0,16 м.

Для точности определения объема перемещаемого грунта важна также площадь, занимаемая не учитываемой деталью рельефа. Допустим, в квадрате 20х20 м между двумя парами пикетов имеется цилиндрическая выпуклость с максимальной высотой 0,15 м. Нетрудно подсчитать, что ее неучет при представлении данной поверхности только двумя треугольниками приведет к ошибке приблизительно в 40 м3. Не так уж много, но для участка в 1 га, расположенного на холме или верхней (как правило, выпуклой) части склона, получится уже 40*25=1000 м3 лишнего грунта. Если же брать пикеты в два раза чаще (то есть через 10 м), ошибка уменьшится вчетверо и составит 250 м3 на гектар. Этот фактор можно учесть заранее, поскольку положительные формы равнинного рельефа обычно имеют выпуклую форму, а отрицательные – вогнутую. Если на подлежащий съемке участок имеются приближенные данные о рельефе, то радиус кривизны поверхности и необходимую густоту пикетов легко рассчитать по величинам заложения горизонталей или отдельным высотным отметкам.

(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

1. Введение

Среди двух классов методов триангуляции - прямых и итерационных - последние обладают достаточной универсальностью и поэтому, в отличие от прямых, могут быть использованы для триангуляции областей довольно произвольного вида. За эту универсальность приходится расплачиваться существенно большим потреблением ресурсов и более трудоемкой реализацией метода в конкретном алгоритме.

В настоящее время разработано большое количество программных пакетов на основе того или иного итерационного метода, реализующих построение сеток (частично или полностью) в автоматическом режиме. В основном эти пакеты коммерческие, что вполне оправдано с учетом затрачиваемых на их создание усилий, ведь трехмерное пространство имеет ряд неприятных особенностей, существенно затрудняющих жизнь разработчику .

Сетки, построенные итерационными методами, как правило, неструктурированы и неоднородны. Неструктурированность обусловлена тем, что топология сетки формируется в процессе построения, и поэтому естественно может варьироваться даже в пределах одной подобласти. По этой же причине однородность если и может возникнуть, то только случайно.

Поскольку перед построением сетки ничего нельзя сказать о ее будущей структуре, нельзя гарантировать и ее качества. Часто построенную сетку можно существенно улучшить с помощью одного из многочисленных методов оптимизации . Этой возможностью обычно не пренебрегают, благо что время, затрачиваемое на оптимизацию, как правило, существенно меньше времени, затрачиваемого на построение.

Целью данной работы является рассмотрение и классификация существующих методов построения тетраэдрических сеток в трехмерных областях. Ввиду значительного объема информации ниже рассматриваются только так называемые "итерационные методы". Прямые методы описаны в .

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (проект № 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, но на самом деле это не так. Например, существующий тетраэдр может целиком оказаться внутри проверяемого тетраэдра.