Модель с расширенными измерениями 9-пересечений ( DE-9IM ) - это топологическая модель и стандарт, используемый для описания пространственных отношений двух регионов (две геометрии в двух измерениях , R 2 ), в геометрии , точечной топологии , геопространственной топологии. , и области, связанные с компьютерным пространственным анализом . Пространственные отношения, выраженные моделью, инвариантны к преобразованиям вращения , перемещения и масштабирования .
Матрица обеспечивает подход к классификации геометрических отношений. Грубо говоря, с матрицей истинной / ложной области существует 512 возможных двумерных топологических отношений, которые могут быть сгруппированы в схемы двоичной классификации . Английский язык содержит около 10 схем (отношений), таких как «пересекает», «касается» и «равно». При тестировании двух геометрий по схеме результатом является пространственный предикат, названный схемой.
Модель была разработана Клементини и другими [1] [2] на основе основополагающих работ Эгенхофера и других. [3] [4] Он использовался в качестве основы для стандартов запросов и утверждений в географических информационных системах (ГИС) и пространственных базах данных .
Матричная модель
Модель DE-9IM основана на матрице пересечений 3 × 3 вида:
( 1 )
где это измерение от пересечения (П) от внутренней (I), граница (В), и внешний вид (Е) геометрий и б .
Термины внутренний и граница в этой статье используются в том смысле, который используется в алгебраической топологии и теории многообразий, а не в смысле, используемом в общей топологии: например, внутренность отрезка прямой - это отрезок прямой без его концов, а его граница - это всего лишь две конечные точки (в общей топологии внутренняя часть линейного сегмента на плоскости пуста, а линейный сегмент является его собственной границей).
В обозначениях операторов топологического пространства матричные элементы могут быть также выражены как
- I ( a ) = a o B ( a ) = ∂ a E ( a ) = a e
( 2 )
Размерность пустых множеств (∅) обозначается как -1 или F (ложь). Размерность непустых множеств (¬∅) обозначается максимальным числом измерений пересечения, в частности 0 для точек , 1 для линий , 2 для площадей . Тогда область определения модели { 0 , 1 , 2 , F }.
Упрощенная версия значения получены отображение значений { 0,1,2 } до T (истина), поэтому использование логического домена { Т , F }. Матрица, обозначенная операторами, может быть выражена как
( 3 )
Элементы матрицы могут быть названы, как показано ниже:
( 4 )
Обе матричные формы с размерными и логическими доменами могут быть сериализованы как « строковые коды DE-9IM », которые представляют их в виде однострочного строкового шаблона. С 1999 года строковые коды имеют стандартный формат [5] .
Для проверки вывода или анализа шаблонов значение матрицы (или строковый код) можно проверить с помощью « маски »: желаемого выходного значения с необязательными символами звездочки в качестве подстановочных знаков, то есть " * "указывает выходные позиции, которые не важны для дизайнера (свободные значения или" неважные позиции "). Домен элементов маски: { 0 , 1 , 2 , F , * } или { Т , F , * } для булевой формы.
Более простые модели 4-пересечение и 9-пересечение были предложены до DE-9IM для выражения пространственных отношений [6] (и породили термины 4IM и 9IM ). Их можно использовать вместо DE-9IM для оптимизации вычислений, когда входные условия удовлетворяют определенным ограничениям.
Иллюстрация
Визуально для двух перекрывающихся полигональных геометрий это выглядит так: [7]
| ||||||||||||||||||
|
|
При чтении слева направо и сверху вниз строковый код DE-9IM ( a , b ) выглядит следующим образом: ' 212101212 ', компактное представление.
Пространственные предикаты
Пространственные предикаты - это топологически инвариантные бинарные пространственные отношения, основанные на DE-9IM. Для простоты использования «именованные пространственные предикаты» были определены для некоторых общих отношений.
В пространственных предикатных функциях , которые могут быть получены (выраженные масками) из DE-9IM включают в себя: [4] [8]
Предикаты, определенные с помощью масок домена { Т , F , * }
Имя (синоним) | Матрица пересечения и строка кода маски ( логическое ИЛИ между матрицами) | Значение и определение [4] | Эквивалент | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Равно |
| Внутри & содержит | |||||||||||
T*F**FFF* | |||||||||||||
Непересекающийся |
| не пересекает | |||||||||||
FF*FF**** | |||||||||||||
Прикосновения (встречает) |
| ||||||||||||
FT******* | F**T***** | F***T**** | |||||||||||
Содержит |
| Внутри ( б , а ) | |||||||||||
T*****FF* | |||||||||||||
Охватывает |
| CoveredBy ( b , a ) | |||||||||||
T*****FF* | *T****FF* | ***T**FF* | ****T*FF* |
Предикаты, которые могут быть получены из приведенного выше логическим отрицанием или инверсией параметров ( транспонирование матрицы ), как указано в последнем столбце:
Пересекает | a пересекает b : геометрии a и b имеют по крайней мере одну общую точку. | не непересекающийся | ||||
---|---|---|---|---|---|---|
T******** | *T******* | ***T***** | ****T**** | |||
Внутри (внутри) | a находится внутри b : a лежит внутри b . | Содержит ( b , a ) | ||||
T*F**F*** | ||||||
Покрыта | a покрывается b (расширяется внутри ): геометрия a лежит в b . Другие определения: «По крайней мере, одна точка a лежит в b , и никакая точка a не лежит вне b », или «Каждая точка a является точкой (внутренней или границы) b ». | Обложки ( б , а ) | ||||
T*F**F*** | *TF**F*** | **FT*F*** | **F*TF*** |
Предикаты, использующие входные измерения и определенные с помощью масок домена { 0 , 1 , Т , * }
Кресты или dim (любой) = 1 | a пересекает b : у них есть некоторые, но не все внутренние точки, общие, и размер пересечения меньше, чем размер хотя бы одной из них. Правила выбора маски проверяются только когда, кроме строковых / строковых входов, иначе ложно: [11]
| ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
T*T****** | T*****T** | 0******** dim (любой) = 1 | |||||||||||
Перекрытия | a перекрывается b : у них есть некоторые, но не все общие точки, они имеют одинаковое измерение, а пересечение внутренних частей двух геометрий имеет такое же измерение, как и сами геометрии. Правила выбора маски проверяются только когда, иначе неверно:
| ||||||||||||
T*T***T** dim = 0 или 2 | 1*T***T** dim = 1 |
Заметь:
- Топологически равное определение не означает , что они имеют одни и те же точки , или даже , что они одного и того же класса.
- Выход иметь информацию, содержащуюся в списке всех интерпретируемых предикатов о геометриях a и b .
- Все предикаты вычисляются с помощью масок. Только кресты и перекрытия имеют дополнительные условия о а также .
- Все коды строк маски заканчиваются на
*
. Это потому, что EE тривиально верно и, следовательно, не дает никакой полезной информации. - В Равно маске,
T*F**FFF*
является "слияние" из Содержит (T*****FF*
) и В (T*F**F***
): ( II ∧ ~ Е.И. ∧ ~ ЕВ ) ∧ ( II ∧ ~ И.Е. ∧ ~ BE ) . - Маска
T*****FF*
встречается в определении как Contains, так и Covers . Обложки - это более инклюзивное отношение. В частности, в отличие от Contains, он не различает точки на границе и внутри геометрии. В большинстве случаев лучше использовать Covers, а не Contains . - Точно так же маска
T*F**F***
встречается в определении как Within, так и CoveredBy . В большинстве случаев CoveredBy следует использовать вместо Within .
Характеристики
Пространственные предикаты обладают следующими свойствами бинарных отношений :
- Reflexive : равно, содержит, покрывает, покрыто, пересекает, внутри
- Антирефлексивный : непересекающийся
- Симметричный : равны, пересечения, пересечения, касания, перекрытия.
- Transitive : Equals, Contains, Covers, CoveredBy, Within
Интерпретация
Выбор терминологии и семантики для пространственных предикатов основан на разумных соглашениях и традициях топологических исследований. [4] Такие отношения, как пересечения , непересекающиеся , касания , внутри , равные (между двумя геометриями a и b ) имеют очевидную семантику: [10] [12]
- Равно
- a = b, то есть ( a ∩ b = a ) ∧ ( a ∩ b = b )
- В
- а ∩ б = а
- Пересекает
- а ∩ б ≠ ∅
- Прикосновения
- ( a ∩ b ≠ ∅) ∧ ( a ο ∩ b ο = ∅)
Предикаты Contains и Within имеют тонкие аспекты в своем определении, которые противоречат интуиции. Так , например, [10] линия L , которая полностью содержится в границе многоугольника Р является не рассматривается как содержащаяся в P . Эту причуду можно выразить как «Многоугольники не содержат границ». Эта проблема вызвана последним предложением определения Contains выше: «по крайней мере одна точка внутри B лежит внутри A». В этом случае предикат Covers имеет более интуитивную семантику (см. Определение), избегая рассмотрения границ.
Для лучшего понимания размерность входных данных может использоваться как обоснование для постепенного введения семантической сложности:
Отношения между Соответствующие предикаты Семантика добавлена точка / точка Равные , непересекающиеся Другие допустимые предикаты сворачиваются в Equals . точка / линия добавляет пересечения Intersects - это уточнение Equals : «некоторая равная точка на линии». линия / линия добавляет штрихи , крестики , ... Прикосновения - это уточнение Intersects , касающееся только «границ». Крестики - это «только одно очко».
Покрытие возможных результатов матрицы
Количество возможных результатов в логической матрице 9IM составляет 2 9 = 512, а в матрице DE-9IM - 3 9 = 6561. Процент этих результатов, удовлетворяющих определенному предикату, определяется следующим образом:
Вероятность | Имя |
---|---|
93,7% | Пересекает |
43,8% | Прикосновения |
25% | Кресты (для действительных входных данных, в противном случае 0%) |
23,4% | Обложки и CoveredBy |
12,5% | Содержит , перекрытия (для допустимых входных данных, 0% в противном случае) и внутри |
6,3% | Непересекающийся |
3,1% | Равно |
В обычных приложениях геометрии пересекаются априори , а остальные соотношения проверяются.
Составные предикаты « Пересекаются ИЛИ Непересекаются » и « Равно ИЛИ Разные » имеют сумму 100% (всегда истинные предикаты), но « Covers OR CoveredBy » имеют 41%, что не является суммой, поскольку они не являются логическими дополнениями и независимыми отношениями. ; idem « Содержит ИЛИ внутри », у которых 21%. Сумма 25% + 12,5% = 37,5% получают при игнорировании перекрывающихся линий в « Крестики ИЛИ перекрытий », так как допустимые множества входных сигналов disjoints.
Запросы и утверждения
DE-9IM предлагает полное описательное утверждение о двух входных геометриях. Это математическая функция, которая представляет полный набор всех возможных отношений между двумя объектами, такими как таблица истинности , трехстороннее сравнение , карта Карно или диаграмма Венна . Каждое выходное значение похоже на строку таблицы истинности, которая представляет отношения конкретных входов.
Как показано выше, вывод «212101212», полученный из DE-9IM ( a , b ), представляет собой полное описание всех топологических отношений между конкретными геометриями a и b . Это говорит нам, что.
С другой стороны, если мы проверим такие предикаты, как Intersects ( a , b ) или Touches ( a , b ) - для того же примера мы имеем « Intersects = правда и касания = истина »- это неполное описание« всех топологических отношений ». Предикаты также ничего не говорят о размерности геометрии (не имеет значения, являются ли a и b линиями, областями или точками).
Эта независимость геометрии типа и отсутствие полноты , на предикатах , являются полезными для общих запросов о двух геометрий:
внутренняя / граница / внешняя семантика обычная смысловая Утверждения более информативный
" a и b имеют DE-9IM ( a , b ) = '212101212' "менее информативный
" a Touches b "Запросы более строгий
"Показать все пары геометрий, где DE-9IM ( a , b ) = '212101212' "более общий
"Показать все пары геометрий, где касается ( a , b )"
Для обычных приложений использование пространственных предикатов также оправдано тем, что они более удобочитаемы, чем описания DE-9IM : типичный пользователь лучше интуитивно понимает предикаты (чем набор пересечений внутреннее / граничное / внешнее).
Предикаты имеют полезную семантику в обычных приложениях, поэтому полезно переводить описание DE-9IM в список всех связанных предикатов [13] [14], что похоже на процесс преобразования между двумя разными семантическими типами. Примеры:
- Строковые коды " 0F1F00102 "и" 0F1FF0102 "имеют семантику" пересечения, пересечения и перекрытия ".
- Строковый код " 1FFF0FFF2 "имеют семантику" Равно ".
- Строковые коды " F01FF0102 "," FF10F0102 "," FF1F00102 "," F01FFF102 "и" FF1F0F1F2 »имеют семантику« Пересечения и прикосновения ».
Стандарты
Открытая Геопространственная Консорциум (ОКГ) имеет стандартизированную типичные пространственные предикаты (Содержит, кресты, пересекающие, Штрихи и т.д.) в качестве булевых функций, и модель DE-9IM, [15] , как это функции , которая возвращает строка (знаменатель 9IM code) с доменом { 0 , 1 , 2 , F }, что означает 0 = точка, 1 = линия, 2 = площадь, а F = «пустой набор». Этот строковый код DE-9IM является стандартизированным форматом для обмена данными.
Стандарт Simple Feature Access (ISO 19125) [16] в главе 7.2.8 «Подпрограммы SQL для типа Geometry» рекомендует в качестве поддерживаемых подпрограмм SQL / MM Spatial [17] (ISO 13249-3, часть 3: Spatial) ST_Dimension , ST_GeometryType , ST_IsEmpty , ST_IsSimple , ST_Boundary для всех типов геометрии. Тот же стандарт, соответствующий определениям отношений в «Части 1, Пункт 6.1.2.3» SQL / MM, рекомендует (должны поддерживаться) метки функций: ST_Equals , ST_Disjoint , ST_Intersects , ST_Touches , ST_Crosses , ST_Within , ST_Contains , ST_Overlaps и ST_Relate .
DE-9IM в стандартах OGC использует следующие определения внутренних и границ для основных типов стандартной геометрии OGC: [18]
Подтипы | Тусклый | Интерьер ( I ) | граница ( B ) |
---|---|---|---|
Точка, Многоточечная | 0 | Точка, Точки | Пустой |
LineString, Линия | 1 | Точки, которые остались после удаления граничных точек. | Две конечные точки. |
Линейное кольцо | 1 | Все точки по геометрии. | Пустой. |
MultilineString | 1 | Точки, которые остались после удаления граничных точек. | Те точки, которые находятся в границах нечетного числа его элементов (кривых). |
Многоугольник | 2 | Очки внутри колец. | Набор колец. |
Мультиполигон | 2 | Очки внутри колец. | Набор колец его элементов (многоугольников). |
ВНИМАНИЕ: внешние точки (E) - это точки p, которые не находятся внутри или на границе , поэтому не требуют дополнительной интерпретации, E (p) = not (I (p) или B (p)) . |
Реализация и практическое использование
Большинство пространственных баз данных, такие как PostGIS , реализует патент DE-9IM () модели с помощью стандартных функций: [19] ST_Relate
, ST_Equals
, ST_Intersects
и т.д. Функциональные ST_Relate(a,b)
выходы стандартного OGC в DE-9IM строка кода .
Примеры: две геометрии, a и b , которые пересекаются и соприкасаются с точкой (например, с а также ), может быть ST_Relate(a,b)='FF1F0F1F2'
или ST_Relate(a,b)='FF10F0102'
или ST_Relate(a,b)='FF1F0F1F2'
. Он также удовлетворяет ST_Intersects(a,b)=true
и ST_Touches(a,b)=true
. Когда ST_Relate(a,b)='0FFFFF212'
, возвращаемый код DE-9IM имеет семантику «Пересечения (a, b) & Crosses (a, b) & Within (a, b) & CoveredBy (a, b)», то есть возвращает true
логическое выражение ST_Intersects(a,b) AND ST_Crosses(a,b) AND ST_Within(a,b) AND ST_Coveredby(a,b)
.
Использование ST_Relate () быстрее, чем прямое вычисление набора соответствующих предикатов. [7] Есть случаи, когда использование ST_Relate () является единственным способом , чтобы вычислить комплексный предикат - см примера кода 0FFFFF0F2
, [20] точка , что не «кресты» многоточечные (объект , который представляет собой множество точек), но предикатные Кресты (если она определена по маске) возвращает истину .
Это обычно перегружаютST_Relate () путем добавления параметра маски или использования возвращенного ST_Relate (a, b) строка в Функция ST_RelateMatch () . [21] При использовании ST_Relate (a, b, mask) , возвращает логическое значение. Примеры:
ST_Relate(a,b,'*FF*FF212')
возвращает истину, когдаST_Relate(a,b)
есть0FFFFF212
или01FFFF212
, и возвращает ложь, когда01FFFF122
или0FF1FFFFF
.ST_RelateMatch('0FFFFF212','*FF*FF212')
иST_RelateMatch('01FFFF212','TTF*FF212')
являются правдой ,ST_RelateMatch('01FFFF122','*FF*FF212')
является ложным .
Синонимы
- «Матрица Эгенгофера» является синонимом матрицы логической области 9IM 3x3. [22]
- «Клементини-Матрица» является синонимом матрицы DE-9IM 3x3 { 0 , 1 , 2 , F } домен. [22]
- «Операторы Эгенгофера» и «Операторы Клементини» иногда являются ссылками на элементы матрицы, такие как II , IE и т. Д., Которые могут использоваться в логических операциях. Пример: предикат " G 1 содержит G 2 " может быть выражено " ⟨ G 1 | II ∧ ~ ∧ ~ Е. И. Е. Б. | G 1 ⟩ ", который может быть переведен , чтобы замаскировать синтаксис,
T*****FF*
. - Предикаты «встречает» - это синоним прикосновений ; «внутри» - это синоним « внутри»
- Oracle [14] «ANYINTERACT» является синонимом пересечений, а «OVERLAPBDYINTERSECT» - синонимом перекрытий . Его "OVERLAPBDYDISJOINT" не имеет соответствующего именованного предиката.
- В исчислении соединений региона операторы предлагают несколько синонимов для предикатов : непересекающееся - это DC (отключено), касания - это EC (внешнее соединение), равно - EQ. Другие, такие как перекрытия как PO (частичное перекрытие), нуждаются в анализе или композиции контекста. [23] [24]
Смотрите также
Стандарты:
| Программное обеспечение:
| Похожие темы:
|
Рекомендации
- ^ Клементини, Элисео; Ди Феличе, Паолино; ван Остером, Питер (1993). «Небольшой набор формальных топологических отношений, пригодных для взаимодействия с конечным пользователем». В Авеле, Давид; Ooi, Beng Chin (ред.). Достижения в пространственных базах данных: Третий международный симпозиум, SSD '93, Сингапур, 23–25 июня 1993 г. Материалы . Конспект лекций по информатике. 692/1993. Springer. С. 277–295. DOI : 10.1007 / 3-540-56869-7_16 . ISBN 978-3-540-56869-8.
- ^ Клементини, Элисео; Шарма, Джаянт; Эгенхофер, Макс Дж. (1994). «Моделирование топологических пространственных отношений: стратегии обработки запросов». Компьютеры и графика . 18 (6): 815–822. DOI : 10.1016 / 0097-8493 (94) 90007-8 .
- ^ Egenhofer, MJ; Franzosa, RD (1991). «Точечно-множественные топологические пространственные отношения» . Int. J. GIS . 5 (2): 161–174. DOI : 10.1080 / 02693799108927841 .
- ^ а б в г Egenhofer, MJ; Селедка, младший (1990). «Математическая основа для определения топологических отношений» (PDF) . Архивировано из оригинального (PDF) 14 июня 2010 года. Цитировать журнал требует
|journal=
( помощь ) - ^ « Спецификация простых функций OpenGIS для SQL», версия 1.1 , была выпущена 5 мая 1999 года. Это был первый международный стандарт, устанавливающий соглашения о формате для строковых кодов DE-9IM и имена предикатов «Именованных пространственных отношений». на базе ДЭ-9ИМ »(см. раздел с таким названием).
- ^ МДж Egenhofer, Дж Шарма и D. Марк (1993) « Критическое Сравнение моделей 4-пересечению и 9-пересечения для пространственных отношений: Формальное анализ архивация 2010-06-14 в Wayback Machine », In: Авто -Carto XI. Архивировано 25 сентября 2014 г. в Wayback Machine .
- ^ a b Глава 4. Использование PostGIS: управление данными и запросы
- ^ JTS: Class IntersectionMatrix , Vivid Solutions, Inc., заархивировано из оригинала 21марта2011 г.
- ^ Технические спецификации JTS 2003 г.
- ^ a b c М. Дэвис (2007), « Причуды пространственного предиката « Содержит » ».
- ^ ST_Кресты
- ^ Câmara, G .; Freitas, UM; Казанова, М.А. (1995). «Алгебры полей и объектов для ГИС-операций». CiteSeerX 10.1.1.17.991 . Цитировать журнал требует
|journal=
( помощь ) - ^ DE-9IM переводчик , все связанныхпредикатами пространственного отношения.
- ^ a b Примечание. В пространственной несильно компании Oracle SDO_RELATE (), заархивированная 21.07.2013 на Wayback Machine, выполняет только частичный внутренний перевод, предлагая пользователю маску для проверяемого списка предикатов вместо строки DE-9IM.
- ^ «Спецификация реализации OpenGIS для географической информации - простой доступ к функциям - Часть 2: опция SQL», OGC , http://www.opengeospatial.org/standards/sfs
- ^ Open Geospatial Consortium Inc. (2007), «Стандарт реализации OpenGIS® для географической информации - Простой доступ к функциям - Часть 2: опция SQL», документ OGC 06-104r4 версии 1.2.1 (обзор от 04.08.2010).
- ^ ISO 13249-3 Часть 3: Пространственные, резюмированные в Пакетах мультимедиа и приложений SQL (SQL / MM). Архивировано 14 февраля 2010 г.на Wayback Machine .
- ^ "Энциклопедия ГИС", под редакцией Шаши Шекхар и Хуэй Сюн. SpringerScience 2008. стр. 242
- ^ ST_Relate () Электронная документация по функции PostGIS .
- ^ Тестовый пример JTS «точка A в одной из точек B», http://www.vividsolutions.com/jts/tests/Run1Case4.html Архивировано 4 марта 2016 г. на Wayback Machine.
- ^ ST_RelateMatch () Электронная документация по функции PostGIS .
- ^ a b "Энциклопедия ГИС", С. Шехар, Х. Сюн. ISBN 978-0-387-35975-5 .
- ^ «Расчет многомерной области» (2017), http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf
- ^ «Идентификация отношений в исчислении региональных связей: 9-пересечение, уменьшенное до 3+ -предикатов пересечения» (2013), https://web.archive.org/web/20181001104247/https://pdfs.semanticscholar.org/8184 /abc9b25ed340f9195cc904249bda415bb0c3.pdf
Внешние ссылки
- Теория множества точек и матрица DE-9IM
- Иллюстрированное руководство для DE-9IM