Триангуляция Делоне и её применение

Скворцов Алексей Владимирович5-7511-1501-5

Скворцов А.В. Триангуляция Делоне и её применение. — Томск: Изд-во Том. ун-та, 2002. — 128 с.В книге рассматриваются триангуляция Делоне и её обобщение – триангуляция Делоне с ограничениями. Приводятся 5 вариантов структуры данных, 4 способа проверки условия Делоне, 4 группы алгоритмов построения триангуляции Делоне (всего 28 алгоритмов) с оценками трудоемкости, 4 алгоритма построения триангуляции Делоне с ограничениями.Рассматривается применение триангуляции Делоне с ограничениями для решения задач пространственного анализа на плоскости (оверлеи, буферные зоны, зоны близости) и моделирования рельефа (построение изолиний, изоконтуров, зон видимости, расчет объемов земляных работ). Описывается структура триангуляции переменного разрешения, используемая для моделирования рельефа, рассматриваются некоторые алгоритмы ее построения.Рекомендуется специалистам, занимающимся разработками в области ГИС и САПР. Может быть использована студентами, изучающими машинную графику, вычислительную геометрию и геоинформатику.

Содержание (текст)
С О Д Е Р Ж А Н И ЕПредисловиеГлава 1. Триангуляция Делоне1.1. Определения1.2. Структуры для представления триангуляции
1.2.1. Структура данных «Узлы с соседями»
1.2.2. Структура данных «Двойные ребра»
1.2.3. Структура данных «Узлы и треугольники»
1.2.4. Структура данных «Узлы, рёбра и треугольники»
1.2.5. Структура данных «Узлы, простые рёбра и треугольники»1.3. Проверка условия Делоне
1.3.1. Проверка через уравнение описанной окружности
1.3.2. Проверка с заранее вычисленной описанной окружностью
1.3.3. Проверка суммы противолежащих углов
1.3.4. Модифицированная проверка суммы противолежащих углов1.4. Алгоритмы триангуляции ДелонеГлава 2. Итеративные алгоритмы построения триангуляции Делоне2.1. Простой итеративный алгоритм
2.1.1. Итеративный алгоритм «Удаляй и строй»2.2. Алгоритмы с индексированием поиска треугольников
2.2.1. Итеративный алгоритм с индексированием треугольников
2.2.2. Итеративный алгоритм с индексированием центров треугольников k-D-деревом
2.2.3. Итеративный алгоритм с индексированием центров треугольников квадродеревом2.3. Алгоритмы с кэшированием поиска треугольников
2.3.1. Итеративный алгоритм со статическим кэшированием поиска
2.3.2. Итеративный алгоритм с динамическим кэшированием поиска
2.3.3. Трудоемкости алгоритмов с кэшированием поиска2.4. Итеративные алгоритмы триангуляции с изменённым порядком добавления точек
2.4.1. Итеративный полосовой алгоритм
2.4.2. Итеративный квадратный алгоритм
2.4.3. Итеративный алгоритм с послойным сгущением
2.4.4. Итеративный алгоритм с сортировкой вдоль кривой, заполняющей плоскость
2.4.5. Итеративный алгоритм с сортировкой по Z-кодуГлава 3. Алгоритмы построения триангуляции Делоне слиянием3.1. Алгоритм слияния «Разделяй и властвуй»
3.1.1. Слияние триангуляции «Удаляй и строй»
3.1.2. Слияние триангуляции «Строй и перестраивай»
3.1.3. Слияние триангуляции «Строй, перестраивая»3.2. Рекурсивный алгоритм с разрезанием по диаметру3.3. Полосовые алгоритмы слияния
3.3.1. Выбор числа полос в алгоритме полосового слияния
3.3.2. Алгоритм выпуклого полосового слияния
3.3.3. Алгоритм невыпуклого полосового слиянияГлава 4. Алгоритмы прямого построения триангуляции Делоне4.1. Пошаговый алгоритм4.2. Пошаговые алгоритмы с ускорением поиска соседей Делоне
4.2.1. Пошаговый алгоритм с k-D-деревом поиска
4.2.2. Клеточный пошаговый алгоритмГлава 5. Двухпроходные алгоритмы построения триангуляции Делоне5.1. Двухпроходные алгоритмы слияния
5.2. Модифицированный иерархический алгоритм
5.3. Линейный алгоритм
5.4. Веерный алгоритм
5.5. Алгоритм рекурсивного расщепления
5.6. Ленточный алгоритмГлава 6. Триангуляция Делоне с ограничениями6.1. Определения6.2. Цепной алгоритм построения триангуляции с ограничениями6.3. Итеративный алгоритм построения триангуляции Делоне с ограничениями
6.3.1. Вставка структурных отрезков «Строй, разбивая»
6.3.2. Вставка структурных отрезков «Удаляй и строй»
6.3.3. Вставка структурных отрезков «Перестраивай и строй»6.4. Классификация треугольников6.5. Выделение регионов из триангуляцииГлава 7. Вычислительная устойчивость алгоритмов триангуляции7.1. Причины возникновения ошибок при вычислениях
7.2. Применение целочисленной арифметики
7.3. Вставка структурных отрезковГлава 8. Пространственный анализ на плоскости8.1. Построение минимального остова
8.2. Построение оверлеев
8.3. Построение буферных зон
8.4. Построение зон близости
8.5. Построение взвешенных зон близости
8.6. Нахождение максимальной пустой окружностиГлава 9. Триангуляционные модели поверхностей9.1. Структуры данных
9.2. Упрощение триангуляции
9.3. Мультитриангуляция
9.4. Пирамида Делоне
9.5. Детализация триангуляции
9.6. Сжатие триангуляцииГлава 10. Анализ поверхностей10.1. Построение разрезов поверхности
10.2. Сглаживание изолиний
10.3. Построение изоклин
10.4. Построение экспозиций склонов
10.5. Вычисление объемов земляных работ
10.6. Построение зон и линий видимостиЛитература

Примеры страниц (сканы)
–
–
–

Доп. информация: —

Мои раздачи литературы по ГЕО-наукам (Геодезия, Картография, Землеустройство, ГИС, ДЗЗ и др.)
Геодезия и Системы спутникового позиционирования

Инженерная геодезия: учебное пособие. В 2-х частях. / Е. С. Богомолова, М. Я. Брынь, В. А. Коугия и др.; под ред. В. А. Коугия. — СПб.: Петербургский государственный университет путей сообщения, 2006-2008. — 179 с.
Поклад Г.Г. Геодезия: учебное пособие для вузов / Г.Г. Поклад, С.П. Гриднев. — М.: Академический Проект, 2007. — 592 с.
Справочник современного изыскателя / Под общ. ред. Л.Р. Маиляна. — Ростов н/Д: Феникс, 2006. — 590 с.: ил. — (Строительство и дизайн).
Селиханович В.Г., Козлов В.П., Логинова Г.П. Практикум по геодезии: Учебное пособие / Под ред. Селиханович В.Г. 2–е изд., стереотипное. — М.: ООО ИД «Альянс», 2006. — 382 с.
Интулов И.П. Инженерная геодезия в строительном производстве: Учеб. пособие для вузов / Воронеж. гос. арх.-строит. ун-т. — Воронеж, 2004. — 329 с.
Генике А.А., Побединский Г.Г. Глобальные спутниковые системы определения местоположения и их применение в геодезии. Изд. 2-е, перераб. и доп. — М.: Картгеоцентр, 2004. — 355 с.: ил.
Руководство пользователя по выполнению работ в системе координат 1995 года (СК-95). ГКИНП (ГНТА)-06-278-04. — М: ЦНИИГАиК, 2004. — 89 с.
Инструкция по нивелированию I, II, III и IV классов. ГКИНП (ГНТА)-03-010-02. — М.: ЦНИИГАиК, 2003. — 135 с.
Хаметов Т.И. Геодезическое обеспечение проектирования, строительства и эксплуатации зданий, сооружений: Учеб. пособие. — М.: Изд-во АСВ, 2002. — 200 с.
Серапинас Б.Б. Глобальные системы позиционирования: Учебное издание. — М.: ИКФ «Каталог», 2002. — 106 с.
Герасимов А.П. Уравнивание государственной геодезической сети. — М.: «Картгеоцентр» – «Геодезиздат», 1996. — 216 с.: ил.
Геодезия: учебное пособие для техникумов / Глинский С.П., Гречанинова Г.И., Данилевич В.М., Гвоздева В.А., Кощеев А.И., Морозов Б.Н. — М.: Картгеоцентр – Геодезиздат, 1995. — 483 с: ил.
Правила закладки центров и реперов на пунктах геодезической и нивелирной сетей. — М.: Картгеоцентр — Геодезиздат, 1993 — 104 с: ил.
Правила по технике безопасности на топографо-геодезических работах / Главное управление геодезии и картографии при Совете Министров СССР: Справочное пособ. — М.: Недра, 1991. — 303 с: ил.
Решение массовых геодезических задач на микроЭВМ: Справочное пособие / М.И. Коробочкин, В.С. Бережнов, Н.С. Зайцева, В.С. Красницкий. — М.: Недра, 1991. — 144 с.: ил.
Лукьянов В.Ф., Новак В.Е. и др. Лабораторный практикум по инженерной геодезии: Учебное пособие для ВУЗов. — М.: «Недра», 1990. — 336 с.
Новак В.Е., Лукьянов В.Ф. и др. Курс инженерной геодезии: Учебник для вузов под ред. проф. Новака В.Е. — М.: «Недра», 1989. — 432 с.
Лукьянов В.Ф., Новак В.Е., Ладонников В.Г. и др. Учебное пособие по геодезической практике. — М.: «Недра», 1986 — 236 с, с ил.
Справочник геодезиста: В 2-х книгах. / Под ред. Большакова В.Д. и Левчука Г.П. — Изд. 3-е, перераб. и доп. — М.: Недра, 1985. — 895 с.
Большаков В.Д., Деймлих Ф., Голубев А.Н., Васильев В.П. Радиогеодезические и электрооптические измерения: Учебник для вузов. — М.: Недра, 1985. — 303 с.: ил.
Урмаев М.С. Орбитальные методы космической геодезии. — М.: Недра, 1981. — 256 с.
Морозов В.П. Курс сфероидической геодезии / Изд. 2, перераб. и доп. — М.: Недра, 1979. — 296 с.
Пеллинен Л.П. Высшая геодезия (Теоретическая геодезия). — М.: «Недра», 1978. — 264 с.
Закатов П.С. Курс высшей геодезии. — Изд. 4, перераб. и доп. — М.: «Недра», 1976. — 511 с.
Грушинский Н.П. Теория фигуры Земли: Учебник для вузов / Изд. 2-е, перераб. и доп. — М.: «Наука», Гл. ред. физико-математической литературы, 1976. — 512 с.: ил., вкл.
Большаков В.Д., Васютинский И.Ю., Клюшин Е.Б. и др. Методы и приборы высокоточных геодезических измерений в строительстве. / Под ред. Большакова В.Д. — М.: «Недра», 1976, — 335 с.
Справочник геодезиста (в двух книгах) / Большаков В.Д., Левчук Г.П., Багратуни Г.В. и др.; под ред. Большакова В.Д., Левчука Г.П. Изд. 2, перераб. и доп. — М: «Недра», 1975. — 1056 с.
Федоров Б.Д. Маркшейдерско-геодезические приборы и инструменты. — М.: «Недра», 1971. — 288 стр.
Голубева 3.С., Калошина О.В, Соколова И.И. Практикум по геодезии. Изд. 3-е, перераб. — М.: «Колос», 1969. — 240 с. с илл. (Учебники и учеб. пособия для высш. с.-х. учеб. заведений).
Красовский Ф.Н. Избранные сочинения: в 4-х томах. — М.: Геодезиздат, 1953-1956. — 2001 с.
Красовский Ф.Н. Руководство по высшей геодезии: Курс Геодезического факультета Московского Межевого Института. Часть I. — М.: Издание Геодезического Управления В.С.Н.Х. С.С.С.Р. и Московского Межевого Института, 1926. — 479 с.

Фотограмметрия, Топография и Картография

Назаров А.С. Фотограмметрия: учебное пособие для студентов вузов. — Минск: ТетраСистемс, 2006. — 368 с.: ил.
Серапинас Б.Б. Математическая картография: Учебник для вузов / Балис Балио Серапинас. — М.: Издательский центр «Академия», 2005. — 336 с.
Стурман В.И. Экологическое картографирование: Учебное пособие. — М.: Аспект Пресс, 2003. — 251 с.
Кусов В.С. Памятники отечественной картографии: Учебное пособие. — М.: Изд-во Моск. ун-та, 2003. — 146 с.
Государства и территории мира: Справочник / Ред. Шкурков В.В. — М.: Роскартография, ЦНИИГАиК, 2003. — 74 с.
Математическая основа карт. Глава III из книги: Берлянт А.М. Картография: Учебник для вузов. — М.: Аспект Пресс, 2002. — 336 с.
Берлянт А.М. Картография: Учебник для вузов. — М.: Аспект Пресс, 2002. — 336 с.
Верещака Т.В. Топографические карты: научные основы содержания. — М.: МАИК «Наука/Интерпериодика», 2002. — 319 с.
Инструкция по фотограмметрическим работам при создании цифровых топографических карт и планов. ГКИНП (ГНТА)–02-036-02. — М.: ЦНИИГАиК, 2002. — 49 с.
Южанинов В.С. Картография с основами топографии: Учебное пособие для вузов. — М.: Высшая школа, 2001. — 302 с.
Тикунов В.С. Моделирование в картографии: Учебник. — М.: Изд-во МГУ, 1997. — 405 с.
Агапов С.В. Фотограмметрия сканерных снимков. — М.: «Картгеоцентр» – «Геодезиздат», 1996. — 176 с: ил.
Урмаев М.С. Космическая фотограмметрия: Учебник для вузов. — М.: Недра, 1989. — 279 с: ил.
Составление и использование почвенных карт (Под редакцией кандидата сельскохозяйственных наук Кашанского А.Д.). — 2-е изд., перераб. и доп. — М.: Агропр

---

Table of contents :
Содержание……Page 4
Предисловие……Page 7
1.1. Определения……Page 8
1.2. Структуры для представления триангуляции……Page 12
1.2.1. Структура данных «Узлы с соседями»……Page 13
1.2.2. Структура данных «Двойные ребра»……Page 14
1.2.3. Структура данных «Узлы и треугольники»……Page 15
1.2.4. Структура данных «Узлы, рёбра и треугольники»……Page 16
1.2.5. Структура данных «Узлы, простые рёбра и треугольники»……Page 17
1.3. Проверка условия Делоне……Page 18
1.3.2. Проверка с заранее вычисленной описанной окружностью……Page 19
1.3.3. Проверка суммы противолежащих углов……Page 21
1.3.4. Модифицированная проверка суммы противолежащих углов……Page 22
1.4. Алгоритмы триангуляции Делоне……Page 23
Глава 2. Итеративные алгоритмы построения триангуляции Делоне……Page 26
2.1. Простой итеративный алгоритм……Page 28
2.1.1. Итеративный алгоритм «Удаляй и строй»……Page 29
2.2.1. Итеративный алгоритм с индексированием треугольников……Page 30
2.2.2. Итеративный алгоритм с индексированием центров треугольников k-D-деревом……Page 31
2.3. Алгоритмы с кэшированием поиска треугольников……Page 32
2.3.2. Итеративный алгоритм с динамическим кэшированием поиска……Page 33
2.3.3. Трудоемкости алгоритмов с кэшированием поиска……Page 35
2.4.1. Итеративный полосовой алгоритм……Page 38
2.4.2. Итеративный квадратный алгоритм……Page 39
2.4.3. Итеративный алгоритм с послойным сгущением……Page 40
2.4.4. Итеративный алгоритм с сортировкой вдоль кривой, заполняющей плоскость……Page 42
2.4.5. Итеративный алгоритм с сортировкой по Z-коду……Page 43
3.1. Алгоритм слияния «Разделяй и властвуй»……Page 45
3.1.1. Слияние триангуляции «Удаляй и строй»……Page 46
3.1.2. Слияние триангуляции «Строй и перестраивай»……Page 48
3.2. Рекурсивный алгоритм с разрезанием по диаметру……Page 49
3.3. Полосовые алгоритмы слияния……Page 50
3.3.1. Выбор числа полос в алгоритме полосового слияния……Page 52
3.3.2. Алгоритм выпуклого полосового слияния……Page 54
3.3.3. Алгоритм невыпуклого полосового слияния……Page 55
4.1. Пошаговый алгоритм……Page 57
4.2.1. Пошаговый алгоритм с k-D-деревом поиска……Page 58
4.2.2. Клеточный пошаговый алгоритм……Page 59
5.1. Двухпроходные алгоритмы слияния……Page 60
5.2. Модифицированный иерархический алгоритм……Page 61
5.4. Веерный алгоритм……Page 62
5.5. Алгоритм рекурсивного расщепления……Page 63
5.6. Ленточный алгоритм……Page 64
6.1. Определения……Page 65
6.2. Цепной алгоритм построения триангуляции с ограничениями……Page 68
6.3. Итеративный алгоритм построения триангуляции Делоне с ограничениями……Page 69
6.3.1. Вставка структурных отрезков «Строй, разбивая»……Page 70
6.3.2. Вставка структурных отрезков «Удаляй и строй»……Page 71
6.3.3. Вставка структурных отрезков «Перестраивай и строй»……Page 73
6.4. Классификация треугольников……Page 75
6.5. Выделение регионов из триангуляции……Page 78
7.1. Причины возникновения ошибок при вычислениях……Page 80
7.2. Применение целочисленной арифметики……Page 83
7.3. Вставка структурных отрезков……Page 84
8.1. Построение минимального остова……Page 87
8.2. Построение оверлеев……Page 88
8.3. Построение буферных зон……Page 90
8.4. Построение зон близости……Page 92
8.5. Построение взвешенных зон близости……Page 93
8.6. Нахождение максимальной пустой окружности……Page 95
9.1. Структуры данных……Page 97
9.2. Упрощение триангуляции……Page 98
9.3. Мультитриангуляция……Page 103
9.4. Пирамида Делоне……Page 107
9.5. Детализация триангуляции……Page 108
9.6. Сжатие триангуляции……Page 110
10.1. Построение разрезов поверхности……Page 113
10.2. Сглаживание изолиний……Page 116
10.3. Построение изоклин……Page 117
10.4. Построение экспозиций склонов……Page 119
10.5. Вычисление объемов земляных работ……Page 120
10.6. Построение зон и линий видимости……Page 122
Литература……Page 126