Введение
Глава 1. Иерархические структуры представления графической информации и метод от общего к частному в задачах вычислительной геометрии 18
Глава 2. Алгоритмы решения задач вычислительной геометрии на базе метода от общего к частному 28
2.1. Планарные алгоритмы 28
2.1.1. Вычисление расстояния от точки до кривой на плоскости 28
2.1.2. Поиск кривой из множества, ближайшей к заданной точке 32
2.1.3. Алгоритм поиска ближайшей к заданной кривой точки из множества точек . к 33
2.1.4. Алгоритм определения пересечений луча с кривой 34
2.1.5. Алгоритм определения положения точки относительно
области 36
2.1.6. Вычисление расстояния между кривыми на плоскости 37
2.1.7. Алгоритм определения участков примыкания двух кривых 39
2.1.8. Алгоритм определения участков совпадения и точек пересечения двух кривых 42
2.1.9. Алгоритм определения частей структурированных кривых, попадающих внутрь области 44
2.1.10. Алгоритм определения частей структурированных кривых, попадающих внутрь области, граница которой задана структурированной кривой 45
2.2. Алгоритмы задач вычислительной геометрии в пространстве R3 46
2.2.1. Вычисление расстояния отточки до поверхности 46
2.2.2. Вычисление расстояния между поверхностью и кривой 49
2.2.3. Вычисление расстояния между двумя поверхностями 51
2.2.4. Алгоритм определения пересечений луча с поверхностью 53
2.3. Классификация алгоритмов решения задач ЯГ на базе метода от общего к частному по типу порядка обхода УБРД 54
Глава 3 Оптимизация временных характеристик алгоритмов решения планарных задач вычислительной геометрии на базе иерархических структур представления данных 60
3.1. Метод оптимизации на базе использования сортировки существенных отсчетов верхнего уровня иерархического представления данных 61
3.1.1. Выбор эффективного значения максимальной длины сортируемых отрезков 65
3.2. Метод оптимизации на базе использования фактора множественности 68
3.3. Метод оптимизации на базе использования сетки квадратов 71
3.4. Сравнение эффективности различных методов оптимизации временных характеристик решения задач вычислительной геометрии 76
Глава 4 Использование базовых геометрических алгоритмов в прикладных задачах обработки картографической информации 79
4.1. Алгоритм построения цепочно-узловой (сегментной) модели описания метрической информации картографических объектов 81
4.2. Алгоритм построения поля квадратов (списка окон) объектной области 85
4.3. Алгоритм определения допустимых участков дорожной сети по критерию видимости 89
4.3.1. Определение значения функции F(X, Y) на кусочно-линейных участках маршрута 90
4.3.2. Определение видимости точки поверхности из заданной точки наблюдения 93
Глава 5. Разработка и создание проблемно - ориентированного программного обеспечения для решения задач вычислительной геометрии в ГИС 99
5.1. Комплекс программ для решения задач вычислительной геометрии 106
5.2. Подсистема построения цепочно-узловой (сегментной) модели описания метрической информации графических объектов 108
5.3. Подсистема формирования пространственно - обусловленных связей 111
5.4. Учебно-исследовательская система "Методы и алгоритмы вычислительной геометрии на базе иерархических структур представления графической информации" 114
Заключение 118
Список литературы 121
