Если провести окружность вокруг 3-ч точек, то другие точки не должны попа-

дать в него.

Алгоритм:

1) Все точки, которые надо стриангулировать, лежат внутри прямоугольника:

2) После этого проводят начальную триангуляцию: делим прямоугольник по-

полам;

3) Берётся точка (например А) и проводится триангуляция:

а) Определяем , в какой треугольник попала эта точка;

б) Делим этот треугольник на 3 треугольника;

в) Помещаем в стек флипов 3 ребра (на рис. 1, 2, 3);

г) Просматриваем стек флипов и , используя круговой критерий, решаем на до флиповать ребро или нет (если точка не попала в окружность, то флип не нужен, а если попала – нужен)

Флип – переброска ребра.

На этом основании в рассматриваемом примере произошла замена ребра

1 на ребро 4.

Примечание:

Если у нас есть N вершин, то сколько у нас будет рёбер (R) и сколько треугольников (Т), а так же найдём количество соседних треугольников (К), приходящихся на одну вершину.

Пусть у нас есть треугольник. На каждую точку, взятую в этом треугольнике, добавляется 2 треугольника. Следовательно, Т=2N.

Число рёбер: R=3N, так как при добавлении каждой точки добавляется ещё и 3 новых ребра.

У каждой точки есть определённое количество соседних вершин, а общее количество прикреплений рёбер к треугольникам будет равно: 2R.

Следовательно: (т.е. у каждой точки есть по “шесть соседей”)

Проверка кругового критерия может быть заменена на проверку расстояний (длины диагоналей сравниваются и выбираются более короткие), но это уже не триангуляция Делоне.

Флип производится с учётом критерия флипа (связан с окружностью)

Решение кругового критерия можно свести к следующему решению:

Введём следующие обозначения :

= отрезок 01; = отрезок 02 и т. д.

Необходимо решить вопрос о том : Какое ребро выбрать? (12 или 34)

В этом нам поможет следующее выражение: