Комплексное исследование и разработка эффективных вычислительно устойчивых алгоритмов вычислительной геометрии и их реализации в геоинформационной системе

Комплексное исследование и разработка эффективных вычислительно устойчивых алгоритмов вычислительной геометрии и их реализации в геоинформационной системе

Автор: Скворцов, Алексей Владимирович

Шифр специальности: 05.13.18

Научная степень: Докторская

Год защиты: 2002

Место защиты: Томск

Количество страниц: 324 с. ил.

Артикул: 2635486

Автор: Скворцов, Алексей Владимирович

Стоимость: 250 руб.

ВВЕДЕНИЕ.
Глава 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. Требования к универсальной графической системе, работающей с
территориально определнной информацией.
1.4.1. Структуры данных, их хранение и выборка
1.4.2. Работа с атрибутивной информацией
1.4.3. Визуализация
1.4.4. Интерфейс и расширение системы.
1.4.5. Моделирование рельефа
1.4.6. Топологические модели и отношения
1.4.7. Алгоритмические проблемы.
1.5. Выводы
Глава 2. ТРИАНГУЛЯЦИЯ ДЕЛОНЕ
2.1. Определения.
2.2. Структуры для представления триангуляции
2.2.1. Структура данных Узлы с соседями.
ф 2.2.2. Структура данных Двойные рбра
2.2.3. Структура данных Узлы и треугольники.
2.2.4. Структура данных Узлы, рбра и треугольники
2.2.5. Структура данных Узлы, простые рбра и треугольники
2.3. Проверка условия Делоне.
2.3.1. Проверка через уравнение описанной окружности
2.3.2. Проверка с заранее вычисленной описанной окружностью
2.3.3. Проверка суммы противолежащих углов
2.3.4. Модифицированная проверка суммы противолежащих углов
2.4. Выводы
Глава 3. АЛГОРИТМЫ ПОСТРОЕНИЯ ТРИАНГУЛЯЦИИ ДЕЛОНЕ
3.1. Классификация алгоритмов.
3.2. Итеративные алгоритмы
3.3. Простой итеративный алгоритм.
3.3.1. Итеративный алгоритм Удаляй и строй
3.4. Алгоритмы с индексированием поиска треугольников.
3.4.1. Итеративный алгоритм с индексированием треугольников
3.4.2. Итеративный алгоритм с индексированием центров треугольников кЕдеревом
3.4.3. Итеративный алгоритм с индексированием центров треугольников квадродеревом.
3.5. Алгоритмы с кэшированием поиска треугольников
3.5.1. Итеративный алгоритм триангуляции со статическим
кэшированием поиска
3.5.2. Итеративный алгоритм триангуляции с динамическим кэшированием поиска.
3.5.3. Трудомкости алгоритмов с кэшированием поиска
3.6. Итеративные алгоритмы триангуляции с изменнным порядком
добавления точек.
3.6.1. Итеративный полосовой алгоритм.
3.6.2. Итеративный квадратный алгоритм
3.6.3. Итеративный алгоритм с послойным сгущением.
3.6.4. Итеративный алгоритм с сортировкой вдоль кривой,
Ф заполняющей плоскость
3.6.5. Итеративный алгоритм с сортировкой по кд.
3.7. Алгоритмы слияния
3.8. Алгоритм слияния Разделяй и властвуй.
3.8.1. Слияние триангуляций Удаляй и строй
3.8.2. Слияние триангуляций Строй и перестраивай
3.8.3. Слияние триангуляций Строй, перестраивая.
3.9. Рекурсивный алгоритм с разрезанием по диаметру.
3 Полосовые алгоритмы слияния.
. Выбор числа полос в алгоритме полосового слияния
. Алгоритм выпуклого полосового слияния.
. Алгоритм невыпуклого полосового слияния.
3 Алгоритмы прямого построения триангуляции Делоне
. Пошаговый алгоритм
. Пошаговые алгоритмы триангуляции с ускорением поиска соседей Делоне
. Пошаговый алгоритм с к1деревом поиска.
. Клеточный пошаговый алгоритм
3 Двухпроходные алгоритмы.
. Двухпроходные алгоритмы слияния.
. Модифицированный иерархический алгоритм.
. Линейный алгоритм.
. Веерный алгоритм
. Алгоритм рекурсивного расщепления.
. Ленточный алгоритм
3 Число перестроений в алгоритмах триангуляции.
3 Сравнение алгоритмов триангуляции Делоне.
3 Клеточный алгоритм построения сверхбольшой триангуляции Делоне.
3 Выводы.
Глава 4. ТРИАНГУЛЯЦИЯ ДЕЛОНЕ С ОГРАНИЧЕНИЯМИ.
4.1. Определения.
4.2. Цепной алгоритм построения триангуляции с ограничениями
4.3. Итеративный алгоритм построения триангуляции Делоне с
ограничениями.
4.3.1. Вставка структурных отрезков Строй, разбивая
4.3.2. Вставка структурных отрезков Удаляй и строй.
4.3.3. Вставка структурных отрезков Перестраивай и строй
4.4. Классификация треугольников
4.5. Выделение многоугольников из триангуляции
4.6. Выводы.
Глава 5. ВЫЧИСЛИТЕЛЬНАЯ УСТОЙЧИВОСТЬ АЛГОРИТМОВ
ТРИАНГУЛЯЦИИ
5.1. Причины возникновения ошибок при вычислениях.
5.2. Применение целочисленной арифметики
5.3. Вставка структурных отрезков.
5.4. Выводы.
Глава 6. ПРИМЕНЕНИЕ ТРИАНГУЛЯЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ
ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ
6.1. Введение.
6.2. Построение буферных зон
6.3. Построение зон близости
6.4. Построение взвешенных зон близости.
6.5. Построение и анализ триангуляционных моделей поверхностей
6.6. Построение разрезов поверхности
6.7. Построение изоклин.
6.8. Построение экспозиций склонов
6.9. Вычисление объемов земляных работ
6 Построение зон и линий видимости
6 Выводы
Глава 7. СЖАТИЕ ТРИАНГУЛЯЦИИ
7.1. Введение.
7.2. Метод шелушения
7.3. Анализ алгоритма шелушения.
7.4. Шелушение с активным выбором ребра.
7.4.1. Шелушение с минимальной суммой внешних углов.
7.4.2. Шелушение с минимальным правым внешним углом.
7.4.3. Шелушение с 4ситуационным кодированием Хаффмана
7.4.4. Шелушение с 6ситуационным кодированием Хаффмана
7.5. Сравнение различных алгоритмов шелушения.
7.6. Сжатие координат узлов триангуляции с предсказанием
7.7. Выводы.
Глава 8. ПОСТРОЕНИЕ ОБЪЕДИНЕНИЯ, ПЕРЕСЕЧЕНИЯ И РАЗНОСТИ
ПРОИЗВОЛЬНЫХ МНОГОУГОЛЬНИКОВ
8.1. Введение.
8.2. Определения
8.3. Обзор известных алгоритмов.
8.3.1. Алгоритм ОРурка.
8.3.2. Алгоритм СазерлендаХоджмана.
8.3.3. Алгоритмы ВейлераАзертона, Ватти и ГрайнераХорманна
8.3.4. Алгоритм МаргалитаКнотта
8.4. Алгоритм на основе триангуляции
8.4.1. Классификация треугольников
8.4.2. Выделение многоугольников из триангуляции
8.5. Линейноузловой алгоритм.
8.5.1. Построение топологии.
8.5.2. Классификация рбер модели и конструирование многоугольников.
8.6. Сравнение алгоритмов построения оверлеев.
8.7. Выводы.
Глава 9. ГЛОБАЛЬНЫЕ АЛГОРИТМЫ ПОСТРОЕНИЯ ДЕРЕВЬЕВ.
9.1. Введение.
9.2. Алгоритмы работы с деревьями.
9.2.1. Поиск
9.2.2. Вставка
9.2.3. Удаление.
9.3. Глобальные алгоритмы.
9.4. Алгоритмы разбиения множества объектов на минимально
пересекающиеся группы
9.4.1. Базовый алгоритм.
9.4.2. Клеточный алгоритм.
9.4.3. Алгоритм Разделяй и властвуй.
9.5. Уточнение разбиений
9.6. Практический анализ глобальных алгоритмов
9.7. Выводы
Глава . ГЕОИНФОРМАЦИОННАЯ СИСТЕМА ГРАФИН 4.
.1. Общая характеристика
.2. Архитектура системы.
.2.1. Структуры данных
.2.2. Менеджер проектов и редакторы документов
.2.3. Работа с картами и чертежами
.2.4. Визуализация векторных данных.
.2.5. Универсальная технология отображения условных знаков .
.2.6. Модуль цифрового моделирования рельефа
.2.7. Подготовка карт к печати
.2.8. Интерфейс прикладного программирования
.3. Технология анализа топологических отношений графических объектов на плоскости.
.3.1. Топологические отношения объектов чертежей и карт
.3.2. Построение графовой модели
.3.3. Реализация в системе ГрафИн.
.4. Применение графовых моделей для анализа инженерных сетей
.4.1. Задачи анализа инженерных сетей.
.4.2. Графовые модели инженерных сетей
.4.3. Анализ электрических сетей
.4.4. Анализ водопроводных сетей
.5. Анализ транспортных сетей.
.5.1. Структуры данных
.5.2. Базовые задачи
.5.3. Расчет транспортных районов и пассажиропотоков
.6. Интегрированный городской кадастр.
.6.1. Кадастр инженерных коммуникаций.
.6.2. Разделы информационной системы
.6.3. Работа с эксплуатационной информацией.
.7. Прочие применения ГИС ГрафИн
.7.1. Геоинформационная система землеустройства.
.7.2. Информационная система жилого фонда.
.7.3. Программа расчета режимов электрических сетей.
.7.4. Информационная система инженерных сетей нефтсгазопромыслов
.8. Сравнение системы ГрафИн с другими системами ГИС и САПР
.9. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Среди самых актуальных базовых вычислительных задач можно выделить задачи регионального поиска графических объектов на плоскости, задачи построения планарной триангуляции и е анализа, задача построения оверлеев, задача анализа топологических отношений объектов на карте или чертеже, решения которых рассматриваются в следующих главах. Для всех этих задач существуют различные алгоритмы решения, однако большинству из них присущи различные ограничения по типам входных данных, точности вычислений. Многие из теоретически эффективных алгоритмов никогда нигде не использовались, т. Целью последующих глав является разработка более эффективных и вычислительно устойчивых алгоритмов, адекватно обрабатывающих любые виды исходных данных и предназначенных для применения в реальной геоинформационной системе. На основе обзора ряда современных реализаций геоинформационных систем и систем автоматизированного проектирования общего назначения выявлен набор базовых функций данных систем, выявлены их достоинства и недостатки в применении к работе с пространственно определнными данными пп. Показано, что системы каждого из этих классов в настоящее время обладают принципиальными недостатками, которые сложно преодолевать, оставаясь в рамках существующих концепций. Именно поэтому приходится использовать разные системы на различных этапах технологической цепочки решения сложных задач, а это громоздко и неудобно на практике. На основании проведнного автором анализа в пп. Данные требования можно рассматривать как минимальный набор свойств, которым должна удовлетворять любая современная геоинформационная система. В п. Это задача регионального поиска объектов, задачи построения, обработки и анализа планарной триангуляции, а также задача анализа топологических отношений объектов на плоскости. Глава 2. Впервые задача построения триангуляции Делоне была поставлена в г. Б.Н. Делоне . Триангуляция Делоне широко применяется в различных отраслях науки для аппроксимации различного рода поверхностей и непрерывных полей 2, разбиения плоскости на элементарные части в методах конечных элементов , учта взаимного влияния смежных тел и частиц . Трудомкость этой задачи составляет 0МоМ. Существуют алгоритмы, достигающие этой оценки в среднем и худшем случаях. Кроме того, известны алгоритмы, позволяющие в ряде случаев достичь в среднем ОЫ. Определение 1. Триангуляцией называется планарный граф, все внутренние области которого являются треугольниками рис. Определение 2. Выпуклой триангуляцией называется такая триангуляция, для которой минимальный многоугольник, охватывающий все треугольники, будет выпуклым. Триангуляция, не являющаяся выпуклой, называется невыпуклой. Задача 1 построение триангуляции по набору двумерных точек. Требуется соединить заданные точки на плоскости непересекающимися отрезками так, чтобы образовалась триангуляция. Определение 3. Триангуляция называется оптимальной, если сумма длин всех рбер минимальна среди всех возможных триангуляций, построенных на тех же исходных точках. В 3, 7 обосновано, что задача построения такой триангуляции видимо является КРполной. Поэтому для большинства реальных задач существующие алгоритмы построения оптимальной триангуляции неприемлемы ввиду слишком высокой трудомкости. При необходимости на практике применяют приближенные алгоритмы ,3, 8, 0. Одним из первых был предложен следующий алгоритм построения триангуляции 1. Жадный алгоритм построения триангуляции. Шаг 1. Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и он сортируется по длинам отрезков. Шаг 2. Начиная с самого короткого, последовательно выполняется вставка отрезков в триангуляцию. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается. Коней алгоритма. Заметим, что если все возможные отрезки имеют разную длину, то результат работы этого алгоритма однозначен, иначе он зависит от порядка вставки отрезков одинаковой длины. Определение 4. Триангуляция называется жадной, если она построена жадным алгоритмом. Трудомкость работы жадного алгоритма при некоторых его улучшениях составляет 4. Кроме оптимальной и жадной триангуляции также широко известна триангуляция Делоне, обладающая рядом практически важных свойств , , 3, 7.

Рекомендуемые диссертации данного раздела

28.06.2016

+ 100 бесплатных диссертаций

Дорогие друзья, в раздел "Бесплатные диссертации" добавлено 100 новых диссертаций. Желаем новых научных ...

15.02.2015

Добавлено 41611 диссертаций РГБ

В каталог сайта http://new-disser.ru добавлено новые диссертации РГБ 2013-2014 года. Желаем новых научных ...


Все новости

Время генерации: 0.244, запросов: 244