Книга. — Томск: Изд-во Том. ун-та, 2006. — 168 с.
В книге рассматриваются различные виды триангуляций: триангуляция
Делоне, триангуляция Делоне с ограничениями, оптимальная
триангуляция. Приводятся различные варианты структур данных для
представления триангуляции, разные способы проверки условия Делоне,
29 алгоритмов построения триангуляции Делоне, алгоритмы построения
триангуляции Делоне с ограничениями и приближённые алгоритмы
построения оптимальной триангуляции.
Рассматривается применение триангуляции Делоне с ограничениями для решения задач пространственного анализа на плоскости (оверлеи, буферные зоны, зоны близости) и моделирования рельефа (построение изолиний, изоконтуров, зон видимости, расчёт объёмов земляных работ). Описывается структура триангуляции переменного разрешения, используемая для моделирования рельефа, рассматриваются алгоритмы её построения.
Рекомендуется специалистам, занимающимся разработками в области ГИС и САПР. Может быть использована студентами, изучающими машинную графику, вычислительную геометрию и геоинформатику. Предисловие Определения и структуры данных
Определения
Количественные характеристики триангуляции
Структуры для представления триангуляции
Структура данных "Узлы с соседями"
Структура данных "Узлы и рёбра"
Структура данных "Двойные рёбра"
Структура данных "Узлы и треугольники"
Структура данных "Узлы, рёбра и треугольники"
Структура данных "Узлы, простые рёбра и треугольники"
Преобразование структур данных
Проверка условия Делоне
Проверка через уравнение описанной окружности
Проверка с заранее вычисленной описанной окружностью
Проверка суммы противолежащих углов
Модифицированная проверка суммы противолежащих углов
Алгоритмы построения триангуляции Делоне
Итеративные алгоритмы построения триангуляции Делоне
Простой итеративный алгоритм
Итеративный алгоритм "Удаляй и строй"
Алгоритмы с индексированием поиска треугольников
Итеративный алгоритм с индексированием треугольников
Итеративный алгоритм с индексированием центров треугольников k-D-деревом
Итеративный алгоритм с индексированием центров треугольников квадродеревом
Алгоритмы с кэшированием поиска треугольников
Итеративный алгоритм со статическим кэшированием поиска
Итеративный алгоритм с динамическим кэшированием поиска
Трудоёмкости алгоритмов с кэшированием поиска
Итеративные алгоритмы триангуляции с изменённым порядком добавления точек
Итеративный полосовой алгоритм
Итеративный квадратный алгоритм
Итеративный алгоритм с послойным сгущением
Итеративный алгоритм с сортировкой вдоль кривой, заполняющей плоскость
Итеративный алгоритм с сортировкой по Z-коду Алгоритмы построения триангуляции Делоне слиянием
Алгоритм слияния "Разделяй и властвуй"
Слияние триангуляций "Удаляй и строй"
Слияние триангуляций "Строй и перестраивай"
Слияние триангуляций "Строй, перестраивая"
Рекурсивный алгоритм с разрезанием по диаметру
Полосовые алгоритмы слияния
Выбор числа полос в алгоритме полосового слияния
Алгоритм выпуклого полосового слияния
Алгоритм невыпуклого полосового слияния Двухпроходные алгоритмы построения триангуляции Делоне
Двухпроходные алгоритмы слияния
Модифицированный иерархический алгоритм
Линейный алгоритм
Веерный алгоритм
Алгоритм рекурсивного расщепления
Ленточный алгоритм Прочие алгоритмы построения триангуляции Делоне
Пошаговый алгоритм
Пошаговые алгоритмы с ускорением поиска соседей Делоне
Пошаговый алгоритм с k-D-деревом поиска
Клеточный пошаговый алгоритм
Алгоритм построения через трёхмерные выпуклые оболочки Триангуляция Делоне с ограничениями
Определения
Цепной алгоритм построения триангуляции с ограничениями
Итеративный алгоритм построения триангуляции Делоне с ограничениями
Классификация треугольников
Выделение регионов из триангуляции Оптимальная триангуляция
Точный алгоритм
Квазижадная триангуляция
Алгоритмы с локальным перестроением треугольников Вычислительная устойчивость алгоритмов триангуляции
Причины возникновения ошибок при вычислениях
Применение целочисленной арифметики
Вставка структурных отрезков Пространственный анализ на плоскости
Триангуляционные модели поверхностей
Стрипификация триангуляции
Сверхбольшие триангуляции
Анализ поверхностей
Литература
Рассматривается применение триангуляции Делоне с ограничениями для решения задач пространственного анализа на плоскости (оверлеи, буферные зоны, зоны близости) и моделирования рельефа (построение изолиний, изоконтуров, зон видимости, расчёт объёмов земляных работ). Описывается структура триангуляции переменного разрешения, используемая для моделирования рельефа, рассматриваются алгоритмы её построения.
Рекомендуется специалистам, занимающимся разработками в области ГИС и САПР. Может быть использована студентами, изучающими машинную графику, вычислительную геометрию и геоинформатику. Предисловие Определения и структуры данных
Определения
Количественные характеристики триангуляции
Структуры для представления триангуляции
Структура данных "Узлы с соседями"
Структура данных "Узлы и рёбра"
Структура данных "Двойные рёбра"
Структура данных "Узлы и треугольники"
Структура данных "Узлы, рёбра и треугольники"
Структура данных "Узлы, простые рёбра и треугольники"
Преобразование структур данных
Проверка условия Делоне
Проверка через уравнение описанной окружности
Проверка с заранее вычисленной описанной окружностью
Проверка суммы противолежащих углов
Модифицированная проверка суммы противолежащих углов
Алгоритмы построения триангуляции Делоне
Итеративные алгоритмы построения триангуляции Делоне
Простой итеративный алгоритм
Итеративный алгоритм "Удаляй и строй"
Алгоритмы с индексированием поиска треугольников
Итеративный алгоритм с индексированием треугольников
Итеративный алгоритм с индексированием центров треугольников k-D-деревом
Итеративный алгоритм с индексированием центров треугольников квадродеревом
Алгоритмы с кэшированием поиска треугольников
Итеративный алгоритм со статическим кэшированием поиска
Итеративный алгоритм с динамическим кэшированием поиска
Трудоёмкости алгоритмов с кэшированием поиска
Итеративные алгоритмы триангуляции с изменённым порядком добавления точек
Итеративный полосовой алгоритм
Итеративный квадратный алгоритм
Итеративный алгоритм с послойным сгущением
Итеративный алгоритм с сортировкой вдоль кривой, заполняющей плоскость
Итеративный алгоритм с сортировкой по Z-коду Алгоритмы построения триангуляции Делоне слиянием
Алгоритм слияния "Разделяй и властвуй"
Слияние триангуляций "Удаляй и строй"
Слияние триангуляций "Строй и перестраивай"
Слияние триангуляций "Строй, перестраивая"
Рекурсивный алгоритм с разрезанием по диаметру
Полосовые алгоритмы слияния
Выбор числа полос в алгоритме полосового слияния
Алгоритм выпуклого полосового слияния
Алгоритм невыпуклого полосового слияния Двухпроходные алгоритмы построения триангуляции Делоне
Двухпроходные алгоритмы слияния
Модифицированный иерархический алгоритм
Линейный алгоритм
Веерный алгоритм
Алгоритм рекурсивного расщепления
Ленточный алгоритм Прочие алгоритмы построения триангуляции Делоне
Пошаговый алгоритм
Пошаговые алгоритмы с ускорением поиска соседей Делоне
Пошаговый алгоритм с k-D-деревом поиска
Клеточный пошаговый алгоритм
Алгоритм построения через трёхмерные выпуклые оболочки Триангуляция Делоне с ограничениями
Определения
Цепной алгоритм построения триангуляции с ограничениями
Итеративный алгоритм построения триангуляции Делоне с ограничениями
Классификация треугольников
Выделение регионов из триангуляции Оптимальная триангуляция
Точный алгоритм
Квазижадная триангуляция
Алгоритмы с локальным перестроением треугольников Вычислительная устойчивость алгоритмов триангуляции
Причины возникновения ошибок при вычислениях
Применение целочисленной арифметики
Вставка структурных отрезков Пространственный анализ на плоскости
Триангуляционные модели поверхностей
Стрипификация триангуляции
Сверхбольшие триангуляции
Анализ поверхностей
Литература