автореферат диссертации по информатике, вычислительной технике и управлению, 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. ЭФФЕКТИВНЫЕ АЛГОРИТМЫ ПОСТРОЕНИЯ

ТРИАНГУЛЯЦИИ ДЕЛОНЕ.

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.10. Итеративные алгоритмы триангуляции с кэшированием.

2.10.1. Локализация точки с кэшированием.

2.10.2. Алгоритм статического кэширования.

2.10.3. Алгоритм динамического кэширования.

2.10.4. Трудоёмкость алгоритмов кэширования.

2.11. Суперструктуры для итеративных алгоритмов.

2.12. Число перестроений в алгоритмах триангуляции.

2.13. Сравнение алгоритмов триангуляции.

2.14. Выводы.

Глава 3. ПРИМЕНЕНИЕ ТРИАНГУЛЯЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ

ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ.

3.1. Введение.

3.2. Построение триангуляции с ограничениями.

3.3. Классификация треугольников.

3.4. Выделение полиполигонов.

3.5. Построение буферных зон.

3.6. Построение оверлеев.

3.7. Построение зон близости.

3.8. Построение изолиний и изоконтуров.

3.9. Выводы.

Глава 4. ГЛОБАЛЬНЫЕ АЛГОРИТМЫ ПОСТРОЕНИЯ R-ДЕРЕВЬЕВ

4.1. Введение.

4.2. Алгоритмы работы с R-деревьями.

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.10. Интерфейс прикладного программирования.

5.11. Сравнение системы ГрафИн с другими система ГИС и САПР.

5.12. Выводы.

Геоинформатика и вычислительная геометрия являются в последнее время одними из наиболее развивающихся областей информатики. Их достижения в явном виде используются в двух основных классах программных систем: в геоинформационных ристемах (ГИС) и системах автоматизированного проек-тирования (САПР). До последнего времени эти прикладные направления развивались почти независимо друг от друга, и только в последние годы наметилась тенденция к их сближению и взаимообогащению идеями, принципами функционирования, алгоритмической проработкой. В связи с этим открылся новый пласт практических задач, которые удаётся эффективно решать, используя комбинированные возможности ГИС и САПР. Таким образом, в настоящее время созрела необходимость создания универсальной графической системы, объединяющей потенциальные возможности упомянутых систем.

В данной работе проводится исследование существующих функций ряда отечественных и зарубежных геоинформационных систем и систем автоматизированного проектирования, что позволяет выявить присущие системам обоих классов недостатки и преимущества друг перед другом, выявить ряд нерешённых задач, а также предложить более эффективные способы решения существующих задач, таких как построение цифровой модели рельефа на основе нере гулярного набора отсчётов и выполнение пространственного анализа на плос кости (построение оверлеев, буферных зон, взвешенных зон близости и изокон-туров), используя предлагаемые в работе эффективные алгоритмы построения триангуляции Делоне и триангуляции с ограничениями. Кроме того, в диссертации рассматривается задача регионального поиска, имеющая высокую практическую значимость, а также предлагаются новые эффективные алгоритмы построения структуры R-дерева.

Проектирование и создание универсальной графической системы на базе современных достижений информатики, в частности, геоинформатики, вычислительной геометрии, теории программирования, а также использование для реализации современных программных объектно-ориентированных технологий позволяет охватить потенциально более широкий круг задач, нежели традиционные системы ГИС/САПР, а также в ряде случаев существенно уменьшить стоимость программно-технических решений задач для конечных пользователей. -у

Цель работы заключается в разработке методов повышения эффективности графических информационных систем, исследование возможностей расширения их функций, а также реализации предложенных методов в виде базовой универсальной графической информационной системы. В рамках этой общей задачи требовалось разработать и исследовать базовые алгоритмы двумерного пространственного индексирования объектов с помощью R-деревьев, построения нерегулярной модели рельефа на основе триангуляции, решения задач пространственного анализа на плоскости, в частности, алгоритмы построения триангуляции Делоне, триангуляции с ограничениями, построения оверлеев, буферных зон, взвешенных зон близости и изоконтуров.

Проведённый в первой главе анализ функциональных возможностей ряда отечественных и зарубежных геоинформационных систем и систем автоматизированного проектирования позволил выявить сходные черты двух классов программного обеспечения, а также свойственные им недостатки, наиболее ярко проявляющиеся при решении задач, находящихся на стыке ГИС и САПР. В этой главе исследуются возможности построения универсальной графической информационной среды, интегрирующей функции ГИС и САПР, а также формулируются основные требования к такой системе. Данному вопросу посвящены работы автора [8,10,12,44,45,47,48,49,51,55,57,58,61,63,66,67,68,69,73].

Для существующих реализаций систем ГИС и САПР выявлен ряд узких мест, определяющих, в конечном счёте, эффективность работы системы в целом. Анализ существующих алгоритмов, применимых для решения j^khx задач, показал, что их прямые реализации в современных системах ГИС и САПР даже на самой современной технике не способны удовлетворить многим практическим запросам. Это связано со етишкчш^ольшой трудоёмкостью алгоритмов, не позволяющей решать задачи с большим объёмом входных данных. Одной из таких базовых ^вычислительных задач является построение планарной триангуляции, другая/- региональный поиск графических объектов на плоскости. Теоретическому исследованию этих задач посвящены вторая, третья и четвёртая главы.

Во второй главе исследуется задача построения планарной триангуляции, являющейся базовой в подсистеме моделирования поверхностей любой геоинформационной системы. Наиболее часто для такого моделирования используется триангуляция Делоне, обладающая рядом оптимальных свойств. Одни из лучших известных алгоритмов построения триангуляции Делоне имеют трудол мкость в худшем и среднем 0(N log TV), другие - 0(N ) в худшем и 0{N) в среднем. При этом они имеют, как правило, сложную алгоритмическую реализацию и неудовлетворительное время работы на больших наборах точек. В работе предлагается ряд новых и модификации известных алгоритмов. Лучшие из предложенных алгоритмов имеют трудоёмкость 0{N) в среднем и работают быстрее известных. Эти результаты опубликованы автором в работах [16,52,62, 64].

В третьей главе исследуется возможность применения триангуляции для решения ряда задач пространственного анализа на плоскости, имеющих широкое применение в графических системах. Большинство известных алгоритмов пространственного анализа имеют сложную алгоритмическую реализацию и неудовлетворительное время работы на больших наборах входных данных. В работе предлагается ряд простых, но эффективных алгоритмов, базирующихся на алгоритме построения триангуляции Делоне с ограничениями и предназначенных для построения оверлеев (объединения, пересечения и разности полигонов), буферных зон, взвешенных зон близости и изоконтуров. Эти результаты опубликованы автором в работах [54,60].

В четвёртой главе исследуется практически важная задача регионального поиска объектов в заданном прямоугольном регионе, при этом выявляются недостатки существующих алгоритмов, в частности, предназначенных для построения R-деревьев - наиболее эффективных из существующих структур.

Для практически важного случая построения индексной структуры по заданному набору объектов автором предлагается ряд глобальных алгоритмов построения R-деревьев, позволяющих значительно улучшить эффективность регионального поиска. Данные алгоритмы описаны автором в работах [43,46].

На основе полученных теоретических результатов разработана графическая информационная система ГрафИн, описанная в пятой главе. Структура системы спроектирована с учётом максимальной универсальности и минимальной сложности. В главе рассматриваются базовые архитектурные решения, положенные в её основу, а также основные возможности системы с точки зрения конечного пользователя. Система ГрафИн описана в работах автора [16,17,44, 45,47,48,49,50,53,54,55,59,61,63,66,67,69,71].

Система ГрафИн в настоящее время является коммерческим продуктом, распространяемым на рынке. Система позиционируется как продукт, занимающий промежуточное место между полнофункциональными геоинформационными системами и системами автоматизированного проектирования универсального назначения. В 1998 году выпущена третья версия системы. г

Графическая информационная система ГрафИн находит применение как в научных исследованиях, так и в решении реальных практических задач. Заложенные в неё базовые возможности определяют потенциально широкий класс пользователей (как программистов, так непрограммистов), для решения задач которых недостаточно средств современных программных систем. В тех же случаях, когда реализованных возможностей системы недостаточно, пользователь-программист может сам создавать надстройки для системы, используя для этого интерфейс прикладного программирования.

Работа поддержана грантом РФФИ № 98-07-03194.

Выводы в работе подробно представлены по главам. Здесь мы коснёмся перспектив использования полученных результатов.

Проведённый в первой главе анализ функциональности ряда отечественных и зарубежных геоинформационных систем и систем автоматизированного проектирования позволил выяснить современные тенденции развития графических сред, а также выяснить свойственные им недостатки, часть из которых не могут быть устранены в рамках упомянутых систем. Кроме того, выявлен ряд узких мест этих систем, проработке которых требуется уделить повышенное внимание при разработке новой среды.

В главе сформулированы требования к универсальной графической среде, интегрирующей возможности геоинформационных систем и систем автоматизированного проектирования, а также предложены подходы к её проектированию.

Всё это позволяет при разработке новой графической среды разработчикам ГИС и САПР учесть недостатки существующих систем и обойти их некоторые узкие места.

Полученные во второй главе результаты могут найти применение не "Только при создании подсистем моделирования рельефа геоинформационных систем, но имеют и самостоятельное значение. Так, известно, что ряд задач вычислительной геометрии, такие как построение остовного дерева, построение диаграмм Вороного, поиск всех ближайших соседей, поиск ближайшей пары, построение выпуклой оболочки, имеют линейную по трудоёмкости связь с задачей построения триангуляции Делоне. Известные автору алгоритмы их решения имеют трудоёмкость 0(N log N) в среднем и худшем случае. Используя алгоритм построения триангуляции Делоне с линейной в среднем трудоёмкостью возможно решение перечисленных задач также с линейной сложностью. Эта возможность открывает перспективы нахождения для этих и других задач ещё более специальных, а потому и более эффективных алгоритмов.

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

Полученные в четвёртой главе новые алгоритмы построения индексных структур для эффективного регионального поиска позволяют создавать более быстродействующие графические системы.

Описанная в пятой главе универсальная графическая информационная система ГрафИн позволяет легко расширять свои возможности для решения конкретных прикладных задач.

Геоинформатика сейчас является одной из наиболее быстроразвиваю-щихся областей применения компьютеров, и есть основания полагать, что она получит ещё более широкое распространение. А так как вычислительная геометрия служит основной теоретической базой геоинформатики, то разработка и реализация эффективных алгоритмов для решения её задач имеют несомнен-„ную теоретическую и практическую ценность.

ЗАКЛЮЧЕНИЕ

1. Аронов Б.С. Методы математической обработки геологических данных на ЭВМ. -М.: Недра, 1977. - 184 с.

2. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979.

3. Благодаров А. Обзор САМ-систем. // Компьютер Пресс, №3, М., 1997, с. 22-23.

4. Благодаров А. Системы автоматизированного проектирования высокого уровня. // Компьютер Пресс., №2, М., 1997, с. 14-22.

5. Бочарова И., Попик А. CADdy-архитектура: широкие возможности и простота внедрения. // Компьютер Пресс, спец. выпуск «САПР и графика», М., 1997, с. 30-35.

6. Вирт Н. Алгоритмы + структуры данных = программы: Пер. с англ. -М.: Мир, 1985.-250 с.

7. Ворошко П.П., Петренко О.Н. Полуавтоматическая триангуляция плоской области по заданным узлам. // Алгоритмы и программы по расчёту на прочность., № 7. 1980, с. 123-132.

8. Готман В.И., Скворцов А.В. Система проектирования воздушных распределительных сетей 0,22-35 кВ. // Энергетика: экология, надёжность, безопасность. Томск, 1996, с. 60-61.

9. Готман В.И., Слюсаренко С.Г., Скворцов А.В. Автоматизированный комплекс по выбору и проверке токопроводов в распределительных сетях. // Проблемы и перспективы развития ТНХК. Томск, 1996, с. 88.

10. Готман В.И., Слюсаренко С.Г., Скворцов А.В. Имитационное моделирование режимов систем электроснабжения промышленных предприятий. // Энергетика: экология, надёжность, безопасность. Томск, 1998 (в печати).

11. Готман В.И., Слюсаренко С.Г., Скворцов А.В. Программа выбора аппаратуры, кабелей и защит в сетях 0,4 кВ. // Проблемы и перспективы развития ТНХК. Томск, 1996, с. 89-90.

12. Готман В.И., Слюсаренко С.Г., Субботин С.А., Скворцов А.В. Информационная система коммуникаций промышленных предприятий. // Проблемы и перспективы развития ТНХК. Томск, 1996, с. 90-91.

13. Дейт К. Введение в системы баз данных: Пер. с англ. К.: Диалектика, 1998.-784 с.

14. Дьяконов К.Н., Касимов Н.С., Тикунов B.C. Современные методы географических исследований. М.: Просвещение, 1996. - 207 с.

15. Желтов С.Ю., Инвалев А.С., Кирьяков К.Р., Степанов А.А. Особенности реализации 3D ГИС. // Информационный бюллетень ГИС-ассоциации. № 5(12), 1997, с. 52-53.

16. Жихарев С.А., Скворцов А.В. Моделирование рельефа в системе ГрафИн. // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та, 1998, с. 194-205.

17. Жихарев С.А., Скворцов А.В. Построение графовых структур в ГИС и САПР. // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та, 1998, с. 139-152.

18. Завьялов Ю.С., Квасов Б.И. Методы сплайн-функций. М.: Наука, 1980.-246 с.

19. Ильман В.М. Алгоритмы триангуляции плоских областей по нерегулярным сетям точек. // Алгоритмы и программы, ВИЭМС. Вып. 10 (88).-М., 1985, с. 3-35.

20. Ильман В.М., Лебедев П.В. Пакет подпрограмм триангуляции плоских областей по нерегулярным сетям точек. // Алгоритмы и программы, ВИЭМС. Вып. 10(88). -М., 1985, с 35-57.

21. Ильман В.М. Экстремальные свойства триангуляции Делоне. // Алгоритмы и программы, ВИЭМС. Вып. 10(88). М., 1985, с 57-66.

22. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976.

23. Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. -М.: Мир, 1978.

24. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск. М.: Мир, 1978. - 848 с.

25. Костюк Ю.Л. Применение сплайнов для изображения линий в машинной графике. // Автоматизация эксперимента и машинная графика. -Томск: Изд-во Томск, ун-та, 1977, с. 116-130.

26. Костюк Ю.Л., Грибель В.А. Размещение и отображение на карте точечных объектов. // Методы и средства обработки сложной графической информации (тезисы докладов всесоюзной конференции), часть И. Горький, с. 60-61.

27. Костюк Ю.Л., Фукс А.Л. Построение и аппроксимация изолиний однозначной поверхности, заданной набором исходных точек. // Геоинформатика: Теория и практика. Томск: Изд-во Томск, ун-та, 1998, с. 119-126.

28. Кошкарёв А.В., Каракин В.П. Региональные геоинформационные системы. М.: Наука, 1987, 126 с.

29. Кошкарёв А.В., Тикунов B.C. Геоинформатика. М.: Картгеоиздат-Геодезиздат, 1993, 213 с.

30. Кравцова В.И. Космические методы картографирования. М.: Изд-во МГУ, 1995.-240 с.

31. Кронберг П. Дистанционное изучение Земли: Пер. с нем. М.: Мир, 1988.-343 с.

32. Ласло М. Вычислительная геометрия и компьютерная графика на С++: Пер. с англ. М.: «Издательство БИНОМ», 1997. - 304 с.

33. Леонтович В.В. Вертикальная планировка городских территорий, пособие для вузов. -М.: Высшая школа, 1985. 120с.

34. Линник В.Г. Построение геоинформационных систем в физической географии. М.: Изд-во МГУ, 1990. - 80 с.

35. Лисицкий Д.В. Основные принципы цифрового картографирования местности. М.: Недра, 1988. - 261 с.

36. Мараховский Я.М., Тикунов B.C. Некоторые структуры для представления пространственных данных в географических информационных системах. // Автоматизированная картография и геоинформатика. -М., с. 41-63.

37. Михайлов А.Е., Корчуганова Н.И., Баранов Ю.Б. Дистанционные методы в геологии. М.: Недра, 1993. - 224 с.

38. Основы ГИС: теория и практика. WinGIS руководство пользователя. - М.: Инженерная экология, 1995. - 232 с.

39. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. - 478 с.

40. Роджерс Д., Адаме Дж. Математические основы машинной графики. Пер. с англ. М.: Машиностроение, 1980. - 204 с.

41. Романовский М., Калинин А. Генплан предприятия в CADdy: от планшета до трёхмерной модели. // Компьютер Пресс, спец. выпуск «САПР и графика», М.: 1997, с. 90-95.

42. САПР и Internet. // Компьютер Пресс., №3, М.,1997, с. 36-38.43уСкворцов А.В. Глобальные алгоритмы построения R-деревьев. // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та, 1998, с. 67-83.

43. Скворцов А.В. Графическая интегрированная система ГрафИн. // Наука и образование на защите населения и территории Томской области от чрезвычайных ситуаций. Томск, 1998, с. 20.

44. Скворцов А.В. Графическая интегрированная система ГрафИн. // Томский государственный университет. Научно-технические разработки. Каталог. Томск: Изд-во Томского ЦНТИ, 1998, с. 90.

45. Скворцов А.В. Иерархические R-деревья. // Непараметрика-97 (материалы всероссийской конференции). Красноярск, 1997 (в печати).

46. Скворцов А.В. Интеграция возможностей ГИС и САПР в системе ГрафИн. // Тезисы докладов конференции молодых учёных СФТИ при ТГУ. Томск, 1998, с. 50-51.

47. Скворцов А.В. Информационная система городских коммуникаций. // Муниципальные ГИС-97 (материалы всероссийской конференции). -Обнинск, 1997 (в печати).

48. Скворцов А.В. Информационная система городских коммуникаций. // Энергетика: экология, надёжность, безопасность., г. Томск, 1996, с. 55-56.

49. Скворцов А.В. Моделирование распространения загрязнений окружающей сред средствами ГИС. // Геоинформационные системы в экологии (материалы конференции). Томск, 1998 ( в печати).

50. Скворцов А.В. Новые технологии от ESRI на платформе Windows. // ArcReview, 1997, №3, с. 11.

51. Скворцов А.В. Построение триангуляции Делоне методом кэширования. // Непараметрика-97 (материалы всероссийской конференции). -Красноярск, 1997 (в печати).

52. Скворцов А.В. Прогнозирование схода паводковых вод с помощью геоинформационных систем. // Геоинформационные системы в экологии (материалы конференции). Томск, 1998 ( в печати).

53. Скворцов А.В. Система ГрафИн. // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск. Ун-та, 1998, с. 182-193.

54. Скворцов А.В. Универсальное программное средство для информационных систем электрических сетей. // Современные техника и технологии (труды областной конференции). Томск: Изд-во ТПУ, 1998, с. 24-25.

55. Скворцов А.В. Ускоритель набора программ. // Информатика и образование, 1997, № 2, с. 24.

56. Скворцов А.В., Костюк Ю.Л. Система ГрафИн как пример современной интегрированной ГИС. // Интеркарто-4 (материалы международной конференции). Барнаул, 1998, с. 152-157.

57. Скворцов А.В., Костюк Ю.Л. Сравнительный анализ алгоритмов построения триангуляции Делоне. // SCOR-98 (материалы международной конференции). Новосибирск, 1998, с. 138.

58. Скворцов А.В., Костюк Ю.Л. Универсальная графическая информационная система ГрафИн. // ИНПРИМ-98 (материалы международной конференции), часть V. Новосибирск, 1998, с. 65-66.

59. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне. // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та, 1998, с. 22-47.

60. Скворцов А.В., Лавров В.А. Проектирование воздушных распределительных сетей с использованием цифровых моделей местности. // Энергетика: экология, надёжность, безопасность., г. Томск, 1996, с. 58-59.

61. Скворцов А.В., Слюсаренко С.Г. Информационная система городских коммуникаций. // ИНПРИМ-98 (материалы международной конференции), часть III. -Новосибирск, 1998, с. 71.

62. Скворцов А.В., Слюсаренко С .Г. Кадастр инженерных коммуникаций г. Томска. // Энергетика: экология, надёжность, безопасность. -Томск, 1998 (в печати).

63. Скворцов А.В., Слюсаренко С.Г., Субботин С.А., Кобрин А.Ю. Информационное обеспечение инженерных сетей. // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та, 1998, с. 206-225.

64. Скворцов А.В., Субботин С.А. Универсальная технология отображения условных знаков. // ИНПРИМ-98 (материалы международной конференции), часть V. Новосибирск, 1998, с. 66.

65. Слюсаренко С.Г., Готман В.И., Скворцов А.В. Непрерывный контроль структурной надёжности инженерных сетей. // Энергетика: экология, надёжность, безопасность. Томск, 1998 (в печати).

66. Слюсаренко С.Г., Скворцов А.В, Космомониторинг и моделирование природных и техногенных процессов. // Геоинформационные системы в экологии (материалы конференции). Томск, 1998 (в печати).

67. Слюсаренко С.Г., Скворцов А.В., Субботин С.А., Готман В.И. Ин-формационно-расчётные комплексы как средство повышения надёжности и экономичности систем энергоснабжения. // Энергетика: экология, надёжность, безопасность. Томск, 1996, с. 54-55.

68. Слюсаренко С.Г., Скворцов А.В., Субботин С.А., Готман В.И. Информационная система коммуникаций промышленных предприятий. // Муниципальные ГИС-97 (материалы всероссийской конференции). Обнинск, 1997 (в печати).

69. Тиори Т., Фрай Д. Проектирование структур баз данных: В 2-х книгах. Кн. 1.: Пер. с англ. -М.: Мир, 1985.-287 с.

70. Тиори Т., Фрай Д. Проектирование структур баз данных: В 2-х книгах. Кн. 2.: Пер. с англ. М.: Мир, 1985. - 320 с.

71. Фукс A.JL Изображение изолиний и разрезов поверхности, заданной нерегулярной системой отсчётов. // Программирование, № 4, М., 1986, с. 87-91.

72. Хаксхолд В. Введение в городские информационные системы: Пер с англ. М.: Русское издательство АГИТ, 1996. - 325 с.

73. Цветков В Л. Геоинформационные системы и технологии. М.: Финансы и статистика, 1998.-288с.

74. Цикритзис Д., Лоховски Ф. Модели данных. М.: Финансы и статистика, 1985.-343 с.

75. Цифровая обработка телевизионных и компьютерных изображений. / Под ред. Ю.Б. Зубарева, В.П. Дворкина. М.: МЦНТИ, 1997. - 216 с.

76. Шикин Е.В., Плис Л.И. Кривые и поверхности на экране компьютера. Руководство по сплайнам для пользователей. М.: ДИАЛОГ-МИФИ, 1996.-240 с.

77. Akima Н. A method of bivariate interpolation and smooth surface fitting for irregularly distributed data points // ACM Trans, for Math. Software. -1978, No. 4, pp. 148-159.

78. Allgower E., Quesenberry N. Automatic Triangulations of Bounded Regions in I2. // Z. Angew. Math, und Mech., Vol. 62, No. 5, 1982, pp. 314-316.

79. ARC/INFO User's Guide: Address Geocoding. Environmental Systems Research Institute. Inc., NY, 1992. 155 p.

80. ARC/INFO User's Guide: ARC/INFO Data Model, Concepts, & Key Terms. Environmental Systems Research Institute. Inc., NY, 1992. 298 p.

81. ARC/INFO User's Guide: Cell-based Modeling with GRID. Environmental Systems Research Institute. Inc., NY, 1992. 305 p.

82. ARC/INFO User's Guide: Map Display & Query. Environmental Systems Research Institute. Inc., NY, 1992. 345 p.

83. ARC/INFO User's Guide: Network Analysis. Environmental Systems Research Institute. Inc., NY, 1992. 317 p.

84. ARC/INFO User's Guide: Surface Modeling With TIN. Environmental Systems Research Institute. Inc., NY, 1992. 240 p.

85. ARC/INFO User's Guide: Understanding GIS The ARC/INFO Method. Environmental Systems Research Institute. Inc., NY, 1997. - 510 p.

86. ArcCAD Programmer's Guide. Environmental Systems Research Institute. Inc., NY, 1992.-384 p.

87. ArcCAD User's Guide. Environmental Systems Research Institute. Inc., NY, 1992.-256 p.

88. ArcView GIS. Environmental Systems Research Institute. Inc., NY, 1997. -350 p.

89. ArcView Network Analyst. Environmental Systems Research Institute. Inc., NY, 1996.-74 p.

90. ArcView Spatial Analyst. Environmental Systems Research Institute. Inc., NY, 1996.- 150 p.

91. ArcView 3D Analyst. Environmental Systems Research Institute. Inc., NY, 1996.- 163 p.

92. ArcView User's Guide. Environmental Systems Research Institute. Inc., NY, 1992.- 192 p.

93. A technical introduction to Digital Video. Pub. John Wiley & Sons, Inc. ISBN 0-471-12253-X.

94. AutoCAD 14: User's Guide. Autodesk. Inc., 1997. 874 p.

95. AutoCAD Data Extension (ADE): User's Guide. Autodesk. Inc., 1993.-234 p.

96. AutoCAD Map 2: User's Guide. Autodesk. Inc., 1997. 624 p.

97. Beckmann N., Kriegel H., Schneider R., Seeger B. The R* tree: An Efficient and Robust Access Method for Points and Rectangles. // ACM, 1990, pp. 322-331.

98. Bentley J. Multidimensional Binaiy Search Trees Used for Associative Searching. // Communications of the ACM, Vol. 18, No. 9, 1975, pp. 509-517.

99. Bentley J., Stanat D., Williams E. The complexity of fixed-radius near neighbor searching. // Inf. Proc., Vol. 6, No. 6, 1977, pp. 209-212.

100. Bentley J., Friedman J. Data Structures for Range Searching. // Computing Surveys, Vol. 11, No. 2, 1979, pp. 121-138.

101. Bouille F. Cartographie thematique informatique. Applications. // Bol. Soc. geogr. Lisboa, Vol. 96, No 1, 1978, pp. 5-54.

102. CADdy 12.0. Руководство пользователя. Ziegler Informatics. 1997. -298 c.

103. Delaunay B. Sur la sphere vide. // Изв. АН СССР, OMEH, 1934, № 4, c. 793-800.

104. ERDAS Field Guide. ERDAS. Inc. 1997. 672 p.

105. ESRI Shapefile: A Technical Description. Environmental Systems Research Institute. Inc., USA, 1997. - 23 p.

106. Finkel R., Bentley J. Quad Trees A Data Structure for Retrieval on Composite Keys. // Acta Informatica, Vol. 4, 1974, pp. 1-9.

107. Greene D. An Implementation and Performance Analysis of Spatial Data Access Methods. // Proc. 5th. Int. Conf. On Data Engineering, 1989, pp. 606-615.

108. Guttmann A. R-trees: A Dynamic Index Structure For Spatial Searching. // Proc. ACM SIGMOD Int. Conf. on Management of Data, 1984, pp. 47-57.

109. Guttmann A., Stonebraker M. Using a Relational Database Management System for Computer Aided Design Data. // IEEE Database Engineering, Vol. 5, No. 2, 1982.

110. Hinrichs K., Nievergelt J. The Grid File: A Data Structure Designed to Support Proximity Queries on Spatial Objects. // Institute fur Informatik, Eidgenossische Technische Hochschule, Zurich, Nr. 54, July, 1985,

111. Keinz W. A classification of digital map data models. EURO-CARTO VI, Proc., 1987, pp. 105-113.

112. Kirkpatrick D. A note on Delaunay and optimal triangulations. // Inf. Proc. Lett., 1980, Vol. 10, No. 3, pp.127-128.

113. Kriegel H., Schiwietz M., Schneider R. Seeger B. Performance comparison of point and spatial access methods. // Proc. Symp. On the Design and Implementation of Large Spatial Databases, Santa Barbara, 1989, Lecture Notes in Computer Science.

114. Larsson G. Land Registration And Cadastral Systems. NY, 1991. 175 p.

115. Lawson C. Software for C1 surface interpolation. // Mathematical Software III. -NY: Academic Press, 1977, pp.161-194.

116. Lawson C. Transforming triangulations.// Discrete Mathematics, No. 3, North-Holland Publishing Company, 1972, pp. 365-372.

117. Lee D., Schachter B. Two algorithms for constructing a Delaunay trian-gulation. // Int. Jour. Сотр. and Inf. Sc., 1980, Vol. 9, No. 3, pp. 219-242.

118. Lee D. Proximity and reachability in the plane, Tech. Rep. No. R-831, Coordinated Sci. Lab., Univ. Of Illinois at Urbana, IL, 1978.

119. Lewis В., Robinson J. Triangulation of planar regions with applications. // The Computer Journal, 1978, Vol. 21, No. 4, pp. 324-332.

120. Lingas A. The Greedy and Delaunay triangulations are not bad. // Lect. Notes Сотр. Sc., 1983, Vol. 158, pp. 270-284.

121. Lloyd E. On triangulation of a set of points in the plain. MIT La. Сотр. Sc. Tech. Memo., No. 88, 1977. 56 p.

122. Manacher G., Zobrist A. Neither the Greedy nor the Delaunay triangulation of planar point set approximates the optimal triangulation. // Inf. Proc. Lett., Vol. 9, No. 1, 1977, pp.31-34.

123. Maplnfo User's Guide. Maplnfo Corp. 1995. 252 p.

124. Margalit A., Knott G.D. An algorithm for computing the union, intersection or difference of two polygons. Comput. & Graphics, Vol. 13, No. 2, 1989, pp. 167-183.

125. Microstation 95 User's Guide. Bentley Systems. Inc. 1997. 358 p.

126. Monmonier Mark. Computer-assisted cartography (principles and prospects). Prentice-Hall, Inc., Englewood Cliffs, 1982.

127. Nelson J. A triangulation algorithm for arbitrary planar domains. // App. Math. Modeling, Vol. 2, September, 1978, pp. 151-159.

128. Nievergelt J., Hinterberger H., Sevcik K. The grid file: an adaptable, symmetric multikey file structure. // ACM Trans. On Database Systems, Vol. 9, No. 1, 1984, pp. 38-71.

129. Overlay Training Workbook: Spatial Manipulation and Analysis. Environmental Systems Research Institute. Inc., NY, 1991. 275 p.

130. Oxley A. Surface fitting by triangulation. // Computer Journal, Vol. 28, No. 3, 1985, pp. 243-245.

131. Robinson J. The K-D-B Tree: A Search Structure for Large Multidimensional Dynamic Indexes. // ACM-SIGMOD Conf. Proc. April, 1981, pp. 10-18.

132. Rosenberg J. Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries. // IEEE Trans. Computer-Aided Design, vol. CAD-4, No. 1, Jan., 1985, pp. 53-67.

133. Roussopoulos N., Leifker D. Direct spatial search on pictorial databases using packed R-trees. // Proc. ACM SIGMOD Int. Conf. On Management of Data, 1985, pp. 17-31.

134. Samet H. The quadtree and related hierarchical data structures. // ACM Computing Surveys, Vol. 16, No. 2, 1984, pp. 187-260.

135. Samet H. Applications of spatial data structures. Computer graphics, image processing and GIS. Addison-Wesley Pub. Com., 1990. - 507 p.

136. Schwarz C.R. Algorithms for constructing lines separated by a fixed distance. Int. Symp. Of Spatial Data Handling, Second, USA, NY, 1986, pp. 510-522.

137. Shapiro M. A note on Lee and Schachter's algorithm for Delaunay triangulation. // Inter. Jour. Of Сотр. and Inf. Sciences, Vol. 10, No. 6, 1981, pp. 413-418.

138. Sibson R. Locally equiangular triangulations. // Computer Journal, Vol. 21, No. 3, 1978, pp. 243-245.

139. Sloan S., Houlsby G., An implementation of Watson's algorithm for computing 2-dimensional Delaunay triangulations. // Adv. Eng. Software, Vol.6, No. 4, 1984, pp. 192-197.

140. Spatial Database Engine 2,1: Developer's Guide. Environmental Systems Research Institute. Inc., NY, 1996. 425 p.

141. Tanimoto S., Pavlidis T. A hierarchical data structure for picture processing. Computer Graphics and Image Processing. Vol. 4, No 2, 1975, pp. 104-119.

142. Teng А.Т., Joseph S.A., Shojaee A.R. Polygon overlay processing: a comparision of pure geometric manipulation and topological overlay processing. Int. Symp. Of Spatial Data Handling, Second, USA, NY, 1986, pp. 102-119.

143. Terry A. Walsh. A technique for high performance data compression. IEEE Computer, vol. 17, No 6, 1984.

144. Toussaint G. Pattern recognition and geometrical complexity. // Proc. 5th Int. Conf. of Patt. Recogn, Miami Beach, 1980, pp. 1324-1247.

145. Yuval G. Finding Near Neighbors in k-dimensional Space. // Inf. Proc. Lett., Vol. 3, No. 4, 1975, pp. 113-114.