Диссертация на тему "Эффективные алгоритмы вычислительной геометрии и их реализация в геоинформационной системе", скачать бесплатно автореферат по специальности 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ

Глава 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.3. Алгоритмы построения триангуляции Делоне.
2.3.1. Алгоритмы слияния.
2.3.2. Итеративные алгоритмы.
2.4. Алгоритм слияния Разделяй и властвуй.
2.5. Алгоритм полосового слияния
2.5.1. Выбор числа полос для полосовых алгоритмов слияния
2.5.2. Алгоритм выпуклого полосового слияния.
2.5.3. Алгоритм невыпуклого полосового слияния.
2.6. Двухпроходные алгоритмы с откладыванием перестроений.
2.7. Простейший итеративный алгоритм
2.8. Итеративные алгоритмы с ускорением поиска
2.9. Итеративные алгоритмы с изменнным порядком добавления точек в
триангуляцию
2.9.1. Итеративный полосовой алгоритм
2.9.2. Итеративный квадратный алгоритм
2 Итеративные алгоритмы триангуляции с кэшированием.
21. Локализация точки с кэшированием.
22. Алгоритм статического кэширования
23. Алгоритм динамического кэширования.
24. Трудомкость алгоритмов кэширования
2 Суперструктуры для итеративных алгоритмов.
2 Число перестроений в алгоритмах триангуляции
2 Сравнение алгоритмов триангуляции.
2 Выводы
Глава 3. ПРИМЕНЕНИЕ ТРИАНГУЛЯЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ
ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ
3.1. Введение.
3.2. Построение триангуляции с ограничениями
3.3. Классификация треугольников
3.4. Выделение полиполигонов
3.5. Построение буферных зон
3.6. Построение оверлеев
3.7. Построение зон близости
3.8. Построение изолиний и изоконтуров
3.9. Выводы.
Глава 4. ГЛОБАЛЬНЫЕ АЛГОРИТМЫ ПОСТРОЕНИЯ ЛДЕРЕВЬЕВ .
4.1. Введение.
4.2. Алгоритмы работы с Лдеревьями.
4.2.1. Поиск
4.2.2. Вставка
4.2.3. Удаление
4.3. Глобальные алгоритмы
4.4. Алгоритмы разбиения множества объектов на минимально
пересекающиеся группы
4.4.1. Базовый алгоритм
4.4.2. Клеточный алгоритм
4.4.3. Алгоритм Разделяй и властвуй
4.5. Уточнение разбиений.
4.6. Практический анализ глобальных алгоритмов.
4.7. Выводы
Глава 5. УНИВЕРСАЛЬНАЯ ГРАФИЧЕСКАЯ ИНФОРМАЦИОННАЯ
СИСТЕМА ГРАФИН.
5.1. Общая характеристика
5.2. Архитектура системы.
5.3. Структуры данных в системе ГрафИн.
5.4. Менеджер проектов.
5.5. Работа с картами и чертежами
5.6. Визуализация векторных данных.
5.7. Универсальная технология отображения условных знаков
5.8. Модуль цифрового моделирования рельефа
5.9. Подготовка карт к печати
5 Интерфейс прикладного программирования.
5 Сравнение системы ГрафИн с другими система ГИС и САПР
5 Выводы.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА

TIFF, JPEG, фрактальное сжатие [], методы разделения яркостной и хроматической информации YUV [], квадротомические деревья [,1,6,9], и т. Тем не менее, в настоящее время принципиально этот недостаток (громоздкость представления данных) устранить не удаётся. Другим крупным недостатком растровых ГИС является отсутствие структуризации объектов на верхнем уровне, что, как следствие, приводит к высокой трудоёмкости простых операций. Например, для выделения на карте некоторого региона с заданным кодом необходимо полное сканирование всего растра. С другой стороны, достоинством растровых ГИС является органичная возможность выполнения пространственного анализа, включающего построение буферных зон, а также выполнение таких операций алгебры карт, как построение пересечений, объединений, разности, сложения, умножения данных в различных растровых слоях. Эти операции также называют оверлеями [,, ,4]. В векторных ГИС вся информация представляется в виде набора неких элементарных объектов - примитивов. Обычно эти объекты подразделяются на точечные (точки, события), линейные (линии, дуги, кривые), площадные (контуры, полигоны), поверхностные (рельеф). Вся информация представляется в виде графических слоев, на которых представлена однородная графическая информация, объединенная по некоторому общему семантическому признаку (например, карта мира может состоять из слоев городов (точкй), стран (полигонов), рек (линий)). Смешение на слое примитивов разных типов обычно не допускается. По способу описания множества объектов различают два основных векторных формата представления данных: топологический и нетонологический [,,6]. В нетопологическом формате все объекты кодируются независимо друг от друга, при этом изменение параметров любого из объектов (координат или атрибутов) никак не влияет на параметры других [,,1,0,8,5]. При таком представлении происходит дублирование координат смежных объектов (особенно полигонов), в нём трудно отслеживать корректность обрабатываемой информации. В топологическом формате, называемом также линейно-узловым представлением [,,,], выделяется три основных вида объектов: узлы, дуги и полигоны. При этом объектам приписываются характеристики, описывающие топологические отношения между ними. Так, дуги имеют указатели на узлы в своём начале и конце, а также на полигоны слева и справа по ходу движения из начала в конец. Полигоны при этом задаются как совокупность дуг. Обзор векторных форматов представления пространственных объектов приводится в работах [,,,,6,6,9,0], где кроме упомянутых рассматриваются и другие менее распространённые структуры, в частности, гипер-графовые модели [6]. В геоинформационных системах базовыми операциями при просмотре и анализе пространственных отношений графических объектов являются операции регионального поиска и локализации точки. Как правило, эффективность их выполнения определяет оперативность работы системы в целом. Поэтому для работы с большими массивами пространственных данных очень важными являются структуры пространственных индексов, поддерживающие упомянутые задачи поиска и локализации. В вычислительной геометрии существует множество структур [,5], предназначенных для представления и поиска многомерных пространственных объектов. К ним относятся такие структуры, как клеточные разбиения [4,4, 0], квадротомические деревья [,1], к-с! К-Э-В-деревья [6], ре1улярные Опб-файлы [5,3]. В настоящее время наиболее эффективной структурой, позволяющей обрабатывать неточечные объекты и эффективно размещать данные во вторичной памяти, считаются -деревья [3,8], а также ряд их модификаций [2], в частности, упакованные -деревья [8] и Я*-дерсвья [2]. Трудоёмкость поиска объектов внутри заданного региона во многих из перечисленных структур линейно зависит от найденного количества объектов, что является оптимальным с точки зрения поставленной задачи. В большинстве случаев в системах, ориентированных на анализ данных, недостаточно чисто графической информации ддя адекватной обработки и анализа объектов. Для этого необходимы некоторые непространственные качественные и количественные характеристики объектов, хранящиеся в базах данных.

Название работы	Автор	Дата защиты
Разработка и исследование метода автоматического определения дрейфа морских льдов по последовательным спутниковым изображениям	Рахина, Татьяна Владимировна	1999
Численное моделирование крупномасштабной конвекции в протонейтронной звезде при взрыве сверхновой II типа	Устюгов, Сергей Дмитриевич	1999
Математические модели ситуационного управления недропользованием	Ермакова, Анна Николаевна	1999

Электронная библиотека диссертаций

Эффективные алгоритмы вычислительной геометрии и их реализация в геоинформационной системе