Алгоритм построения триангуляции
Постановка задачи: Задано конечное множество точек на плоскости с вещественными координатами,  . Требуется построить триангуляцию для этого множества точек.
Алгоритм решения задачи:
Будем одновременно строить выпуклую оболочку и триангуляцию (вовсе не обязательно Делоне).
Шаг 1: заводим двусвязный список в который, будем заносить отсортированные точки таким образом, чтобы можно было определить точки с совпадающими координатами по y (точки одного уровня).
Далее будем считать, что порядок в списке идет слева на право.
Шаг 2: сортируем лексикографически множество P. Берем две точки  ,  и сравниваем координаты y. Если  больше  , то говорим что i-тая точка больше (i+1)-й, меняем их местами и заносим в список; если и равны, то сравниваем координаты x аналогичным образом и заносим точки в список (рис 1).
Шаг 3: Строим триангуляцию итерационно по уровням и одновременно строим выпуклую оболочку.
- Если количество точек на первом уровне больше трех, и они не лежат на одной прямой, то строим треугольник (рис 2).
- Далее идет итерация по различным координатам y (по высоте). Пусть мы имеем выпуклую оболочку на i-м шаге (для i уровней по y). Рассмотрим переход от i-го шага итерации к (i+1)-му.
1. Если i-й и (i+1)-й уровни содержат ровно по одной точке то соединяем их и переходим к шагу 4, иначе переходим к шагу 2.
2. Из точек i-го и (i+1)-го уровня берем две, первую и последнюю. Соединяем первую точку i-го уровня с первой точкой (i+1)-го уровня, и последнюю с последней этих же уровней.
3. Выберем точку p0 из выпуклой оболочки, следующую за первой точкой i-го уровня в списке. Соединим первую точку (i+1)-го уровня с точкой p0, получим вектор  .
4. Проверим значение угла между вектором и вектором  , соединяющем первые точки i-го и (i+1)-го уровней (рис 4). Для этого решим систему уравнений
Находим параметры  и  . Если значения и положительны, то выбираем точку p1, следующую за p0 и переходим к шагу 4 положив вместо p0 p1. Иначе, обозначаем последнюю точку, при которой и были положительными plt.
5. Аналогичный процесс проводим для последней точки i+1-го уровня, только идем в обратном направлении, получая точку prt (Рис 3).
- Строим триангуляцию для (i+1)-го уровня
1. Последовательно соединяем крайнюю левую точку (i+1)-го уровня отрезками с точками от p0 до plt из выпуклой оболочки.
2. Аналогично соединяем крайнюю правую точку (i+1)-го уровня отрезками с точками от p0 до prt из выпуклой оболочки.
3. Для точек лежащих на уровнях i и i+1 строим триангуляцию.
- Перестраиваем выпуклую оболочку
1. Удаляем из выпуклой оболочки ребра от точки plt до точки prt.
2. Добавляем в цепь prt – крайнюю правую точку и plt – крайнюю левую точку.
а)
б)
в)
г)
Рис. 11.4.
|
