Метод триангуляции Делоне

Суть:

Позволяет получать триангуляцию, все треугольники стремятся к правильной форме.

В основе метода лежит круговой критерий:

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

дать в него.

Алгоритм:

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

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

полам;

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

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

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

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

г) Просматриваем стек флипов и, используя круговой критерий, решаем на-

до флиповать ребро или нет (если точка не попала в окружность, то флип

не нужен, а если попала – нужен)

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

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

1 на ребро 4.

Примечание:

Если у нас есть N вершин, то сколько у нас будет рёбер (R) и сколько треуголь-

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

хся на одну вершину.

Пусть у нас есть треугольник. На каждую точку, взятую в этом треугольнике до-

бавляется 2 треугольника. Следовательно, Т=2N.

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

3 новых ребра.

У каждой точки есть определённое количество соседних вершин, а общее коли-

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

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

Проверка кругового критерия может быть заменена на проверку расстояний

(длины диагоналей сравниваются и выбираются более короткие),но это уже не

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

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

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

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

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

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

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