Введение
Глава 1. Графические системы: аналитический обзор 15
1 1 Графические системы, работающие с территориально определённой информацией 15
1.2. Геоинформационные системы 15
1.2 Л. Структуры данных 15
1.2-2- Выборка данных 18
1.2.3- Работа с атрибутивной информацией 19
1.2.4. Трёхмерные ГИС 20
1.2.5. Основные возможности ГИС 21
1.3. Системы автоматизированного проектирования 22
1.3.1. Структуры данных 22
1.3.2. Работа с атрибутивной информацией 23
1.3-3. Технологические и функциональные схемы 23
1.3.4. Основные возможности САПР 24
1.4. Требования к универсальной графической системе, работающей с
территориально определённой информацией 24
1.4.1. Структуры данных, их хранение и выборка 25
1.4.2. Работа с атрибутивной информацией 26
* 1.4.3. Визуализация 26
1.4.4. Интерфейс ирасширение системы , 26
1.4.5. Моделирование рельефа 26
L4.6. Топологические модели и отношения 27
1.4.7. Алгоритмические проблемы 27
1.5. Выводы 28
Глава 2. Триангуляция делоне 29
2Л- Определения 29
2.2. Структуры для представления триангуляции 33
2.2Л, Структура данных «Узлы с соседями» 34
ф, 2.2.2. Структура данных «Двойные рёбра» 35
2.2.3. Структура данных «Узлы и треугольники» 36
2.2.4. Структура данных «Узлы» рёбра и треугольники» 37
2.2.5. Структура данных «Узлы, простые рёбра и треугольники» 38
2.3. Проверка условия Делоне 40
2.3.1- Проверка через уравнение описанной окружности 40
2.3.2. Проверка с заранее вычисленной описанной окружностью...41
2.3.3. Проверка суммы противолежащих углов 42
2.3.4. Модифицированная проверка суммы противолежащих углов 43
2.4. Выводы 45
4 Глава 3. Алгоритмы построения триангуляции делоне 46
3.1. Классификация алгоритмов 46
3.2. Итеративные алгоритмы 48
3 3. Простой итеративный алгоритм 50
3.3Л. Итеративный алгоритм «Удаляй и строй» 52
3.4. Алгоритмы с индексированием поиска треугольников 52
3.4Л. Итеративный алгоритм с индексированием треугольников 53
3.4.2. Итеративный алгоритм с индексированием центров треугольников k-D-деревом 53
3.4.3. Итеративный алгоритм с индексированием центров треугольников квадродеревом 54
3.5. Алгоритмы с кэшированием поиска треугольников 54
3.5Л. Итеративный алгоритм триангуляции со статическим
кэшированием поиска 55
3.5.2. Итеративный алгоритм триангуляции с динамическим кэшированием поиска 56
3.5.3. Трудоёмкости алгоритмов с кэшированием поиска,- 57
3.6. Итеративные алгоритмы триангуляции с изменённым порядком
добавления точек 60
3.6.1. Итеративный полосовой алгоритм 60
3.6.2. Итеративный квадратный алгоритм 62
3.6.3. Итеративный алгоритм с послойным сгущением 63
3-6.4. Итеративный алгоритм с сортировкой вдоль кривой,
заполняющей плоскость 64
3.6.5. Итеративный алгоритм с сортировкой по Z-коду 66
3.7. Алгоритмы слияния 67
3.8. Алгоритм слияния «Разделяй и властвуй» 67
3.8Л. Слияние триангуляции «Удаляй и строй» 69
3.8.2. Слияние триангуляции «Строй и перестраивай» 70
3.8.3. Слияние триангуляции «Строй, перестраивая» 71
3.9. Рекурсивный алгоритм с разрезанием по диаметру 72
ЗЛО. Полосовые алгоритмы слияния 73
ЗЛОЛ. Выбор числа полос в алгоритме полосового слияния 74
3.10.2. Алгоритм выпуклого полосового слияния 76
3.10.3. Алгоритм невыпуклого полосового слияния 77
ЗЛ1- Алгоритмы прямого построения триангуляции Делоне 79
3.11Л. Пошаговый алгоритм 79
3.1L2. Пошаговые алгоритмы триангуляции с ускорением поиска
соседей Делоне 80
3.1 L3. Пошаговый алгоритм с k-D-деревом поиска 80
3.11.4. Клеточный пошаговый алгоритм 81
3.12. Двухпроходные алгоритмы 81
ЗЛ2.1. Двухпроходные алгоритмы слияния 82
3.12.2. Модифицированный иерархический алгоритм 83
3.12.3. Линейный алгоритм 83
3.12.4. Веерный алгоритм 84
3.12.5. Алгоритм рекурсивного расщепления 85
3.12.6. Ленточный алгоритм 86
3.13. Число перестроений в алгоритмах триангуляции 86
3.14. Сравнение алгоритмов триангуляции Делоне 88
3.15. Клеточный алгоритм построения сверхбольшой триангуляции
Делоне 92
3.16. Выводы 97
Глава 4. Триангуляция делоне с ограничениями 99
4Л. Определения 99
4.2. Цепной алгоритм построения триангуляции с ограничениями 103
4.3, Итеративный алгоритм построения триангуляции Делоне с ограничениями 104
4.3.1, Вставка структурных отрезков «Строй, разбивая» 105
4.3.2, Вставка структурных отрезков «Удаляй и строй» 106
4.33. Вставка структурных отрезков «Перестраивай и строй» 109
4.4. Классификация треугольников 111
4.5, Выделение многоугольников из триангуляции 114
4.6-Выводы 115
Глава 5. Вычислительная устойчивость алгоритмов триангуляции 116
5.1. Причины возникновения ошибок при вычислениях 116
5.2. Применение целочисленной арифметики , 119
5.3. Вставка структурных отрезков 120
5.4. Выводы 123
Глава 6. Применение триангуляции для решения задач вычислительной геометрии 124
6.1. Введение 124
6-2. Построение буферных зон 124
6.3. Построение зон близости 127
6-4. Построение взвешенных зон близости 129
6.5. Построение и анализ триангуляционных моделей поверхностей 132
6.6. Построение разрезов поверхности 134
6.7. Построение изоклин 138
6.8. Построение экспозиций склонов 140
6.9. Вычисление объемов земляных работ 141
6.10- Построение зон и линий видимости 144
6.11-Выводы 147
Глава 7. Сжатие триангуляции 148
7.1. Введение 148
7.2. Метод шелушения 149
7.3. Анализ алгоритма шелушения 151
7.4. Шелушение с активным выбором ребра 153
7.4.1. Шелушение с минимальной суммой внешних углов 153
7.4.2. Шелушение с минимальным правым внешним углом 154
7.4.3. Шелушение с 4-ситуационным кодированием Хаффмана 155
7.4.4. Шелушение с 6-ситуационным кодированием Хаффмана 158
7.5. Сравнение различных алгоритмов шелушения 161
7.6. Сжатие координат узлов триангуляции с предсказанием 163
7.7. Выводы 166
Глава 8. Построение объединения, пересечения и разности произвольных многоугольников 167
8.1. Введение 167
8.2. Определения 167
8.3. Обзор известных алгоритмов 170
8.3.1. Алгоритм ОРурка 171
8.3.2. Алгоритм Сазерленда-Ходжмана 171
8.3.3. Алгоритмы Вейлера-Азертона, Ватти и Грайнера-Хорманна 173
8.3.4. Алгоритм Маргалита-Кнотта 174
8.4. Алгоритм на основе триангуляции 175
8.4.1. Классификация треугольников 177
8.4.2. Выделение многоугольников из триангуляции 179
8.5. Линейно-узловой алгоритм 181
8.5.1. Построение топологии 185
8.5.2. Классификация рёбер модели и конструирование многоугольников 187
8.6. Сравнение алгоритмов построения оверлеев 190
8.7. Выводы 192
Глава 9. Глобальные алгоритмы построения r-деревьев 193
9.1. Введение 193
9.2. Алгоритмы работы с R-деревьями 195
9.2.1. Поиск 197
9.2.2. Вставка 197
9.2.3. Удаление 198
9.3. Глобальные алгоритмы 200
9.4. Алгоритмы разбиения множества объектов на минимально
пересекающиеся группы 201
9.4.1. Базовый алгоритм 201
9.4.2. Клеточный алгоритм 204
9.4.3. Алгоритм «Разделяй и властвуй» 207
9.5. Уточнение разбиений 210
9.6. Практический анализ глобальных алгоритмов 211
9.7. Выводы 216
Глава 10. Геоинформационная система графин 4.0 218
10.1. Общая характеристика 218
10.2. Архитектура системы 219
10.2.1. Структуры данных 220
10.2.2. Менеджер проектов и редакторы документов 221
10.2.3. Работа с картами и чертежами 223
10.2.4. Визуализация векторных данных 225
10.2.5. Универсальная технология отображения условных знаков .229
10.2.6. Модуль цифрового моделирования рельефа 232
10.2.7. Подготовка карт к печати 236
10.2.8. Интерфейс прикладного программирования 238
10.3. Технология анализа топологических отношений графических
объектов на плоскости 239
10.3.1. Топологические отношения объектов чертежей и карт 241
10.3.2. Построение графовой модели 243
10.3.3. Реализация в системе ГрафИн 244
10.4. Применение графовых моделей для анализа инженерных сетей...246
10.4.1. Задачи анализа инженерных сетей 246
10.4.2. Графовые модели инженерных сетей 248
10.4.3. Анализ электрических сетей 250
10.4.4. Анализ водопроводных сетей 253
10.5. Анализ транспортных сетей 256
10.5.1. Структуры данных 256
10.5.2. Базовые задачи 258
10.5.3. Расчет транспортных районов и пассажиропотоков 261
10.6. Интегрированный городской кадастр 265
10.6.1. Кадастр инженерных коммуникаций 267
10.6.2. Разделы информационной системы 270
10.6.3. Работа с эксплуатационной информацией 276
10.7. Прочие применения ГИС ГрафИн 278
10.7.1. Геоинформационная система землеустройства 278
10.7.2. Информационная система жилого фонда 279
10.7.3. Программа расчета режимов электрических сетей 280
10.7.4. Информационная система инженерных сетей нефтегазопромыслов 281
10.8. Сравнение системы ГрафИн с другими системами ГИС и САПР 282
10.9. Выводы 285
Заключение 287
Литература
