Автор работы: Пользователь скрыл имя, 02 Ноября 2013 в 17:43, реферат
Задача построения триангуляции Делоне является одной из базовых в вычислительной геометрии. К ней сводятся многие другие задачи, она широко используется в машинной графике и геоинформационных системах для моделирования поверхностей и решения пространственных задач. Впервые задача построения триангуляции Делоне была поставлена в 1934 г. в работе советского математика Бориса Николаевича Делоне.
Введение 3
1.Триангуляция Делоне
1.Основные определения и задачи триангуляции Делоне 4
2.Теоремы для алгоритмов построения триангуляции Делоне 6
3.Структуры для представления триангуляции 7
1.Структура «Узлы с соседями» 7
2.Структура «Двойные ребра» 8
3.Структура «Узлы и треугольники» 9
4.Структура «Узлы, ребра и треугольники» 10
5.Структура «Узлы, простые ребра и треугольники» 10
2.Алгоритмы триангуляции Делоне
1.Классификация алгоритмов триангуляции Делоне 12
2.Итеративные алгоритмы с кэшированием поиска треугольников 13
1.Алгоритм со статистическим кэшированием поиска 13
2.Алгоритм с динамическим кэшированием поиска 14
3.Полигоны Вороного 15
Заключение 16
Список использованной литературы 17
Рис 10 - Локализация точек в кэше (S - найденный квадрат, T - связанный с квадратом треугольник, T - конечный треугольник)
2.2.1 Алгоритм со статистическим кэшированием поиска
В алгоритме триангуляции со статическим кэшированием поиска необходимо выбрать число m и завести кэш в виде 2-мерного массива размером m×m ссылок на треугольники. Первоначально этот массив надо заполнить ссылками на самый первый построенный треугольник. Затем после выполнения очередного поиска, который был начат с квадрата (i, j) и в котором был найден некоторый треугольник T, необходимо обновить информацию в кэше: r(i,j) = ссылка_на_T . Размер статического кэша следует выбирать по формуле m = s ⋅ N^(3/8) , где s – коэффициент статического кэша. На практике значение s следует брать ≈ 0,6 − 0,9 (рис. 11).
Рисунок 11 - зависимость времени t построения триангуляции Делоне от значения s.
2.2.2 Алгоритм с динамическим кэшированием поиска
В алгоритме триангуляции
с динамическим кэшированием поиска
необходимо завести кэш минимального
размера, например 2× 2. По мере роста
числа добавленных в
Данный алгоритм кэширования позволяет одинаково эффективно работать на маленьком и большом количестве точек, заранее не зная их числа. Увеличение размера динамического кэша в 2 раза следует производить каждый раз при достижении числа точек в триангуляции n = r ⋅m2 , где r – коэффициент роста динамического кэша, а m – текущий размер кэша. На практике значение коэффициента роста динамического кэша следует выбрать ≈ 3 − 8 (рис. 12).
Рисунок 12 – Зависимость времени построения триангуляции Делоне t от значения s.
Для заданной точки Pi ∈{P1,...,PN} на плоскости многоугольником (ячейкой) Вороного называется геометрическое место точек на плоскости, которые находятся к Pi ближе, чем к любой другой заданной точке P j, j ≠ i . Совокупность многоугольников Вороного образует разбиение плоскости, представляющее векторную сеть.
Диаграммой Вороного заданного множества точек {P 1 ... Pn} называется совокупность всех многоугольников Вороного этих точек (рис. 13).
Диаграммы Вороного также иногда называют разбиением Тиссена и ячейками Дирихле.
Рисунок 13 – полигоны Вороного.
Одним из главных свойств диаграммы Вороного является её двойственность триангуляции Делоне. А именно, соединив отрезками те исходные точки, чьи многоугольники Вороного соприкасаются хотя бы углами, мы получим триангуляцию Делоне (рис. 14).
Рисунок 14 – Диаграмма Вороного и триангуляция Делоне.
Заключение
Были рассмотрены основные определения и теоремы задачи триангуляции Делоне и полигонов Вороного, структуры представления триангуляции. Проведен обзор итеративного алгоритма построения триангуляции – алгоритма с. кэшированием поиска треугольников, а также жадного алгоритма.
Для большинства случайных распределений исходных точек данный алгоритм работает значительно быстрее всех остальных алгоритмов. Однако на некоторых реальных данных, в которых последовательные исходные точки находятся вблизи друг друга (например, точки изолиний карт рельефа), алгоритм динамического кэширования может тратить большее время, чем другие алгоритмы.
Список использованной литературы
Красноярск 2013