По статье Дэвида М. Теобалда, Университет Колорадо,
в журнале ArcUser, апрель-июнь 2001 г.
На вопрос, является ли топология ключевой концепцией ГИС, большинство использующих ГИС утвердительно качают головами. Но если их спросить о том, каким образом топология внедрена в шейп-файлы, они скорее всего, пожмут плечами. Почему ГИС пользователи должны обращать внимание на топологию? Каковы преимущества и недостатки хранения полигональных данных в шейп-файлах, а не в покрытиях? Попробуем разобраться.
Что ест(ь) топология?
В 1736 году математик Леонард Эйлер опубликовал статью, с которой, возможно, началось направление математики, известное как топология. В этой статье Эйлер рассмотрел задачу, названную им «Семь мостов Кёнигсберга» (описание задачи см. ниже). Сравнительно недавно Бюро Переписи США при подготовке к общенациональной переписи населения 1970 года первым применило математическую топологию к картам с целью уменьшить ошибки в массивах данных переписи, сведенных в таблицы. В настоящее время топология в ГИС обычно определяется как пространственные взаимоотношения между смежными или близкорасположенными объектами.
Математическая топология предполагает, что географические объекты располагаются на двухмерной плоскости. В плоском представлении пространственные объекты могут быть представлены с помощью узлов (nodes, 0-мерные ячейки); ребер (edges), иногда называемых дугами (arcs, одномерные ячейки); или полигонов (polygons, двухмерные ячейки). Поскольку объекты могут существовать только на плоскости, пересекающиеся линии разбиваются на отдельные линии, оканчивающиеся узлами, представляющими пересечения, а не простыми вершинами (также называемыми вертексами или формообразующими точками).
В ГИС топология отражается в структуре данных. Например, покрытие ArcInfo представляет собой знакомую многим (корректную) топологическую структуру данных. Покрытие в явном виде содержит топологические отношения между соседними полигонами в таблице AAT (Arc Attribute Table), хранящей идентификационные номера (IDs) смежных полигонов в полях Lpoly (для левого полигона) и Rpoly (для правого полигона). Смежные линии соединяются через узлы, и эта информация хранится в таблице дуг-узлов (arc-node table). CLEAN и BUILD — две фундаментальные команды (операции) ArcInfo, вводящие плоскую топологию в данные и обновляющие топологические таблицы.
За последние два или три десятилетия в ГИС- сообществе установилось единое мнение, что топологические структуры данных более предпочтительны, так как они обеспечивают наиболее логичный (автоматизированный) путь для проведения оцифровки, исправления ошибок и артефактов; сокращают объем хранимых данных по полигонам, поскольку границы между смежными полигонами хранятся один раз (не дублируются); и обеспечивают продвинутый пространственный анализ таких отношений как смежность, связность и включение. Еще одним важным следствием плоского представления является то, что карта с топологией содержит пространственные элементы — неперекрывающиеся полигоны. Следовательно, так называемые картографические (то есть, нетопологические) структуры данных более не используются в основной массе программного ГИС обеспечения.
Явление шейп-файлов
Шейп-файлы появились в ArcView версии 2 в начале 1990-х годов. Шейп-файл — это нетопологическая структура данных, которая не хранит топологические отношения в явном виде. Однако, в отличие от других упрощенных графических структур данных, полигоны в шейп-файле представляются в виде одного или нескольких звеньев (rings). Звено — это замкнутая, не пересекающая сама себя петля. С помощью такой структуры можно представлять сложные (составные) структуры, такие как полигоны, содержащие внутри себя «острова» (пустоты). Вершины звена располагаются (нумеруются) последовательно в направлении по ходу часовой стрелки, при этом область справа по ходу движения вдоль границы звена будет находиться внутри данного полигона, а область слева — вне данного полигона (рис. 1).
Рис. 1. Полигоны в шейп-файле представляются одним или несколькими звеньями, являющимися замкнутыми, не пересекающими сами себя петлями. Вершины звена нумеруются строго по часовой стрелке.
Более того, полигональные объекты в формате шейп-файла могут содержать одну или несколько частей, поэтому могут быть представлены объекты, состоящие из несмыкающихся или перекрывающихся частей. Например, отдельный участок земли, который разделяется дорогой, может быть представлен либо в виде двух отдельных полигонов с помощью двух звеньев и двух записей в таблице атрибутов, либо как один полигон из двух частей с одной записью в таблице атрибутов. По этой причине, часть пользователей может ввести в заблуждение тот факт, что использование некоторых команд ArcView GIS может привести к созданию пространственно разобщенных, состоящих из нескольких частей объектов.
Главным преимуществом шейп-файлов является то, что эта простая структура файлов обеспечивает более быструю прорисовку в сравнении с покрытиями. Возможно, именно поэтому структура данных в виде шейп-файлов была разработана для ArcView GIS — программного обеспечения, первоначально предназначенного скорее для отображения данных, а не для их анализа. Кроме того, шейп-файлы легко скопировать, при этом не нужно их экспортировать, что требуется для файлов формата .e00. Спецификация шейп-файлов доступна, и многие программные продукты поддерживают их. Во многом по этим причинам шейп-файлы стали ведущим стандартом обмена ГИС данными. Однако, эти преимущества не полностью объясняют причины возрождения нетопологической структуры данных.
Топологическое цифрование и редактирование
Одной из основных причин разработки топологии было создание строгого автоматизированного метода исправления ошибок ввода и проверки корректности данных. Типичным методом процедуры цифрования является оцифровка всех линий, построение топологии, задание меток полигонам, исправление недоводов и переводов, выявление висячих дуг и рукавных полигонов, затем новый цикл построения топологии, чистки и так далее, вплоть до достижения приемлемого результата.
Что получится, если этот процесс не был запущен, чтобы упорядочить замысловатую мешанину «картографических спагетти»? Если проводить цифрование с позиций объектного подхода и внедрения плоской топологии, когда проводится оцифровка всех границ объекта и задается его метка, то рукавные полигоны, висячие узлы, объекты с пропущенными метками и объекты с несколькими метками будут убраны. Однако, честно говоря, не всегда имеются в наличии достаточно мощные компьютеры для поддержки подхода, сфокусированного на оцифровке объектов, который требует расчетов геометрии пересечений на лету (хотя подход с оцифровкой в режиме WYSIWYG был разработан уже давно, в 1987 году).
Современные компьютеры достаточно мощны для поддержки сфокусированного на объектах цифрования в задачах, стоящих перед большинством ГИС пользователей. ArcView GIS поддерживает такой подход с помощью инструментов Append Polygon, Split Polygon и Split Line. С их помощью можно добавить полигон (или линию), примыкающий к имеющемуся полигону и получить прекрасное совпадение границ. ArcView GIS также поддерживает редактирование совместных границ или узлов через манипулирование вершинами (рис 2).
Рис. 2. Полигон бреши (gap) удаляется путем слияния с примыкающим полигоном либо путем превращения его в легитимный (законный) полигон. Перекрытия (overlap) обнаруживаются по пересечениям каждого из полигонов со всеми другими полигонами.
Размер файлов больше не проблема
Вторым часто упоминаемым преимуществом топологических структур данных является меньший размер результирующих файлов, поскольку общие вершины или смежные полигоны не хранятся дважды. Теоретически эти файлы должны быть вдвое меньше, чем нетопологические файлы. Однако, на практике шейп-файлы редко бывают вдвое больше по размеру чем те же данные, хранимые в покрытиях, частично потому, что для покрытий необходимы дополнительные файлы для хранения топологической информации. Под таблицы атрибутов часто отводится существенная доля общего размера файлов, но их размер одинаков вне зависимости от того, как хранится геометрия объектов. Более того, хотя размер был важен в прошлом, сейчас средства хранения относительно дешевы, то есть для большинства ГИС пользователей место для хранения данных не является определяющим фактором.
Поиск примыкающих (смежных) объектов
По-видимому, самым распространенным заблуждением относительно шейп-файлов является то, что используя их, нельзя находить смежные объекты, поскольку топология изначально в них не хранится. Однако, смежные объекты могут быть с легкостью обнаружены по пересечению целевых полигонов с другими полигонами на той же карте и идентификации точек пересечения полигонов, которые касаются границ или накладываются на них. Геометрические пересечения смежных объектов рассчитываются на лету путем сравнения вершин смежных объектов, а не путем поиска смежных полигонов в таблице.
Например, для того, чтобы найти все участки, примыкающие к данному участку, надо выбрать этот участок, выбрать опцию “Выбрать темой” из меню “Тема”, указать «пересекают» из ниспадающего окна и щелкнуть на кнопке “Новая выборка”, чтобы выбрать все участки, примыкающие к первоначально выбранному участку. Более сложный анализ смежности (соседства) можно провести, объединяя выборку темой с запросом специфических атрибутов, таким как идентификация только жилых участков, примыкающих к промышленным зонам. Хотя некоторые более сложные типы смежности, которые включают направление (например, поиск смежных участков на восток от заданной дороги), достаточно трудно выявить без создания топологии, подобные варианты анализа применяются не часто и не всегда критически важны для обычных пользователей.
Расчет Списка соседей
Хотя аналитические операции, для проведения которых необходима информация о смежности (соседстве), можно выполнять в ArcView GIS через интерфейс, требования производительности могут вынудить создать таблицу для хранения информации о соседстве (смежности). Через скрипты Avenue можно воспроизвести два описываемых ниже алгоритма построения списков смежных объектов. Хотя представление топологических пространственных отношений традиционно ограничивается строго примыкающими соседями, это ограничение можно обойти, задав поиск примыкающих (смежных) объектов. Понятие смежности можно расширить включением объектов, находящихся в пределах некоторого расстояния (D), а не только строго примыкающих (D=0). Одним из преимуществ создания списков соседей является то, что соседство (примыкание) можно определить с учетом пространственной точности координат, что делает анализ менее чувствительным к рукавным полигонам. С помощью этих алгоритмов можно выявить смежность для полилиний и полигонов. Если D>0, то можно также идентифицировать и смежные (соседние) точки.
Первый алгоритм создает список соседей с использованием так называемого «brute-force» подхода (метод решения « в лоб»). В этом простом алгоритме для каждой пары пространственных объектов определяется, пересекаются ли они, и сохраняются значения индекса смежности. Время расчета пропорционально второй степени количества объектов (N) или кратности O(N2). Однако, вследствие того, что смежность является рефлексивным (возвратным) пространственным отношением, brute-force алгоритм можно изменить для хранения индекса также и по обратным (взаимосвязанным) объектам. Время, необходимое для расчета по модифицированному алгоритму, пропорционально кратности O(N(N-1)/2).
Второй алгоритм использует подход «divide and conquer» (разделяй и властвуй) для рекурсивного подразделения объектов на все более и более мелкие группы. Рефлексивный подход brute-force применяется для этих более мелких групп. Вследствие того, что количество объектов в каждой из групп меньше чем N, общее число тестов на проверку пересечения между двумя объектами значительно уменьшается.
Проверка топологии в шейп-файлах
Шейп-файл с поддержкой плоской топологии может быть создан как описано выше, или получен из покрытия. Однако, если при этом используются нетопологические методы редактирования, то в процессе редактирования шейп-файл может потерять топологические свойства. Плоская топология может быть внедрена в шейп-файл при использовании нескольких скриптов Avenue. Ниже описывается логика предлагаемого алгоритма, а сами скрипты можно скачать с Web сайта ArcUser Online (www.esri.com/news/arcuser/0401/toposcript.txt), или с сайта автора этих скриптов (www.ndis.nrel.colostate.edu/davet).
Первый этап при внедрении плоской топологии в шейп-файлы заключается в удалении спиральных, то есть самопересекающихся звеньев, составляющих полигон, и проверке того, что «внутренность» полигона корректно расположена (находится с нужной стороны) относительно его границы. На следующем этапе проводится идентификация брешей (паразитных полигонов) путем создания прямоугольника, оконтуривающего все нужные полигоны и служащего в качестве фоновой основы. Полигоны вычитаются (вычленяются) из прямоугольника, содержащего все полигоны. Оставшиеся после вычитания области являются брешами. Полигоны брешей удаляются путем их слияния со смежными полигонами или путем их превращения в «законные» полигоны. Перекрытия выявляются по пересечению каждого полигона со всеми полигонами. Если пересечение обнаружено, то создается полигон, представляющий область перекрытия (наложения). Перекрытия можно удалить, удаляя области наложения из одного из перекрывающихся полигонов (рис. 3). После внесения изменений в границы необходимо пересчитать площадь и периметр каждого полигона.
Рис. 3. ArcView GIS поддерживает топологическое редактирование общих границ или узлов за счет манипулирования вершинами, чтобы пользователи могли добавить полигон (или линию), смежную с существующим полигоном, при этом общие границы прекрасным образом совпадают.
Заключение
Стандартное определение топологии в ГИС связано с явным представленим пространственных отношений смежности (соседства) и привлеченим плоского представления географических объектов. Хотя в шейп-файлах топологические отношения не хранятся в явном виде, этот формат представления можно привести в соответствие с требованиями плоского представления. Если в процессе создания или редактирования карт пренебречь требованиями плоского представления, то статистическое суммирование, предполагающее полное заполнение области полигонами, может быть неточным — дать неверные результаты.
Хотя это может прозвучать как ересь для многих пользователей, но есть некоторые преимущества в использовании шейп-файлов, нарушающих принципы плоского представления (то есть шейп-файлов, имеющих бреши и/или перекрытия). Во многих задачах не требуется, чтобы данные имели строгую плоскую топологию, но эти виды анализа никогда не проводятся потому, что априори предполагается, что данные всегда должны быть топологически корректными. Например, городские или районные власти могут быть вынуждены прийти к выводу, что задача создания полноценного покрытия по земельным участкам отнимет слишком много ресурсов и займет длительное время из-за того, что имеющиеся описания границ участков неполны, а описания границ смежных участков не точно соответствуют друг другу. Разрешение несоответствий описаний этих границ и возникающих при этом конфликтов — процесс длительный и непростой, нередко связанный со сложными судебными разбирательствами. Однако, стандартный запрос данных по участку, представленных с приемлемым для многих задач совпадением границ смежных участков (на практике, с точностью около метра), может использоваться для отображения информации о владельцах или арендаторах земельных участков, находящихся в пределах определенного расстояния от заданного места, например с целью их уведомления о каком-то мероприятии, затрагивающим их интересы.
Хотя преимущества, прежде безоговорочно приписываемые только топологически корректным структурам данных, на наш взгляд не всегда очевидны, во многом благодаря резкому повышению производительности компьютеров, главным критерием является необходимость адекватного понимания ГИС- пользователями структуры имеющихся у них или доступных данных.
Об авторе
Дэвид Теобалд является научным сотрудником лаборатории Природных экологических ресурсов Университета штата Колорадо, автор книги «Концепции ГИС и методы ArcView». Эта книга есть в виртуальном магазине ESRI (www.esri.com/gisstore). На персональном Web сайте Теобалда (www.ndis.nrel.colostate.edu/davet) можно узнать больше о нем и выполняемых им исследованиях и проектах.
