Задача построения триангуляции Делоне является одной из базовых в вычислительной геометрии. К ней сводятся многие другие задачи, она широко используется в машинной графике и геоинформационных системах для моделирования поверхностей и решения пространственных задач.В книге рассматриваются триангуляция Делоне и её обобщение – триангуляция Делоне с ограничениями. Приводятся 5 вариантов структуры данных, 4 способа проверки условия Делоне, 4 группы алгоритмов построения триангуляции Делоне (всего 28 алгоритмов) с оценками трудоемкости, 4 алгоритма построения триангуляции Делоне с ограничениями.Рассматривается применение триангуляции Делоне с ограничениями для решения задач пространственного анализа на плоскости (оверлеи, буферные зоны, зоны близости) и моделирования рельефа (построение изолиний, изоконтуров, зон видимости, расчет объемов земляных работ).Описывается структура триангуляции переменного разрешения, используемая для моделирования рельефа, рассматриваются некоторые алгоритмы ее построения.Рекомендуется специалистам, занимающимся разработками в области ГИС и САПР. Может быть использована студентами, изучающими машинную графику, вычислительную геометрию и геоинформатику.
Author(s): А. В. Скворцов
Publisher: Изд-во Том. ун-та
Year: 2002
Language: Russian
Pages: 128
City: [Томск]
Титульный лист......Page 1
Содержание......Page 3
Предисловие......Page 6
1.1. Определения......Page 7
1.2. Структуры для представления триангуляции......Page 11
1.2.1. Структура данных "Узлы с соседями"......Page 12
1.2.2. Структура данных "Двойные рёбра"......Page 13
1.2.3. Структура данных "Узлы и треугольники"......Page 14
1.2.4. Структура данных "Узлы, рёбра и треугольники"......Page 15
1.2.5. Структура данных "Узлы, простые рёбра и треугольники"......Page 16
1.3. Проверка условия Делоне......Page 17
1.3.2. Проверка с заранее вычисленной описанной окружностью......Page 18
1.3.3. Проверка суммы противолежащих углов......Page 20
1.3.4. Модифицированная проверка суммы противолежащих углов......Page 21
1.4. Алгоритмы триангуляции Делоне......Page 22
Глава 2. Итеративные алгоритмы построения триангуляции Делоне......Page 25
2.1. Простой итеративный алгоритм......Page 27
2.1.1. Итеративный алгоритм "Удаляй и строй"......Page 28
2.2.1. Итеративный алгоритм с индексированием треугольников......Page 29
2.2.2. Итеративный алгоритм с индексированием центров треугольников k-D-деревом......Page 30
2.3. Алгоритмы с кэшированием поиска треугольников......Page 31
2.3.2. Итеративный алгоритм с динамическим кэшированием поиска......Page 32
2.3.3. Трудоемкости алгоритмов с кэшированием поиска......Page 34
2.4.1. Итеративный полосовой алгоритм......Page 37
2.4.2. Итеративный квадратный алгоритм......Page 38
2.4.3. Итеративный алгоритм с послойным сгущением точек......Page 39
2.4.4. Итеративный алгоритм с сортировкой вдоль кривой, заполняющей плоскость......Page 41
2.4.5. Итеративный алгоритм с сортировкой по Z-коду......Page 42
3.1. Алгоритм слияния "Разделяй и властвуй"......Page 44
3.1.1. Слияние триангуляции "Удаляй и строй"......Page 45
3.1.2. Слияние триангуляций "Строй и перестраивай"......Page 47
3.2. Рекурсивный алгоритм с разрезанием по диаметру......Page 48
3.3. Полосовые алгоритмы слияния......Page 49
3.3.1. Выбор числа полос в алгоритме полосового слияния......Page 51
3.3.2. Алгоритм выпуклого полосового слияния......Page 53
3.3.3. Алгоритм невыпуклого полосового слияния......Page 54
4.1. Пошаговый алгоритм......Page 56
4.2.1. Пошаговый алгоритм с k-D-деревом поиска......Page 57
4.2.2. Клеточный пошаговый алгоритм......Page 58
5.1. Двухпроходные алгоритмы слияния......Page 59
5.2. Модифицированный иерархический алгоритм......Page 60
5.4. Веерный алгоритм......Page 61
5.5. Алгоритм рекурсивного расщепления......Page 62
5.6. Ленточный алгоритм......Page 63
6.1. Определения......Page 64
6.2. Цепной алгоритм построения триангуляции с ограничениями......Page 67
6.3. Итеративный алгоритм построения триангуляции Делоне с ограничениями......Page 68
6.3.1. Вставка структурных отрезков "Строй, разбивая"......Page 69
6.3.2. Вставка структурных отрезков "Удаляй и строй"......Page 70
6.3.3. Вставка структурных отрезков "Перестраивая и строй"......Page 72
6.4. Классификация треугольников......Page 74
6.5. Выделение регионов из триангуляции......Page 77
7.1. Причины возникновения ошибок при вычислениях......Page 79
7.2. Применение целочисленной арифметики......Page 82
7.3. Вставка структурных отрезков......Page 83
8.1. Построение минимального остова......Page 86
8.2. Построение оверлеев......Page 87
8.3. Построение буферных зон......Page 89
8.4. Построение зон близости......Page 91
8.5. Построение взвешенных зон близости......Page 92
8.6. Нахождение максимальной пустой окружности......Page 94
9.1. Структуры данных......Page 96
9.2. Упрощение триангуляции......Page 97
9.3. Мультитриангуляция......Page 102
9.4. Пирамида Делоне......Page 106
9.5. Детализация триангуляции......Page 107
9.6. Сжатие триангуляции......Page 109
10.1. Построение разрезов поверхностей......Page 112
10.2. Сглаживание изолиний......Page 115
10.3. Построение изоклин......Page 116
10.4. Построение экспозиций склонов......Page 118
10.5. Вычисление объемов земляных работ......Page 119
10.6. Построение зон и линий видимости......Page 121
Литература......Page 125
