Читать онлайн «Алгоритмы построения и анализа триангуляции»

Томский государственный университет Факультет информатики А. В. Скворцов, Н. С. Мирза АЛГОРИТМЫ ПОСТРОЕНИЯ И АНАЛИЗА ТРИАНГУЛЯЦИИ ИЗДАТЕЛЬСТВО ТОМСКОГО УНИВЕРСИТЕТА 2006 УДК 681. 3 ББК 22. 19 C 42 Скворцов А. В. , Мирза Н. С. C 42 Алгоритмы построения и анализа триангуляции. – Томск: Изд- во Том. ун-та, 2006. – 168 с. ISBN 5-7511-2028-5 В книге рассматриваются различные виды триангуляций: триангуляция Делоне, триангуляция Делоне с ограничениями, оптимальная триангуляция. Приводятся различные варианты структур данных для представления триангу- ляции, разные способы проверки условия Делоне, 29 алгоритмов построения триангуляции Делоне, алгоритмы построения триангуляции Делоне с ограниче- ниями и приближенные алгоритмы построения оптимальной триангуляции. Рассматривается применение триангуляции Делоне с ограничениями для решения задач пространственного анализа на плоскости (оверлеи, буферные зо- ны, зоны близости) и моделирования рельефа (построение изолиний, изоконту- ров, зон видимости, расчёт объёмов земляных работ). Описывается структура триангуляции переменного разрешения, используемая для моделирования рель- ефа, рассматриваются алгоритмы её построения. Рекомендуется специалистам, занимающимся разработками в области ГИС и САПР. Может быть использована студентами, изучающими машинную графику, вычислительную геометрию и геоинформатику. УДК 681. 3 ББК 22. 19 © А. В. Скворцов, Н. С. Мирза, 2006 ISBN 5-7511-2028-5 © Ю. С. Мирза, обложка, 2006  Оглавление Предисловие ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6 Глава 1. Определения и структуры данных ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 7 1. 1. Определения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 7 1. 2. Количественные характеристики триангуляции ... ... ... ... ... ... ... ... ... ... . . 11 1. 3. Структуры для представления триангуляции ... ... ... ... ... ... ... ... ... ... ... ... . 12 1. 3. 1. Структура данных «Узлы с соседями» ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 13 1. 3. 2. Структура данных «Узлы и рёбра» ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 14 1. 3. 3. Структура данных «Двойные рёбра» ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 15 1. 3. 4. Структура данных «Узлы и треугольники» ... ... ... ... ... ... ... ... ... ... ... ... ... ... 16 1. 3. 5. Структура данных «Узлы, рёбра и треугольники»... ... ... ... ... ... ... ... ... ... . 17 1. 3. 6. Структура данных «Узлы, простые рёбра и треугольники»... ... ... ... ... . 17 1. 3. 7. Преобразование структур данных ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 19 1. 4.