Методы на основе критерия Делоне

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

Рис. 5. Пример триангуляции простой трехмерной области (призма с двумя цилиндрическими отверстиями) методом граничной коррекции. Показаны только граничные узлы "видимых" сплайнов.

Триангуляция Делоне обладает рядом интересных свойств [2, 23, 30]. В частности, триангуляция Делоне обладает наибольшей суммой минимальных углов всех своих треугольников, а также наименьшей суммой радиусов описанных вокруг треугольников окружностей среди всех возможных сеток на той же системе точек. Поскольку величины минимальных углов явным образом фигурируют в некоторых оценках качества аппроксимации [4], можно сказать, что триангуляция Делоне для заданного набора точек в определенном смысле является оптимальной.

Алгоритмы построения сеток на основе критерия Делоне впервые были предложены Чарльзом Лоусоном (Charles Lawson) и Дэйвом Уотсоном (Dave Watson) [43]. За короткое время их идеи были существенно развиты, и в настоящий момент проблема двумерной триангуляции методами на основе критерия Делоне фактически является закрытой. Разработаны быстрые и эффективные алгоритмы построения и оптимизации сеток, в том числе и в сложных (двумерных) областях [2, 3].

Рис. 6. Сетка, удовлетворяющая критерию Делоне (слева), и не удовлетворяющая ему (справа).

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

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

У двумерного "флипа" есть и трехмерный аналог, хотя основанный на другой идее. Оказывается, почти любые два соседних тетраэдра можно превратить в три. Для этого достаточно вставить внутрь шестигранника, образованного тетраэдрами, внутреннее ребро (рис. 7), причем сделать это можно единственным образом. Слово "почти" стоит здесь потому, что если любые три вершины этого шестигранника лежат на одной прямой либо четыре его вершины лежат в одной плоскости, то эта операция приведет к образованию вырожденных тетраэдров. Операция замены 2 тетраэдров на 3 и наоборот называется "трейд[3]" (от англ. trade). Как и "флип", "трейд" позволяет заменять элементы, не удовлетворяющие критерию Делоне, на элементы, ему удовлетворяющие.

Рис. 7. "Трейд" - замена 2 тетраэдров на 3

Попытки использовать "трейд" для приведения произвольной трехмерной сетки к триангуляции Делоне закончились неудачно, поскольку такие алгоритмы очень часто зацикливались в локальных оптимумах. Вместе с тем не так давно был получен важный теоретический результат: канадский математик Б. Джо (Barry Joe) доказал, что если к уже существующей триангуляции Делоне добавить новые тетраэдры (разбив один из внутренних или присоединив тетраэдр к внешней грани), то полученную сетку можно гарантированно привести к триангуляции Делоне с помощью последовательных "трейдов" [23]. Этот факт играет огромную роль в построении триангуляций Делоне с ограничениями.