3. Описание модифицированного алгоритма построения триангуляции Делоне

Классический алгоритм построения триангуляции Делоне, основанный на полном переборе всех троек вершин, может быть значительно ускорен, если при построении учитывать свойства триангуляции как планарного графа. Например, если сумма углов при вершине достигла 360, то эта вершина не может принадлежать более ни одному треугольнику (кроме уже отстроенных), и при дальнейшем переборе троек вершин данную вершину рассматривать не нужно. Исключать из повторного рассмотрения также нужно уже встречавшиеся “зоны неоднозначности“ – выше упоминавшиеся точки, лежащие на одной окружности при условии, что их больше трёх. Значительно ускорить алгоритм позволяет перенесение начальной точки построения в центр масс области и предварительная сортировка точек набора в порядке их удаления от центра масс.

Схема работы алгоритма:

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

2. Перебираем комбинации точек по 3. Пусть {v1,v2,v3} – проверяемая на данной итерации комбинация точек, где точка v1 получена в первом цикле (по i), v2 – во втором (по j), а v3 – в третьем цикле (по k). Для исключения полного перебора всех комбинаций выполняем следующие действия:

   1. В начале цикла по i проверяем сумму углов при выбранной точке. Если сумма углов треугольников, уже вошедших в триангуляцию, с вершиной v1 равна 360 градусов, то триангуляция не может содержать больше ни одного треугольника с данной вершиной, и можно сразу перейти к рассмотрению следующей тройки точек. То есть выполняется переход к следующей точке v1.

   2. Аналогичная проверка делается в начале следующего цикла (по j) для точки v2.

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

   4. Выбираем точку v3, проверяя соответствующую сумму углов триангуляции при v3.

   5. Если выполнены успешно все проверки для вершин v1, v2, v3, то переходим к проверке выполнения условия Делоне по следующей схеме:

• для треугольника {v1, v2, v3} находим центр и радиус описанной окружности;

• проверяем точки входного множества на нахождение их внутри или на окружности, если найдены точки, лежащие на окружности и их больше трёх, то триангуляция может быть получена не единственным образом, поэтому будем называть такие окружности с точками – “зоной неоднозначности”, и заносить их радиусы в отдельный список;

• если радиус описанной окружности текущего треугольника {v1, v2, v3} уже числится в списке “зон неоднозначности”, то, не делая дополнительных проверок, расширяем данную “зону неоднозначности”;

• строим триангуляцию “зон неоднозначности” как выпуклого полигона “веером”.

6. Если условие Делоне выполнилось, то треугольник входит в триангуляцию. Определяем углы при его вершинах и дополняем ими суммы углов при соответствующих им входных точках.

7. Проверяем сумму углов при точке v1, так как возможно, что один из углов последнего отстроенного треугольника дополнил его до 360 градусов.