Майкл ДМерс ГИС. Инициаторы проведения этого новаторского события надеются привлечь к нему внимание мировой общественности и широких масс пользователей географических информационных систем из всех стран.
 Скачать 4.47 Mb.
|
|
Глава 4 что вы видите большую группу ячеек растра, представляющую некоторую область. Если вы начнете с одного угла, задав его координаты и значение ячейки, затем перейдете по главным направлениям (вниз, вверх, вправо, влево) вдоль области, записав число, представляющее направление, и еще одно, равное количеству ячеек, на которое вы переместились, то для записи области потребуется всего лишь несколько чисел. Таким образом, вы бы сохранили еще больше места на диске и, конечно, времени ручного ввода. Этот метод называется цепочечным кодированием (raster chain codes), он буквально прокладывает цепь ячеек растра вдоль границы каждой области. В общем, вы указываете координаты (X,Y) начала, значение ячеек для всей области, а затем вектора направлений, показывающие, куда двигаться дальше, где повернуть и как далеко идти. Обычно векторы описываются количеством ячеек и направлением в виде чисел 0,1,2,3, соответствующих движению вверх, вниз, вправо и влево. Есть еще два подхода к сжатию растровой информации, оба ориентированы на квадратные матрицы. Первый, называемый блочным кодированием (block codes), является модификацией группового кодирования. Вместо указания начальной и конечной точек и значения ячеек, мы выбираем квадратную группу ячеек растра и назначаем начальную точку, скажем, центр или угол, берем значение ячейки и сообщаем компьютеру ширину квадрата ячеек. Как видите, это, в сущности, двухмерное групповое кодирование. Таким образом может быть записана каждая квадратная группа ячеек, включая и отдельные ячейки, с минимальным количеством чисел. Конечно, если ваше покрытие имеет очень мало больших квадратных групп ячеек, этот метод не даст значительного выигрыша в объеме памяти. Но в таком случае и групповое кодирование может быть неэффективно, когда есть мало длинных цепочек одной величины. Но все же большинство тематических карт имеют достаточно большое количество таких групп, и блочное кодирование поэтому очень эффективно. Квадродерево (Quadtree), последний рассматриваемый нами метод сжатия растровых данных, несколько сложнее, и ваш преподаватель может посчитать ненужным его освещать. Все же существует по меньшей мере одна коммерческая система компании Tydac под названием SPANS и одна экспериментальная система под названием Quilt [Shaffer, Samet, and Nelson, 1987], которые основаны на этой схеме. Как и блочное кодирование, квадродерево основано на квадратных группах ячеек растра, но в данном случае вся карта последовательно делится на квадраты с одинаковым значением атрибута внутри. Вначале квадрат размером со всю карту делится на четыре квадранта (СЗ, СВ, ЮЗ, ЮВ). Если один из них однороден (т.е. содержит ячейки с одним и тем же значением), то этот квадрант записывается и больше не участвует в делении. Каждый оставшийся квадрант опять делится на четыре квадранта, опять СЗ, СВ, ЮЗ, ЮВ. Опять каждый квадрант проверяется на однородность. Все однородные квадранты записываются, и каждый из оставшихся делится далее и проверяется, пока вся карта не будет записана как множество квадратных групп ячеек, каждая с одинаковым значением атрибута внутри. Мельчайшим квадратом является одна ячейка растра [Burrough, 1983]. Системы, основанные на квадродереве, называются системами с переменным разрешением, так как они могут оперировать на любом уровне деления квадродерева. Пользователи могут решать, какой уровень разрешения нужен для их расчетов. Кроме того, благодаря высокой степени компрессии данных этого метода, в одной системе могут храниться очень большие базы данных - масштаба континента и даже всей Земли. Наибольшей трудностью для квадродерева является метод разделения ячеек растра на регионы, В блочном кодировании решение принимается целиком на основе существования квадратных групп однородности независимо от того, где они находятся на карте. В квадродереве деление на квадранты фиксировано, поэтому некоторые однородные регионы оказываются разбитыми на несколько квадрантов. Это приводит к некоторым трудностям при анализе формы и распределения, которые приходится преодолевать достаточно сложными вычислительными методами, выходящими за рамки данной книги. ГИС, использующие квадродерево, функционируют на рабочих станциях и PC в среде разных операционных систем. Такие программы используются по всему миру и предлагают некоторые интересные возможности, особенно для тех, кто работает с очень большими базами данных. Векторные модели данных Как мы уже видели, векторные структуры данных дают представление географического пространства более интуитивно понятным способом и очевидно больше напоминают хорошо известные бумажные карты. Вы также помните, что они представляют пространственное положение объектов явным образом, храня атрибуты чаще всего в отдельном файле для последующего доступа. Существуют несколько способов объединения векторных структур данных в векторную модель данных, позволяющую нам исследовать взаимосвязи между показателями внутри одного покрытия или между разными покрытиями. Мы рассмотрим их на примере трех основных типов: спагетти-модели, топологической модели и кодирования цепочек векторов. Хотя существуют и другие типы, и многие варианты каждого типа, этих должно вам хватить для обзора того, что имеется для векторных ГИС. Простейшей векторной структурой данных является спагетти-модель [Dangermond, 1982] (Рисунок4.13), которая по сути переводит "один в один" графическое изображение карты. Возможно, она представляется большинством из нас как наиболее естественная или наиболее логичная, в основном потому, что карта реализуется как умозрительная модель. Хотя название звучит несколько странно, оно на самом деле весьма точно по сути. Если представить себе покрытие каждого графического объекта нашей бумажной карты кусочком (одним или несколькими) макарон, то вы получите достаточно точное изображение того, как эта модель работает. Каждый кусочек действует как один примитив: очень короткие—для точек, более длинные - для отрезков прямых, наборы отрезков, соединенных концами, - для границ областей. Каждый примитив - одна логическая запись в компьютере, записанная как строки переменной длины пар координат (X,Y).  Структура данных
Рисунок 4.13. Спагетти-модель векторных данных. Нет явной топологической информации, модель - прямой перевод графического изображения. В этой модели соседние области должны иметь разные цепочки спагетти для общих сторон. То есть, не существует областей, для которых какая-либо цепочка спагетти была бы общей. Каждая сторона каждой области имеет Картографические и геоинформационные структуры данных свой уникальный набор линий и пар координат. Хотя, конечно, общие стороны областей, даже будучи записанными отдельно в компьютере, должны иметь одинаковые наборы координат. Поскольку спагетти-модель выглядит как перевод "один к одному" аналоговой карты, пространственные отношения между объектами (топология), например, такие, как положение смежных областей, -подразумеваются, а не записываются в компьютер в явном виде. И все отношения между всеми объектами должны вычисляться независимо. Результатом отсутствия такого явного описания топологии является огромная дополнительная вычислительная нагрузка, которая затрудняет измерения и анализ. Но так как спагетти-модель очень сильно напоминает бумажную карту, она является эффективным методом картографического отображения и все еще часто используется в компьютеризованной картографии, где анализ не является главной целью. Кроме того, это представление оказывается весьма близким к языку управления многих плоттеров, что упрощает преобразование и повышает его эффективность. Отрисовка на плоттере данных спагетти-модели обычно довольно быстрая по сравнению с другими. В отличие от спагетти-модели, топологические модели [Dangermond, 1982] (Рисунок 4.14), как это следует из названия, содержат топологическую информацию в явном виде. Для поддержки продвинутых аналитических методов нужно внести в компьютер как можно больше явной топологической информации. Подобно тому, как математический сопроцессор объединяет многие специализированные математические операции, так и топологическая модель данных объединяет решения некоторых из наиболее часто используемых в географическом анализе функций. Это обеспечивается включением в структуру данных информации о смежности для устранения необходимости определения ее при выполнении многих операций. Топологическая информация описывается набором узлов и дуг. Узел (node) - больше, чем просто точка, обычно это пересечение двух или более дуг, и его номер используется для ссылки на любую дугу, которой он принадлежит. Каждая дуга (arc) начинается и заканчивается либо в точке пересечения с другой дугой, либо в узле, не принадлежащем другим дугам. Дуги образуются последовательностями отрезков, соединенных промежуточными (формообразующими) точками. В этом случае каждая линия имеет два набора чисел: пары координат промежуточных точек и номера узлов. Кроме того, каждая дуга имеет свой идентификационный номер, который используется для указания того, какие узлы представляет ее начало и конец. Области, ограниченные дугами, также имеют идентифицирующие их коды, которые используются для определения их отношений с дугами. Далее, каждая дуга содержит явную информацию о номерах областей слева и справа от нее, что позволяет находить смежные области. Эта особенность данной модели позволяет компьютеру знать действительные отношения между графическими объектами. Другими словами, мы имеем векторную модель данных, которая лучше отражает то, как мы, пользователи карт, определяем пространственные взаимоотношения, записанные в традиционном картографическом документе.     Рисунок 4.14. Топологическая векторная модель данных. Обратите внимание на включение явной информации о соединении узлов, дуг и областей. Разработаны и применяются несколько топологических моделей данных. Все они немного различаются, и мы посмотрим на некоторые наиболее общие из них с тем, чтобы выяснить, как можно их реализовать. Возможно, наиболее известной является модель GBF/DIME (geographic base file/dual independent map encoding), созданная Бюро переписи США для хранения в компьютере уличной сети, используемой при переписях, проходящих каждые десять лет [U.S. Department of Commerce, Bureau of the Census, 1969] (Рисунок 4.15a). В ней дуги используются для представления улиц, рек, рельсовых путей и т.д. [Peuquet, 1984]. В этой топологической структуре данных каждая дуга заканчивается при смене направления или при пересечении с другой дутой (то есть, не используются промежуточные точки), а узлы идентифицируются кодами. Вдобавок к базовой топологической модели, GBF/DIME присваивает дугам коды направлений в форме пар Начальный узел - Конечный узел. Этот подход упрощает проверку потери узлов (см. Главу 6) при редактировании. Если, например, вы хотите посмотреть, не потерял ли контур полигона какие-либо дуги, просто проверьте совпадение начального узла каждой дуги с конечным узлом предыдущей дуги. Если где-то обнаружится несовпадение, то это значит, что какая-то дута потеряна [Peuquet, 1984]. Дополнительным полезным свойством системы GBF/DIME является то, что для каждой дуги явно определены почтовые адреса и координаты UTM, что обеспечивает доступ к адресам через координаты. Однако, эту модель данных преследует та же проблема, что и базовую топологическую модель и, конечно, спагетти-модель тоже. Поскольку нет определенного порядка, в котором отрезки встречаются в системе, то чтобы найти какой-то конкретный отрезок, программа должна выполнить утомительный последовательный поиск по всей базе данных. А это самый медленный из возможных способов поиска. Более того, GBF/DIME основана на идее теории графов, где не важна форма линии, соединяющей любые две точки. Поэтому сторона многоугольника, используемая для обозначения извилистой границы реки, будет записана не как кривая линия, а как прямая между двумя точками, а результирующая модель не будет иметь графической точности, к которой мы привыкли, общаясь с бумажными картами. Некоторые проблемы GBF/DIME были устранены с разработкой другой системы, TIGER (topologicaly integrated geographic encoding and referencing system) [Marx, 1986], созданной для использования в переписи США 1990 года (Рисунок 4.15Ь). В этой системе точки, линии и области могут адресоваться явно, поэтому участки переписи могут выбираться прямо по номеру участка, а не через информацию о смежности, содержащуюся в связях. Кроме того, так как эта модель не полагается не только на теорию графов, объекты реального мира, такие как извилистые реки и нерегулярная береговая линия отображаются графически более точно [Clarke, 1990]. Поэтому файлы TIGER полезны также и для исследований, не связанных с переписью.    
Рисунок 4.15. Топологические модели данных. Примеры топологических векторных моделей данных: a) GBF/DIME, b) TIGER, с) POLYVRT. Еще одна модель, разработанная Пьюкером и Крисмэном [Peucker and Chrisman, 1975], и реализованная позже в Гарвардской лаборатории компьютерной графики [Peuquet, 1984], называется POLYVRT (POLYgon conVeRTer) (Рисунок 4.15c). Как и TIGER, она устраняет неэффективность хранения и поиска, присущую базовой топологической модели, раздельным хранением каждого типа объектов (точки, линии, области). Эти отдельные объекты затем связываются в иерархическую структуру данных, где точки через указатели связаны с линиями, а линии - с областями. Каждый набор отрезков, называемый в данной модели цепочкой, начинается и заканчивается в определенных узлах (пересечениях двух цепочек). И, как и в GBF/DIME, каждая цепочка содержит явную информацию о направлении в форме "Начальный узел - Конечный узел", а также идентификаторы правых и левых областей (Рисунок 4.15с). Как и TIGER, POLYVRT имеет преимущество отдельного хранения каждого типа объектов: вы можете выбрать точки, линии или области по желанию, идентифицируя их по кодам (которые, конечно, связаны с записями их атрибутов). Поскольку в POLYVRT списки цепочек, окружающие полигоны, хранятся в явном виде и связаны через указатели с каждым полигоном, размер БД определяется в большей степени числом полигонов, нежели сложностью их геометрических форм. Это повышает эффективность хранения и поиска, особенно в случае сложных полигональных форм, встречающихся у многих природных объектов [Peuquet, 1984]. Главный недостаток POLYVRT - это трудность обнаружения неверного указателя для заданного полигона пока он не будет реально выбран, и даже тогда вы должны точно знать, что этот полигон должен представлять. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||