LEC-23 (Материалы к лекциям), страница 2

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

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

• спящие ребра: ребро триангуляции Делоне является спящим, если она еще не было обнаружено алгоритмом;

• живые ребра: ребро живое, если оно обнаружено, но известна только одна примыкающая к нему область;

• мертвые ребра: ребро считается мертвым, если оно обнаружено и известны обе примыкающие к нему области.

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

На каждой итерации выбирается любое одно из ребер е границы и оно подвергается обработке, заключающейся в поиске неизвестной области, ко торой принадлежит ребро е. Если эта область окажется треугольником f, определяемым концевыми точками ребра е и некоторой третьей вершинов v, то ребро е становится мертвым, поскольку теперь известны обе примыкающие к нему области. Каждое из двух других ребер треугольника t переводятся в следующее состояние: из спящего в живое или из живого в мертвое. Здесь вершина v будет называться сопряженной с ребром е. противном случае, если неизвестная область оказывается бесконечной плоскостью, то ребро е просто умирает. В этом случае ребро е не имеет сопряженной вершины.

Этот алгоритм для вычисления триангуляции Делоне по набору из n точек выполняется за время О(n²), поскольку при каждой итерации из границы исключается одно ребро. Поскольку каждое ребро исключается из границы только однажды — каждое ребро относится к границе однажды и затем исключается из нее, никогда не возвращаясь — число итераций равно числу ребер в триангуляции Делоне. Согласно теореме о триангуляции набор точек любая триангуляция содержит не более, чем О(n) ребер, поэтому алгоритм выполняет О(n) итераций. Поскольку на каждую итерацию тратится время О(n), то полностью алгоритм выполняется за время О(n²).

На рис. 5-Д показана работа алгоритма, где действие происходит сверху вниз и слева направо. Граница на каждом этапе выделена толстой линией.

Недостатки алгоритма:

• алгоритм использует постоянно вычисляемые тригонометрические

функции, что резко замедляет процесс;

• при исследовании взаимоотношения точек и базового отрезка возникают

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

Инкрементный алгоритм.

Этот алгоритм считается гораздо более эффективным, чем предыдущий.

Схема алгоритма следующая:

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

Полученная триангуляция превращается в триангуляцию Делоне. Для этого:

• последовательно для каждой точки выбирается гнездо треугольников,

имеющих эту точку в качестве общей вершины;

• для каждого из треугольников гнезда (последовательным обхождением

вокруг центральной вершины, скажем, по часовой стрелке) находится сопряженный треугольник, расположенный против этой центральной вершины;

• каждая полученная пара треугольников исследуется на соответствие

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

Флипом называется операция переброски диагонали выпуклого четырехугольника, т.е. если у четырехугольника ABCD разбитого диагональю BD на два треугольника, удалить эту диагональ и заменить ее на AC, то получится другая триангуляция четырехугольника (рис.6-Д).

 

 

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

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

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

из трех точек;

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

ее центра;

• если внутри окружности текущей комбинации не находится ни одной

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

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

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

замедляет процесс построений;

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

предварительных построений;

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

• в итоге триангуляционная сетка представлена множеством

треугольников, а не отдельных линий.

Заканчивая рассмотрение алгоритмов Делоне приведём названия наиболее используемых из них:

1. Radial sweep algorithm.

2. Recursive split algorithm (Алгоритм последовательного разбиения).

3. Divide-and-conquer algorithm (Алгоритм деления-и-включения).

4. Step-by-step algorithm.

5. Modified hierarchical algorithm (Модифицированный иерархический алгоритм)

6. Incremental algorithm.

7. Incremental delete-and-build algorithm.

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

На самом деле их значительно больше. Наиболее полный обзор алгоритмов триангуляции Делоне приведён в работе А.В. Скворцова. «Обзор алгоритмов построения триангуляции Делоне» в сборнике «Вычислительные методы и программирование», том. 3, 2002 год.