Исследование методов, разработка алгоритмического и программного обеспечения пространственного анализа графической информации

• Автор: Утешева, Тамара Шатовна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2005
• Место защиты: Нижний Новгород
• Количество страниц: 134 с. : ил.

Содержание
Аннотация
1 Введение
Глава 1. Иерархические структуры представления графической информации и метод от общего к частному в задачах

вычислительной геометрии

Глава 2. Алгоритмы решения задач вычислительной геометрии на

базе метода от общего к частному

2.1. Планарные алгоритмы

2.1.1. Вычисление расстояния от точки до кривой на плоскости

2.1.2. Поиск кривой из множества, ближайшей к заданной точке

2.1.3. Алгоритм поиска ближайшей к заданной кривой точки из

множества точек .к
2.1.4. Алгоритм определения пересечений луча с кривой
2.1.5. Алгоритм определения положения точки относительно
области
2.1.6. Вычисление расстояния между кривыми на плоскости
2.1.7. Алгоритм определения участков примыкания двух кривых
2.1.8. Алгоритм определения участков совпадения и точек пересечения двух кривых
2.1.9. Алгоритм определения частей структурированных кривых, попадающих внутрь области
4 2.1 Алгоритм определения частей структурированных
кривых, попадающих внутрь области, граница которой задана структурированной кривой
2.2. Алгоритмы задач вычислительной геометрии в пространстве Я3
2.2.1. Вычисление расстояния от точки до поверхности
2.2.2. Вычисление расстояния между поверхностью и кривой
2.2.3. Вычисление расстояния между двумя поверхностями
2.2.4. Алгоритм определения пересечений луча с поверхностью 2.3. Классификация алгоритмов решения задач ВГна базе метода от общего к частному по типу порядка обхода УБРД
Глава 3 Оптимизация временных характеристик алгоритмов решения р планарных задач вычислительной геометрии на базе иерархических
структур представления данных
3.1. Метод оптимизации на базе использования сортировки существенных отсчетов верхнего уровня иерархического представления данных
3.1.1. Выбор эффективного значения максимальной длины сортируемых отрезков
3.2. Метод оптимизации на базе использования фактора множественности
3.3. Метод оптимизации на базе использования сетки квадратов
3.4. Сравнение эффективности различных методов оптимизации временных характеристик решения задач вычислительной геометрии
Глава 4 Использование базовых геометрических алгоритмов в прикладных задачах обработки картографической информации
4.1. Алгоритм построения цепочноузловой сегментной модели описания метрической информации картографических объектов
4.2. Алгоритм построения поля квадратов списка окон объектной области
4.3. Алгоритм определения допустимых участков дорожной сети по критерию видимости
4.3.1. Определение значения функции БХ, У на кусочно линейных участках маршрута
4.3.2. Определение видимости точки поверхности из заданной точки наблюдения
Глава 5. Разработка и создание проблемно ориентированного программного обеспечения для решения задач вычислительной геометрии в ГИС
5.1. Комплекс программ для решения задач вычислительной геометрии
5.2. Подсистема построения цепочноузловой сегментной модели описания метрической информации графических объектов
5.3. Подсистема формирования пространственно обусловленных связей
5.4. Учебноисследовательская система Методы и алгоритмы вычислительной геометрии на базе иерархических структур представления графической информации
Заключение
Список литературы


Метод обхода Грэхема состоит в упорядочивании точек множества в соответствии с полярным углом и расстоянием до некоторой внутренней точки множества. При этом выпуклая оболочка точек на плоскости может быть найдена за время при памяти 0Л с использованием только арифметических операций и сравнений. Алгоритм Джарвиса обходит кругом выпуклую оболочку обход Джарвиса, порождая в нужном порядке последовательность крайних точек по одной на каждом шаге. В худшем случае временные затраты алгоритма определяются как 0П2, но он очень эффективен, когда заранее известно, что число вершин выпуклой оболочки Л мало г П. Быстрый метод построения выпуклой оболочки , , , iv имеет временные затраты . Хорошо исследован большой класс задач вычислительной геометрии, который анализирует близость ближайшая пара двух точек, поиск ближайших соседей в окрестности фиксированного радиуса, все ближайшие соседи, к ближайших соседей. При решении задач близости метод простого перебора имеет сложность 1. Применение метода диаграммы Вороного сокращает это время до 0 . Естественным расширением задач о принадлежности и близости является широкий класс задач вычислительной геометрии о пересечении. Одна из важнейших задач машинной графики, которая входит в этот класс это задача удаления невидимых линий и поверхностей. Она привлекала внимание многих исследователей , , , i, , i в связи с потребностями развития САПР, а в настоящее время бурное развитие машинной графики, компьютерных игр, мультимедиа поддерживает этот интерес. Большое количество алгоритмов предложено для. Предметом нашего обзора являются алгоритмы для работы в векторном формате. Основная вычислительная задача при удалении невидимых линий состоит в формировании пересечений двух многоугольников. Простейший случай пересечение выпуклых многоугольников. Одним из наиболее простых алгоритмов для решения этой задачи кроме, разумеется, простого перебора отрезков, который имеет сложность 0 М, где и М количество вершин двух выпуклых многоугольников, является алгоритм Сазерленда Ходжмана. Алгоритм Шеймоса и Хоуи базируется на упорядочивании набора лучей, исходящих из удаленной точки О плоскости и проходящих через вершины многоугольников, по величине угла. Ключевым моментом является то, что пересечение каждого сектора с выпуклым многоугольником образует четырехугольник, а в случае бесконечного удаления точки О, прямоугольник. Поэтому внутри каждого сектора пересечением многоугольников будет пересечение двух четырехугольников, которое можно найти за константное время. Результирующие фрагменты собираются воедино за один проход секторов, а затем требуется еще один очищающий просмотр для удаления ложных вершин, которые возникают на границах между секторами. Доказывается, что сложность этого алгоритма 0 М. В начале обзора существующих методов и алгоритмов рассматривался метод заметания. Он применим для этого класса задач и дает временную сложность вычисления 0. Одним из способов оптимизации алгоритмов решения задач поиска пересечений, и всех задач, которые к ним сводятся является построение ограничивающих тел i V . Вокруг каждого объекта описывается тело достаточно простого вида прямоугольники на плоскости, прямоугольные параллепипеды с ребрами, параллельными осям в трех мерном пространстве. Если эти тела не пересекаются, то и содержащиеся в них объекты не пересекаются. При пересечении описывающих тел поиск пересечений соответствующих объектов ведется обычным образом. Еще одним методом, позволяющим упростить анализ взаимного расположения объектов и использовать когерентност как на плоскости так и в пространстве, является разбиение плоскости пространства i ivii . С этой целью плоскость разбивается на квадраты и для каждой клетки . При неравномерном распределении объектов имеет смысл использовать неравномерное адаптивное разбиение плоскости пространства в случае 3. Стандартными формами таких структур являются восьмеричные, тетрарные и бинарные деревья. Одной из сравнительно простых структур является иерархия ограничивающих тел.