Перенос баз данных с одного SQL Server на другой Изменения в системе защиты SQL Server Новые средства разработки Новые элементы программирования на языке Visual Basic Редактирование и анализ данных с помощью запросов

Лекции по компьютерной графике начало

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

Суть :

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

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

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

Алгоритм:

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


 

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

полам;

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

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

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

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

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

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

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

  1 на ребро 4.

Примечание:

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

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

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

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

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

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

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

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


 

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

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

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

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

Дизайн, инженерная и Web графика