Триангуляция Делоне: условие пустого круга и флипы

Триангуляция Делоне - это способ соединить набор точек на плоскости треугольниками так, чтобы получившаяся сетка была максимально равномерной: без вытянутых и тонких треугольников. Она названа в честь Бориса Делоне и лежит в основе построения сеток для метода конечных элементов, интерполяции рельефа, компьютерной графики и геоинформационных систем. Главная её особенность формулируется одним условием - условием пустой описанной окружности, - и из него автоматически следует ключевое свойство: триангуляция Делоне максимизирует минимальный угол среди всех возможных триангуляций того же набора точек. Ниже разберём это условие строго, покажем алгоритм построения и формулу числа треугольников. Чтобы сразу почувствовать связь точек и сетки, покрути калькулятор ниже: он перестраивает триангуляцию при каждом изменении и рисует описанный круг, который остаётся пустым.

Что такое триангуляция Делоне

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

Рассчитать для своей задачи

Условие пустой описанной окружности

Формальное определение звучит так: треугольник принадлежит триангуляции Делоне тогда и только тогда, когда внутри его описанной окружности не лежит ни одна другая точка набора.

$\text{для каждого треугольника } \triangle ABC: \quad \forall P \neq A,B,C \colon \; |PO| \ge R,$

где $O$ - центр описанной окружности треугольника $ABC$, а $R$ - её радиус. Иными словами, описанный круг должен быть пустым: все остальные точки лежат на окружности или вне её. Это локальное условие, проверяемое для каждого треугольника отдельно, но если оно выполнено для всех треугольников сразу, триангуляция глобально оптимальна по форме.

Рассчитать для своей задачи

В калькуляторе голубой круг описан вокруг подсвеченного треугольника - подвигай ползунки, и убедишься, что он всегда остаётся пустым. Проверять условие удобно через определитель: точка $D$ лежит внутри описанной окружности $\triangle ABC$ (вершины обходятся против часовой стрелки), если

$\begin{vmatrix} A_x - D_x & A_y - D_y & (A_x - D_x)^2 + (A_y - D_y)^2 \\ B_x - D_x & B_y - D_y & (B_x - D_x)^2 + (B_y - D_y)^2 \\ C_x - D_x & C_y - D_y & (C_x - D_x)^2 + (C_y - D_y)^2 \end{vmatrix} > 0.$

Этот предикат «in-circle» не требует явно вычислять центр и радиус и потому устойчивее в расчётах.

Свойство максимума минимального угла

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

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

Алгоритм Боуэра-Уотсона

На практике триангуляцию Делоне чаще всего строят инкрементным алгоритмом Боуэра-Уотсона. Идея проста и наглядна:

1. Создаём большой вспомогательный «супертреугольник», заведомо накрывающий все точки набора.
2. Добавляем точки по одной. Для очередной точки находим все треугольники, в чью описанную окружность она попала, - они нарушают условие Делоне и образуют «плохую» область.
3. Удаляем эти треугольники: на их месте остаётся многоугольная дыра. Соединяем новую точку со всеми вершинами границы дыры - получаем новые треугольники.
4. Когда все точки вставлены, удаляем треугольники, опирающиеся на вершины супертреугольника.

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

Рассчитать для своей задачи

Сколько получается треугольников и рёбер

Число элементов триангуляции жёстко фиксировано и не зависит от расположения точек, а только от их количества и числа точек на выпуклой оболочке. Пусть всего $N$ точек, из них $B$ лежат на границе выпуклой оболочки. Тогда число треугольников $T$ и рёбер $E$ равно

$T = 2N - 2 - B, \qquad E = 3N - 3 - B.$

Эти формулы выводятся из формулы Эйлера для плоского графа $V - E + F = 2$. Например, для $N = 9$ точек, из которых на оболочке лежат $B = 5$, получаем $T = 2\cdot 9 - 2 - 5 = 11$ треугольников. В калькуляторе счётчики треугольников и рёбер пересчитываются на лету - проверь формулу для разных $N$.

Связь с диаграммой Вороного

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

Частые ошибки

• Путают условие с минимальной суммарной длиной рёбер. Делоне минимизирует не длину, а «тонкость» - максимизирует минимальный угол. Триангуляция с минимальной суммой рёбер - это другая задача.
• Забывают про общее положение точек. Если четыре точки лежат на одной окружности, триангуляция Делоне не единственна - любая из диагоналей допустима. На практике добавляют символическое возмущение.
• Считают, что порядок вставки меняет результат. Сама триангуляция Делоне единственна (в общем положении), от порядка вставки точек в Боуэра-Уотсона зависит только скорость, но не итог.
• Берут описанную окружность не того треугольника при флипе. Проверять условие надо для четырёхугольника из двух смежных треугольников, а не для произвольной пары.
• Игнорируют точки на границе круга. Условие нестрогое: точка строго внутри круга нарушает Делоне, точка на самой окружности - нет.

FAQ

Чем триангуляция Делоне лучше произвольной? Она избегает тонких вытянутых треугольников: максимизирует минимальный угол, поэтому даёт самые «правильные» по форме треугольники из возможных. Для расчётных сеток и интерполяции это критично - точность и устойчивость численных методов напрямую зависят от формы элементов.

Как проверить, является ли триангуляция Делоне? Для каждого ребра, общего у двух треугольников, проверьте предикат «in-circle»: попадает ли противоположная вершина одного треугольника внутрь описанной окружности другого. Если ни для одного ребра не попадает - триангуляция удовлетворяет условию Делоне.

Сколько треугольников будет для N точек? Для $N$ точек, из которых $B$ на выпуклой оболочке, ровно $T = 2N - 2 - B$ треугольников и $E = 3N - 3 - B$ рёбер. Число фиксировано формулой Эйлера и не зависит от расположения внутренних точек.

Коротко

Триангуляция Делоне соединяет точки треугольниками по одному правилу - описанная окружность каждого треугольника пуста. Из этого условия следует главное свойство: максимум минимального угла, то есть отсутствие тонких треугольников. Строят её инкрементно алгоритмом Боуэра-Уотсона или флипами рёбер, число элементов задаёт формула Эйлера $T = 2N - 2 - B$, а двойственная ей структура - диаграмма Вороного. Покрути калькулятор: пустой круг и сравнение диагоналей показывают суть нагляднее формул.