Читать онлайн «Алгоритмы и структуры данных геоинформационных систем: Методические указания для студентов специальности 071903 – «Геоинформационные системы»»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ ГЕОИНФОРМАЦИОННЫХ СИСТЕМ Методические указания Красноярск 2003 3 УДК 528. 9(07) М21 М21 Алгоритмы и структуры данных геоинформационных систем: Методические указания для студентов специальности 071903 – «Геоинформационные системы» / Сост. И. В. Варфоломеев, И. Г. Ермакова, А. С. Савельев. Красноярск: КГТУ, 2003, 34 с. Печатается по решению редакционно-издательского совета университета © КГТУ, 2003 Печатается в авторской редакции 4  Общие сведения Методические указания подготовлены в соответствии с рабочей про- граммой по курсу «Проектирование геоинформационных систем» для сту- дентов Красноярского Государственного технического университета специ- альности 071903 – «Геоинформационные системы». В методических указаниях отражены вопросы моделирования данных в геоинформационных системах, рассматриваются некоторые алгоритмы вы- числительной геометрии. Применение структур данных и алгоритмов пока- зано на примере моделирования поверхностей (рельефа). В этих методических указаниях авторы преследуют две цели. Во- первых, студенты должны не только уметь работать с современным про- граммным обеспечением ГИС, но и понимать, как внутри системы выполня- ется та или иная операция. Во-вторых, проектирование ГИС вовсе не ограни- чено использованием существующего коммерческого программного обеспе- чения. Методические указания помогут студентам при выполнении лаборатор- ных работ, в которых требуется на некотором языке программирования соз- дать приложения обработки географических данных, сравнимые по функ- циональности с коммерческими ГИС, например MapInfo. 5  1. Структуры пространственных данных ГИС 1. 1. Хранение растровых данных В геоинформационных системах широко распространена растровая мо- дель данных. Растры применяются для хранения и обработки данных дистан- ционного зондирования, для представления цифровых моделей рельефа, при визуализации геоданных и т. д. Существует множество вариантов кодирова- ния растровых структур. Некоторые из них более экономно расходуют па- мять, другие позволяют получать более быстрые алгоритмы. Растровая мо- дель соответствует двумерному ячеистому изображению, которое хранится в памяти компьютера в виде одномерной последовательности значений. Рас- тровые изображения обычно разлагаются по строке сверху – слева. Далее бу- дут описаны другие способы эффективного представления растров. В некоторых форматах графических файлов используется сжатие изо- бражения, основанное на замене длительных последовательностей повто- ряющихся значений парой <значение, количество повторов> (рис. 1-а). Гео- графические данные обычно автокоррелированны. В растровой модели это означает, что соседние ячейки имеют большую вероятность быть одинако- выми, чем разобщенные.