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

Триангуляцией называется планарное разбиение плоскости на плоские фигуры, из которых одна является внешней бесконечностью, а остальные - треугольниками. Будем рассматривать задачу построения триангуляции по заданному набору S двумерных точек. Эта задача состоит в соединении заданных точек из S прямыми отрезками так, чтобы никакие отрезки не пересекались. Решение этой задачи неоднозначно, поэтому возникает проблема построения оптимальной триангуляции.

Триангуляция Делоне - это такая триангуляция, при которой ни одна из точек набора S не попадает внутрь ни одной из описанных вокруг полученных треугольников окружностей. Впервые задача построение подобной триангуляции была поставлена советским математиком Борисом Николаевичем Делоне в 1934 г.

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

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

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

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