WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 | 5 |

«КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ ГЕОИНФОРМАЦИОННЫХ СИСТЕМ Методические указания Красноярск 2003 3 УДК 528.9(07) М21 М21 ...»

-- [ Страница 1 ] --

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ

ГЕОИНФОРМАЦИОННЫХ СИСТЕМ

Методические указания

Красноярск 2003

3

УДК 528.9(07)

М21

М21 Алгоритмы и структуры данных геоинформационных систем: Методические указания для студентов специальности 071903 – «Геоинформационные системы» / Сост. И.В. Варфоломеев, И.Г. Ермакова, А.С. Савельев. Красноярск: КГТУ, 2003, 34 с.

Печатается по решению редакционно-издательского совета университета © КГТУ, 2003 Печатается в авторской редакции Общие сведения Методические указания подготовлены в соответствии с рабочей программой по курсу «Проектирование геоинформационных систем» для студентов Красноярского Государственного технического университета специальности 071903 – «Геоинформационные системы».

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

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

Методические указания помогут студентам при выполнении лабораторных работ, в которых требуется на некотором языке программирования создать приложения обработки географических данных, сравнимые по функциональности с коммерческими ГИС, например MapInfo.

1. Структуры пространственных данных ГИС 1.1. Хранение растровых данных В геоинформационных системах широко распространена растровая модель данных. Растры применяются для хранения и обработки данных дистанционного зондирования, для представления цифровых моделей рельефа, при визуализации геоданных и т.д. Существует множество вариантов кодирования растровых структур. Некоторые из них более экономно расходуют память, другие позволяют получать более быстрые алгоритмы. Растровая модель соответствует двумерному ячеистому изображению, которое хранится в памяти компьютера в виде одномерной последовательности значений. Растровые изображения обычно разлагаются по строке сверху – слева. Далее будут описаны другие способы эффективного представления растров.

В некоторых форматах графических файлов используется сжатие изображения, основанное на замене длительных последовательностей повторяющихся значений парой значение, количество повторов (рис. 1-а). Географические данные обычно автокоррелированны. В растровой модели это означает, что соседние ячейки имеют большую вероятность быть одинаковыми, чем разобщенные. При обычном порядке сканирования в конце каждой строки происходит скачок на начало следующей строки. Предложим простое изменение порядка сканирования. Нечетные строки будем кодировать слева направо, а четные – в обратном направлении (рис. 1-б). Направление сканирования напоминает движение быка, вспахивающего поле. Отсюда название этого способа сканирования – Boustrophedon (греч. – бык, вспахивающий поле). Теперь при переходе к новой строке первая ячейка является смежной последней ячейке старой строки. Так в линейном разложении растра сохраняется автокорреляция и повышается эффективность кодирования.

A A A A

A A A A A B B B

а)

A B B B A A B B

б)

A A B B A A A B

A A A B AAAA BBBA AABB BAAA 16 байт 4A 3B 3A 3B 3A 8 байт AAAA ABBB AABB AAAB 16 байт 5A 3B 2A 2B 3A 1B 12 байт Рис. 1. Порядки сканирования растров, их линейное разложение и сжатие: а) обычный порядок; б) Boustrophedon.

Порядок сканирования Мортона (назван по имени Гая Мортона, впервые использовавшего этот способ в Canada GIS) основан на иерархическом разбиении карты. В предыдущих способах сканирования учитывалась автокорреляция значений ячеек только по одному направлению (по строке). Географические объекты образуют на растровом изображении пятна. В порядке Мортона предпринимается попытка сканирования ячеек таким образом, чтобы охватить линией обхода эти двумерные пятна.

Для растра размером 2 x 2 применяется обычный порядок сканирования.

На следующем уровне матрица размера 4 x 4 складывается из четырех матриц размера 2 x 2, расположенных в таком же порядке, как ячейки матрицы 2 x 2 (рис. 2). Аналогично формируется линия сканирования любой матрицы порядка 2n. Матрица формируется уровень за уровнем, повторяя один и тот же шаблон размера 2 x 2. При сканировании растра по Мортону линия сканирования представляет собой фрактал. Недостатки сканирования по Мортону очевидны. Во-первых, присутствуют скачки, например, от ячейки 7 к ячейке 8. Во-вторых, таким способом можно кодировать только растры размера, кратного двум.

2 3 10 11 14 15 42 43 46 47 58 59 62 8 9 12 0 1 40 41 44 45 56 57 60 2 3 6 7 34 35 38 39 50 51 54 0 1 4 32 33 36 37 48 49 52

AAAAABBBABAABBAA

Рис. 2. Порядок сканирования растра по Мортону.

Рассмотрим следующий способ сканирования, в котором отсутствуют скачки между ячейками. На рис. 3 ячейки растра сканируется по линии Пеано. Имеется базовый П-образный шаблон, который поворачивается от уровня к уровню так, чтобы обеспечить непрерывность линии сканирования.



При работе с растровыми данными важной является задача определения местоположения ячейки в последовательном файле по растровым координатам и наоборот. Для обычного порядка сканирования и для Boustrophedon – сканирования получение такого отображения не составляет труда. При сканировании по Мортону задача усложняется.

Рассмотрим пример. Пусть требуется по растровым координатам ячейки A(2, 3) определить ее номер в последовательности Мортона. Для этого представим координаты A в двоичной системе счисления и на их основе сформируем число N так, что координаты столбца ячейки A задают нечетные биты N, а координаты строки – четные биты. Получившееся число N=( 1 1 0 1 )2= соответствует позиции ячейки A в последовательности Мортона.

AAAAABBBBBAAABAA

Обратная задача решается похожим способом. Пусть ячейка B записана в десятой позиции последовательности Мортона. Представим ее номер в двоичной системе счисления и разделим четные и нечетные биты между растровыми координатами столбца и строки ячейки: N=10=(1010)2. Получим растровые координаты ячейки A(3, 0).

1.2. Иерархические структуры данных Рассмотренные выше порядки сканирования растровых изображений дают незначительные различия в компрессии данных. Основное преимущество Мортон-сканирования и других иерархических структур данных заключается в более быстром доступе к данным. Информация распределена по карте неравномерно. Увеличение разрешения растрового изображения приводит к увеличению размеров файлов, а уменьшение – к потере информации. Далее пойдет речь об адаптивных методах представления растровых данных с разной плотностью информации.

На рис. 4 изображена растровая матрица размера 16 x 16, в которой содержатся 255 значений “A” и одно “B”. Индексируем растр следующим способом. Разделим матрицу на четыре подматрицы размера 8 x 8 и нумеруем их 0, 1, 2, 3 в порядке Мортона. Назовем подматрицу гомогенной, если в ней содержатся одинаковые значения. Будем рекурсивно разбивать негомогенные подматрицы до тех пор, пока не достигнем гомогенности всех подматриц.

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

Идея выделения гомогенных блоков растра тождественна кодированию растра по Мортону. Гомогенный блок растра размера m x m при сканировании по Мортону соответствует коду m2,A.

Соответствие двумерных растровых координат ячейки и адреса ячейки в последовательном файле похоже на аналогичное преобразование при кодировании растра по Мортону. Единственное отличие в том, что используется система счисления с основанием четыре. В примере на рис. 4 ячейка “B” имеет код 0311. В двоичной системе счисления N=0311=(00110101)2. Разделим биты между растровыми координатами и выясним, что ячейка лежит в четвертой строке и седьмом столбце.

Представленные таким способом растровые данные соответствуют квадродереву, вершина которого – исходное изображение, а листья – гомогенные блоки ячеек. При кодировании квадродеревьев ячейки на каждом уровне могут содержать либо значение гомогенного блока, либо указатель на следующий уровень. Дерево, показанное на рис. 4 может быть представлено в виде линейной последовательности следующим образом.

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

Обозначим n – число уровней квадродерева (тогда размер растра 2n*2n) и через m – число листьев в дереве. Чтобы найти части карты с некоторым значением B, необходимо проверить каждый лист дерева, что потребует m шагов. Определение значения ячейки происходит путем спуска по квадродереву до тех пор, пока не будет получен гомогенный блок. В худшем случае, когда ячейка находится на самой вершине дерева (как, например, ячейка B на рис. 4), поиск займет n шагов. Сравним теперь трудоемкости обеих задач на квадродереве с трудоемкостями этих задач при различных вариантах сканирования растра.

Трудоемкость алгоритмов при различной организации растров.

Структура данных Поиск частей с задан- Определение значения Прим. * – проверяется каждая ячейка матрицы; ** – непосредственное вычисление позиции ячейки; *** – число цепочек примерно соответствует числу листьев; **** – проверяется каждая цепочка.

Существуют различные модификации квадродеревьев, позволяющие, например, эффективно индексировать трехмерные данные (при этом куб рекурсивно делится на восемь частей). При кодировании глобальных данных в проекции Меркатора, представленных в растровой форме, существует проблема различий в форме и размерах ячеек, что приводит к отклонениям в модели. Проблема может быть решена путем представления данных в иерархической форме. Для этого строится глобальная тесселяция: земная поверхность проецируется на октаэдр, содержащий восемь пронумерованных треугольников. Далее каждый треугольник делится на четыре треугольника соединением отрезками середин его сторон. Получившаяся модификация квадродерева позволяет получать разрешение 1 метр при уровне вложенности дерева, равном 20.

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

Чтобы определить площадь ячеек с некоторым значением в растровом слое, необходимо обойти дерево и подсчитать количество ячеек, кодированных этим значением, взвешенное площадью ячейке на данном уровне дерева.

Вычислим, например, на карте 1 (рис. 6) площадь ячеек со значением “A”.

Площадь SA = 1*(Count leaf (00,02,03,32)) + 4*(Count leaf (2)) = 8.



Pages:     || 2 | 3 | 4 | 5 |
 



Похожие работы:

«Препринт # WP/2002/031 Данная статья была выполнена в рамках исследовательского проекта Конкуренция между юриcдикциями в России, являющейся частью исследовательской программы Российские экономические и политические институты в процессе реформ при поддержке фонда Форда и фонда Джона и Кэтрин МакАртуров Москва 2002 Макаров В.Л., Данков А.Н. Межтерриториальная и электоральная конкуренция: сравнительный анализ влияния политических институтов. WP/2002/032. - М.: Российская экономическая школа, 2002....»

«Новости ГПНТБ СО РАН № 4 (октябрь – декабрь) 2007 НОВОСИБИРСК Составитель Е.Б. Соболева Ответственный за выпуск И.А. Гузнер Новости ГПНТБ СО РАН. № 4 (октябрь – декабрь 2007). – Новосибирск. – 2008. – 96 с. – Ежекв. Цель издания – информировать коллектив ГПНТБ СО РАН и библиотечную общественность о важнейших событиях и результатах работы по основным направлениям деятельности различных подразделений Библиотеки. Производственно-практическое издание Новости ГПНТБ СО РАН № 4 (октябрь – декабрь)...»

«Приложение к документации о размещении заказа ПРОЕКТ ДОГОВОРА ДОГОВОР № _ поставки экземпляров Систем КонсультантПлюс и Онлайн Приложения КонсультантПлюс и оказания информационных услуг с использованием экземпляров Систем КонсультантПлюс и Онлайн Приложения КонсультантПлюс г. Москва _ 2014 г. именуемое в дальнейшем Исполнитель, в _, лице, действующего на основании _, с одной стороны, и Российский научный фонд, именуемое в дальнейшем Заказчик, в лице Начальника Административно-технического...»

«Микро-, малые и средние предприятия и глобальный экономический кризис Последствия кризиса и ответные политические меры Пол Ванденберг © Международная организация труда, 2011 Первое издание 2011 Публикации Международного бюро труда охраняются авторским правом в соответствии с Протоколом 2 Всемирной конвенции об авторском праве. Тем не менее краткие выдержки из них могут воспроизводиться без получения разрешения при условии указания источника. Для получения прав на воспроизведение или перевод...»

«Серия Профессора ДИИТа Профессор Фришман Моисей Абрамович ПОД Р ЕД АК Ц ИЕ Й Д -Р А Т ЕХН. Н АУ К, ПР ОФ. В. В. Р ЫБ КИ Н А ИЗД АТ Е ЛЬ СТ В О Д Н Е ПР ОПЕТ Р ОВ С КО ГО Н АЦ ИО Н АЛЬ НО ГО УН ИВ ЕР С ИТ ЕТ А ЖЕ ЛЕЗ НО Д ОР О Ж НО Г О Т Р АН СП ОР Т А ИМЕ НИ АК АД ЕМ ИК А В. Л АЗ АР ЯН А 2013 УДК 625.1:378:001(092) ББК 39.211:74.58г П 84 Печатается по решению ученого совета университета (протокол № 10 от 27.05.2013 г.) П 84 Профессор Фришман Моисей Абрамович [Текст] / под ред. д-ра техн....»

«ДОКУМЕНТАЦИЯ ОБ АУКЦИОНЕ В ЭЛЕКТРОННОЙ ФОРМЕ на право заключения государственного контракта на оказание услуг по печатанию книги для государственных нужд Курганской областной Думы г. Курган 2014 17 февраля 2014 года № ЭА- 1 Извещение о проведении аукциона в электронной форме 1. Способ определения поставщика (подрядчика, исполнителя): аукцион в электронной форме (далее также - электронный аукцион). 2. Наименование и адрес электронной площадки в сети Интернет: автоматизированная система торгов...»

«Eurotherm Technology 50 ES 50 EST 100 ES 100 EST РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ КСКТ 00.00.000-03 РЭ 3 КСКТ 00.00.000-03 РЭ Введение Руководство по эксплуатации (далее – Руководство) является эксплуатационным документом, содержащим информацию по применению, монтажу, эксплуатации аппаратов отопительных газовых бытовых (далее – аппараты) хххES и ххх ESТ, которые разработаны и изготовлены с учётом наиболее современных технических решений, с использованием конструктивных элементов ведущих фирм Чехии,...»

«Принят на заседании Ученого совета 04 апреля 2014г., протокол № 4 ОТЧЕТ О САМООБСЛЕДОВАНИИ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО АВТОНОМНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ Ростов-на-Дону 2014 СОДЕРЖАНИЕ 1. Общие сведения об образовательной организации 1.1 Стратегическая цель и задачи Университета 3 1.2 Система управления 4 1.3 Планируемые результаты деятельности, определенные программой 11 развития 2. Образовательная деятельность 2.1...»

«Приказ МПР РФ от 16 июля 2007 г. N 184 Об утверждении Правил заготовки древесины В соответствии со статьей 29 Лесного кодекса Российской Федерации (Собрание законодательства Российской Федерации, 2006, N 50, ст. 5278) приказываю: Утвердить прилагаемые Правила заготовки древесины. Министр Ю.П. Трутнев Зарегистрировано в Минюсте РФ 22 октября 2007 г. Регистрационный N 10374 Правила заготовки древесины I. Общие положения II. Рубки лесных насаждений и их применение III. Требования к организации и...»

«Акустические дожди. Физматкнига Москва, 2010 1 УДК 551.583 ББК 22.161 Т 82 Тулайкова Т.В. Мищенко А.В., Амирова С.Р. Акустические дожди – Москва, Физматкнига, 2010 г. – 160с. ISBN.589155193 Рецензент – доктор технических наук, Профессор Гринченко С. Н., главный научный сотрудник ИПИ РАН. Избыточное количество парниковых газов в земной атмосфере препятствует естественному охлаждению Земли, как это было в природе сотни и тысячи лет назад. Поэтому, наряду с усилиями по ограничению выбросов...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.