Векторное наложение
Наложение векторов — это операция (или класс операций) в географической информационной системе (ГИС) для интеграции двух или более наборов векторных пространственных данных. Такие термины, как наложение полигона , наложение карты и топологическое наложение , часто используются как синонимы, хотя они не идентичны по диапазону операций, которые они включают. Наложение было одним из основных элементов пространственного анализа в ГИС с самого начала его разработки. Некоторые операции наложения, особенно Intersect и Union, реализованы во всех программах ГИС и используются в самых разных аналитических приложениях, тогда как другие встречаются реже.
Наложение основано на фундаментальном принципе географии, известном как площадная интеграция , при котором различные темы (например, климат, топография и сельское хозяйство) можно напрямую сравнивать на основе общего местоположения. Он также основан на математике теории множеств и топологии точечных множеств .
Основной подход операции наложения векторов состоит в том, чтобы взять два или более слоев, состоящих из векторных фигур, и вывести слой, состоящий из новых фигур, созданных на основе топологических связей, обнаруженных между входными фигурами. Ряд конкретных операторов позволяет использовать разные типы входных данных и разные варианты включения в выходные данные.
История [ править ]
До появления ГИС принцип наложения развивался как метод буквального наложения различных тематических карт (обычно изарифмической карты или хорохроматической карты ), нарисованных на прозрачной пленке (например, из ацетата целлюлозы ), чтобы увидеть взаимодействия и найти места с конкретными комбинации характеристик. [1] Техника во многом была разработана ландшафтными архитекторами . Уоррен Мэннинг, по-видимому, использовал этот подход для сравнения аспектов Биллерики, штат Массачусетс , хотя его опубликованные отчеты только воспроизводят карты, не объясняя технику. [2] Жаклин Тирвитт опубликовала инструкции по этой технике в учебнике английского языка в 1950 году, в том числе: [3]
Карты, насколько это возможно, следует чертить на прозрачной бумаге, чтобы после завершения карты одного масштаба можно было «просеять», т. е. поочередно наложить одну на другую, чтобы можно было отметить корреляции или их отсутствие. (стр. 157)
Иэн МакХарг , пожалуй, больше всего ответственен за широкую пропаганду этого подхода к планированию в книге «Дизайн с природой» (1969), в которой он привел несколько примеров проектов, по которым он консультировал, таких как транспортное планирование и сохранение земель . [4]
Первая настоящая ГИС, Канадская географическая информационная система (CGIS), разработанная в 1960-х годах и завершенная в 1971 году, была основана на элементарной модели векторных данных, а одной из самых ранних функций было наложение полигонов. [5] Другая ранняя векторная ГИС, система наложения полигональной информации (PIOS), разработанная ESRI для округа Сан-Диего, штат Калифорния , в 1971 году, также поддерживала наложение полигонов. [6] Он использовал алгоритм «Точка в полигоне» для быстрого поиска пересечений. К сожалению, результаты наложения в этих ранних системах часто были подвержены ошибкам. [7]
Карл Стейниц , ландшафтный архитектор, помог основать Гарвардскую лабораторию компьютерной графики и пространственного анализа , отчасти для разработки ГИС как цифрового инструмента для реализации методов МакХарга. В 1975 году Томас Пойкер и Николас Крисман из Гарвардской лаборатории представили модель данных POLYVRT, одну из первых, которая явно представляет топологические отношения и атрибуты в векторных данных. [8] Они представляли себе систему, которая могла бы обрабатывать несколько «полигональных сетей» (слоев), которые перекрываются путем вычисления наименьших общих географических единиц (LCGU), области, где перекрывается пара полигонов, с атрибутами, унаследованными от исходных полигонов. Крисман и Джеймс Дугеник реализовали эту стратегию в программе WHIRLPOOL, выпущенной в 1979 году в рамках проекта Odyssey по разработке ГИС общего назначения. [9] В этой системе реализовано несколько улучшений по сравнению с предыдущими подходами CGIS и PIOS, и ее алгоритм стал частью ядра программного обеспечения ГИС на десятилетия вперед.
Алгоритм [ править ]
Целью всех операций наложения является использование векторных слоев и создание слоя, который объединяет как геометрию, так и атрибуты входных данных. [10] Обычно оба входных сигнала представляют собой полигональные слои, но во многих операциях допускаются линии и точки с более простой обработкой.
Со времени первоначальной реализации основная стратегия алгоритма наложения полигонов осталась прежней, хотя используемые структуры векторных данных претерпели изменения. [11]
- Учитывая два входных слоя полигонов, извлеките граничные линии.
- Часть A : В каждом слое определите ребра, общие для полигонов. Разорвите каждую линию на стыке общих ребер и удалите дубликаты, чтобы создать набор топологически плоских соединенных линий. В ранних топологических структурах данных, таких как POLYVRT и покрытие ARC/INFO, данные изначально хранились таким образом, поэтому этот шаг был ненужным.
- Взлом, часть B : Найдите любые пересечения между линиями из двух входов. На каждом пересечении разделите обе линии. Затем объедините два слоя линий в один набор топологически плоских соединенных линий.
- Сборка части А : Найдите каждое минимальное замкнутое кольцо линий и используйте его для создания многоугольника. Каждый из них будет наименее распространенной географической единицей (LCGU) с не более чем одним «родительским» полигоном от каждого из двух входных данных.
- Сборка, часть B : Создайте таблицу атрибутов, включающую столбцы из обоих входов. Для каждого LCGU определите его родительский полигон из каждого входного слоя и скопируйте его атрибуты в строку LCGU в новой таблице; если его не было ни в одном из полигонов одного из входных слоев, оставьте значения равными нулю.
Обычно доступны параметры, позволяющие пользователю откалибровать алгоритм для конкретной ситуации. Одним из первых был щелкающий или нечеткий допуск , пороговое расстояние. Любая пара линий, находящихся в пределах этого расстояния друг от друга, сворачивается в одну линию, что позволяет избежать нежелательных узких ленточных многоугольников , которые могут возникнуть, когда линии, которые должны совпадать (например, река и граница, которая должна следовать за ней де-юре ), являются оцифрованы отдельно с немного разными вершинами. [12]
Операторы [ править ]
Базовый алгоритм можно модифицировать разными способами, чтобы получить различные формы интеграции между двумя входными слоями. Эти различные операторы наложения используются для ответа на множество вопросов, хотя некоторые из них реализуются и используются гораздо чаще, чем другие. Наиболее распространенные из них очень похожи на операторы теории множеств и булевой логики и используют их термины. Как и в этих алгебраических системах, операторы наложения могут быть коммутативными (дающими один и тот же результат независимо от порядка) и/или ассоциативными (более двух входных данных дают один и тот же результат независимо от порядка их спаривания).
- Пересечение (ArcGIS, QGIS, Manifold, TNTmips; AND в GRASS): результат включает только те LCGU, где два входных слоя пересекаются (перекрываются); то есть те, у кого есть оба «родителя». Это идентично теоретико-множественному пересечению входных слоев. Пересечение, вероятно, является наиболее часто используемым оператором в этом списке. Коммутативный, ассоциативный
- Объединение (ArcGIS, QGIS, Manifold, TNTmips или в GRASS): результат включает в себя все LCGU, как те, где входные данные пересекаются, так и те, где они не пересекаются. Это идентично теоретико-множественному объединению входных слоев. Коммутативный, ассоциативный
- Вычесть (TNTmips; Стереть в ArcGIS; Разница в QGIS; нет в GRASS; отсутствует в многообразии): результат включает в себя только те части полигонов в одном слое, которые не перекрываются с другим слоем; то есть LCGU, у которых нет родительского элемента из другого уровня. Некоммутативный, неассоциативный
- Исключающее или ( Симметричная разница в ArcGIS, QGIS; Эксклюзивное объединение в TNTmips; XOR в GRASS; отсутствует в многообразии): результат включает в себя части полигонов в обоих слоях, которые не перекрываются; то есть все LCGU, имеющие одного родителя. Этого также можно достичь, вычислив пересечение и объединение, а затем вычитая пересечение из объединения, или вычитая каждый слой из другого, а затем вычисляя объединение двух вычитаний. Коммутативный, ассоциативный
- Вырезать (ArcGIS, QGIS, GRASS, Manifold; Extract Inside в TNTmips): результат включает в себя части полигонов одного слоя, где они пересекают другой слой. Контур такой же, как и пересечение, но внутренняя часть включает только полигоны одного слоя, а не вычисляет LCGU. Некоммутативный, неассоциативный
- Покрытие ( обновление в ArcGIS и Manifold; замена в TNTmips; не в QGIS или GRASS): результат включает в себя один неповрежденный слой, а части полигонов другого слоя только там, где эти два слоя не пересекаются. Это называется «покрытием», потому что результат выглядит так, будто один слой перекрывает другой; в ArcGIS это называется «обновлением», потому что чаще всего оно используется, когда два слоя представляют одну и ту же тему, но один представляет недавние изменения (например, новые участки), которые необходимо заменить более старые в том же месте. Его можно воспроизвести, вычитая один слой из другого, а затем вычисляя объединение этого результата с исходным первым слоем. Некоммутативный, неассоциативный
- Разделить ( Identity в ArcGIS и Manifold; не в QGIS, TNTmips или GRASS): результат включает в себя все LCGU, которые покрывают один из входных слоев, исключая те, которые находятся только в другом слое. Он называется «разделить», потому что он выглядит так, будто один слой используется для разделения полигонов другого слоя. Его можно воспроизвести, вычислив пересечение, затем вычитая один слой из другого, а затем вычисляя объединение этих двух результатов. Некоммутативный, неассоциативный
Булева алгебра наложения [ править ]
Одним из наиболее распространенных применений наложения полигонов является выполнение анализа пригодности , также известного как модель пригодности или многокритериальная оценка. Задача — найти регион, соответствующий набору критериев, каждый из которых может быть представлен регионом. Например, среда обитания вида дикой природы может быть A) в пределах определенных типов растительного покрова, B) в пределах порогового расстояния от источника воды (рассчитанного с использованием буфера ) и C) вне порогового расстояния от основных дорог. . Каждый из критериев можно считать булевым в смысле булевой логики , поскольку для любой точки пространства каждый критерий либо присутствует, либо отсутствует, и точка либо находится в конечной области обитания, либо ее нет (признавая, что критерии может быть расплывчатым, но для этого требуются более сложные методы анализа нечеткой пригодности). То есть не важно, в каком полигоне растительности находится точка, важно только, подходит она или не подходит. Это означает, что критерии могут быть выражены в виде выражения логической логики, в данном случае H = A и B, а не C.
В такой задаче процедуру наложения можно упростить, поскольку отдельные полигоны внутри каждого слоя не важны, и их можно растворить в одной логической области (состоящей из одного или нескольких непересекающихся полигонов, но без соседних полигонов), представляющей область, которая соответствует критерию. С этими входными данными каждый из операторов булевой логики точно соответствует одному из операторов наложения многоугольников: пересечение = И, объединение = ИЛИ, вычитание = И НЕ, исключающее или = XOR. Таким образом, указанный выше регион обитания будет создан путем вычисления пересечения A и B и вычитания C из результата.
Таким образом, это конкретное использование наложения многоугольников можно рассматривать как алгебру гомоморфную , булевой логике . Это позволяет использовать ГИС для решения многих пространственных задач, которые можно свести к простой логике.
Линии и точки [ править ]
Наложение векторов чаще всего выполняется с использованием двух слоев полигонов в качестве входных данных и созданием третьего слоя полигонов. Однако можно выполнить один и тот же алгоритм (по крайней мере, его части) с точками и линиями. [13] В программном обеспечении ГИС обычно поддерживаются следующие операции:
- Пересечение: выходные данные будут того же размера, что и меньшие из входных данных: Точки * {Точки, Линии, Полигоны} = Точки, Линии * {Линии, Полигоны} = Линии. Это часто используется как форма пространственного соединения , поскольку оно объединяет таблицы атрибутов двух слоев, аналогично соединению таблиц. Примером этого может быть распределение учащихся по школьным округам. Поскольку точка редко попадает точно на линию или другую точку, здесь часто используется нечеткий допуск. В QGIS есть отдельные операции для вычисления пересечения линий как линий (для поиска совпадающих линий) и как точек . [14]
- Вычитание: выходные данные будут иметь тот же размер, что и основной вход, при этом слой вычитания будет иметь тот же или меньший размер: Точки — {Точки, Линии, Многоугольники} = Точки, Линии — {Линии, Многоугольники} = Линии.
- Вырез: Хотя основной входной сигнал может представлять собой точки или линии, слой отсечения обычно должен представлять собой полигоны, создавая ту же геометрию, что и основной входной сигнал, но включая только те объекты (или части линий), которые находятся внутри полигонов отсечения. Эту операцию также можно рассматривать как форму пространственного запроса , поскольку она сохраняет особенности одного слоя на основе его топологического отношения к другому.
- Объединение: обычно ожидается, что оба входных слоя будут иметь одинаковую размерность, в результате чего выходной слой будет включать оба набора объектов. ArcGIS и GRASS не поддерживают эту опцию для точек или линий.
Реализации [ править ]
Vector Overlay в той или иной форме включен практически в каждый пакет программного обеспечения ГИС, поддерживающий векторный анализ, хотя интерфейс и базовые алгоритмы значительно различаются.
- Программное обеспечение Esri GIS включает наложение полигонов с момента выхода первого выпуска ARC/INFO в 1982 году. [15] Каждое поколение программного обеспечения Esri (ARC/INFO, ArcGIS, ArcGIS Pro) включает набор отдельных инструментов для каждого из операторов наложения (Intersect, Union, Clip и т. д.). В текущую реализацию ArcGIS Pro недавно добавлен альтернативный набор инструментов « Попарное наложение » (начиная с версии 2.7), который использует параллельную обработку для более эффективной обработки очень больших наборов данных.
- GRASS GIS (с открытым исходным кодом), хотя изначально она была растровой, начиная с GRASS 3.0 (1988 г.), включала наложение как часть своей векторной системы. [16] Большинство операторов наложения полигонов собраны в одну команду v.overlay , а v.clip выделен в отдельную команду.
- QGIS (с открытым исходным кодом) изначально включала GRASS в качестве своего аналитического механизма, но постепенно разработала собственную структуру обработки, включая векторное наложение .
- Manifold System реализует наложение в своей системе трансформации .
- API Turf Javascript включает наиболее распространенные методы наложения, хотя они работают с отдельными входными полигональными объектами, а не со всеми слоями.
- TNTmips включает в себя несколько инструментов для наложения процессов векторного анализа.
Ссылки [ править ]
- ^ Стейниц, Карл; Паркер, Пол; Джордан, Лори (1976). «Нарисованные от руки накладки: их история и перспективное использование». Ландшафтная архитектура . 66 (5 (сентябрь)): 444–455.
- ^ Мэннинг, Уоррен (1913). «План города Биллерика». Ландшафтная архитектура . 3 : 108–118.
- ^ Тирвитт, Жаклин (1950). «Обследования для планирования». В АППР (ред.). Учебник по городскому и дачному планированию . Архитектурная пресса.
- ^ МакХарг, Ян (1969). Дизайн с природой . п. 34. ISBN 0-471-11460-Х .
- ^ Томлинсон, Роджер (1968). «Географическая информационная система для регионального планирования». В Стюарте, Джорджия (ред.). Оценка земли: материалы симпозиума CSIRO . Макмиллан из Австралии. стр. 200–210.
- ^ Томлинсон, Роджер Ф.; Калкинс, Хью В.; Марбл, Дуэйн Ф. (1976). Компьютерная обработка географических данных . ЮНЕСКО Пресс.
- ^ Гудчайлд, Майкл Ф. (1978). «Статистические аспекты проблемы наложения полигонов». Гарвардские статьи по географическим информационным системам . 6 .
- ^ Пойкер, Томас К.; Крисман, Николас (1975). «Картографические структуры данных». Американский картограф . 2 (1): 55–69. дои : 10.1559/152304075784447289 .
- ^ Дугеник, Джеймс (1979). «WHIRLPOOL: геометрический процессор для данных о покрытии полигонов» (PDF) . Труды Международного симпозиума по картографии и информатике (Auto-Carto IV) . 2 : 304–311.
- ^ Болстад, Пол (2008). Основы ГИС: первый текст по географическим информационным системам (3-е изд.). Эйдер Пресс. п. 352.
- ^ Крисман, Николас Р. (2002). Исследование географических информационных систем (2-е изд.). Уайли. стр. 125–137.
- ^ Ло, КП; Юнг, Альберт К.В. (2002). Концепции и методы географических информационных систем . Прентис Холл. п. 211. ИСБН 0-13-080427-4 .
- ^ Эсри. «Пересечение (Анализ)» . Документация ArcGIS Pro . Проверено 29 октября 2021 г.
- ^ QGIS. «Пересечение линий» . Документация QGIS 3.16 .
- ^ Морхаус, Скотт (1985). «ARC/INFO: геореляционная модель пространственной информации» (PDF) . Труды Международного симпозиума по картографии и информатике (Auto-Carto VII) : 388.
- ^ Вестервельт, Джеймс (2004). «Корни ТРАВЫ» (PDF) . Материалы конференции пользователей FOSS/GRASS . Проверено 26 октября 2021 г.
Внешние ссылки [ править ]
- Документация по набору инструментов Overlay в Esri ArcGIS
- Документация по команде v.overlay в GRASS GIS
- Документация по векторному наложению в QGIS
- Документация по наложениям топологии в Manifold