СодержаниеСодержание
Содержание 2
1. Введение 2
1.1. Глоссарий 2
1.2. Описание предметной области............................................................2
1.3. Неформальная постановка задачи 3
1.4. Обзор существующих методов решения 3
2. Требования к окружению 4
2.1. Требования к аппаратному обеспечению 4
2.2. Требования к программному обеспечению 4
2.3. Требования к пользователям 4
3. Спецификация данных 4
3.1. Описание формата и структуры данных 4
4. Функциональные требования.................4
5. Требования к интерфейсу 6
6. Проект............................6
6.1. Средства реализации 6
6.2. Модули и алгоритмы 6
6.4. Структуры данных 9
7. Реализация и тестирование 10
Заключение 10
Список литературы 11ВведениеВведение
1.1. Глоссарий
Оверлейные операции – это операции объединения, пересечения и разности геометрических объектов.
Триангуляция – планарное разбиение плоскости на М фигур, из которых одна является внешней бесконечной, а остальные - треугольники.
Построение триангуляции по заданному набору точек – соединение заданных точек непересекающимися отрезками таким образом, чтобы в полученной триангуляции между любыми двумя данными точками нельзя было построить новые отрезки без пересечения с уже существующими.
1.2. Описание предметной области
В настоящее время геоинформационные системы завоевывают все большую популярность в различных областях науки и экономики. ГИС сейчас можно встретить практически в любой сфере деятельности. Геоинформационные технологии предлагают новые эффективные подходы к анализу и решению территориальных проблем, они становятся важным фактором в решении задач социально-экономического, политического и экологического развития и управления природным, производственным и трудовым потенциалом в интересах региона.
Работая с пространственными объектами ГИС, зачастую приходится выполнять геометрические операции. При условии, что библиотеки к ним зачастую платные. И их цена доступна не всем пользователям и разработчикам ГИС. Имеется потребность в библиотеке геометрических операций, не зависящей от конкретной ГИС и которая распространялась бы свободно (бесплатно).
На примере ArcView GIS были изучены доступные геометрические операции. Часть из них решено реализовать в собственной библиотеке. Также изучены алгоритмы вычислительной геометрии, которые приведены на сайте http://algolist.manual.ru ([1]) и http://num-meth.srcc.msu.su ([3], [4]), а также в книге Т. Кормена «Алгоритмы: построение и анализ» ([2]).
Библиотека геометрических операций должна быть реализована на ЯП Delphi. Так как в настоящее время ещё нет подобных программ, написанных на данном ЯП.
1.3. Неформальная постановка задачи
Цель данной работы: разработать и реализовать библиотеку геометрических операций над точечными, линейными и полигональными объектами. Планируется реализовать:
? Стандартные геометрические операции над указанными выше объектами;
? Оверлейные операции, как например пересечение полигональных объектов и т.д.
? Построение триангуляции множества точек, а также триангуляция полигона.
Использовать при этом ЯП Delphi.
Библиотека не должна зависеть от конкретной ГИС, т.е. иметь широкий круг использования. Также должна распространяться бесплатно.
1.4. Обзор существующих методов решения
При подготовке к выполнению данной работы были изучены возможности модуля пространственных операций ArcView GIS, какие действия можно производить в нем над точечными, линейными и полигональными объектами. Данная ГИС, а также все дополнительные модули к ней для пространственного анализа распространяется платно.
Также в Интернете найдено описание других ГИС.
параметры ArcView Gis MapInfo AutoCad GeomLib
операции с точечными, линейными и полигональными объектами + + + +
доступность - - - +/-
открытость - - - +
В связи, с чем имеется необходимость в написании собственного модуля для работы с пространственными данными, такой, чтобы его можно было использовать в любой ГИС и при этом в нем имелось достаточное количество геометрических операций для пользователя данной системы.
2. Требования к окружениюЛитератураСписок литературы
[1] Вычислительная геометрия, .
[2] Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ, 2 – е изд., стереотип.: Пер. с англ. под ред. А. Шеня – М.: МНЦМО: Бином. Лаборатория знаний, 2004. – 960 с.: 263 ил.
[3] Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне, .
[4] Скворцов А.В. Построение объединения, пересечения и разности произвольных многоугольников в среднем за линейное время с помощью триангуляции, < http://num-meth.srcc.msu.su/zhurnal/tom_2002/pdf/art1_8.pdf>.
[5] Ченцов О.В., Скворцов А.В. Обзор алгоритмов построения оверлеев многоугольников,
|
