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

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

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

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

Существуют и другие, более сложные методы. Так, метод под названием "упаковка пузырьков" ("bubble packing") основан на физической аналогии заполнения области мыльными пузырьками. В данном приложении модель этого процесса, разумеется, сильно упрощена - до уровня сил отталкивания между центрами пузырьков. Возникающие при этом дополнительные (довольно значительные) затраты на решение системы дифференциальных уравнений компенсируются максимально оптимальным размещением узлов, позволяющим получить сетки с априори высоким качеством триангуляции [41]. Используются и другие варианты [5, 8, 9, 35, 42].

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

Алгоритм состоит из следующих шагов:

1. Формирование множества U - набора заданных узлов.

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

3. Формирование множества G узлов сетки, куда переносятся все узлы U, использованные как вершины суперструктуры (если такие есть).

4. Если в качестве суперструктуры использован тетраэдр, производится переход к п. 5; иначе на основе узлов суперструктуры формируется триангуляция Делоне. Если в качестве суперструктуры использован правильный многогранник (октаэдр или икосаэдр), то это можно сделать следующим образом: выбрав произвольный узел из U, перенести его в G и путем вставки ребер между этим узлом и всеми вершинами многогранника сформировать сетку из n тетраэдров, где n - число граней, равное 8 или 20 соответственно. Эта сетка будет являться триангуляцией Делоне [22].

5.Поиск для всех тетраэдров сетки центров и радиусов описанной сферы.

6. Выбор произвольного узла q из множества U и перенос его в G, затем удаление всех тетраэдров, для которых q попадает внутрь описанной сферы. При этом в сетке образуется полость в виде многогранника, в общем случае имеющего звездную форму. При этом любой луч, исходящий из q, должен пересекать границу этого многогранника в единственной точке. Если обнаруживаются тетраэдры, для которых q лежит в плоскости одной из граней (это возможно в случае неоднозначности триангуляции Делоне, если, например, пять или больше точек лежат на одной сфере), то их тоже необходимо удалить. Заметим, что фактически ребро (или грань) удаляется только в том случае, если удаляются все смежные с ним тетраэдры; при этом ребра и грани суперструктуры не удаляются никогда. Новые тетраэдры образуются путем вставки ребер между q и вершинами этого многогранника. Доказано [23], что при этом получается триангуляция Делоне.

7. Нахождение для новообразованных тетраэдров центра и радиуса описанной сферы.

8. Если множество U не пусто, то переход к п. 6, иначе - к п. 9.

9. Удаление из сетки всех тетраэдров, в числе вершин которых есть вспомогательные узлы, использовавшиеся для построения суперструктуры. В результате получается сетка, построенная только на заданных узлах (G).

Двумерный аналог этого процесса проиллюстрирован на рис. 8.

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

Рис. 8. Двумерный вариант алгоритма на основе критерия Делоне

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

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