ДЭ-9ИМ - DE-9IM

В Размерно расширенная модель с 9 пересечениями (ДЭ-9ИМ) это топологический модель и стандарт используется для описания пространственные отношения двух регионов (два геометрии в двух измерениях, р²), в геометрия, точечная топология, геопространственная топология, и поля, связанные с компьютерный пространственный анализ. Пространственные отношения, выражаемые моделью, инвариантны к вращение, перевод и масштабирование трансформации.

Матрица обеспечивает подход к классификации геометрических отношений. Грубо говоря, для области матрицы истинно / ложно существует 512 возможных двумерных топологических отношений, которые можно сгруппировать в схемы двоичной классификации. Английский язык содержит около 10 схем (отношений), таких как «пересекает», «касается» и «равно». При тестировании двух геометрий по схеме результат пространственный предикат названные по схеме.

Модель разработана Клементини и другими.^[1][2] на основе основополагающих работ Эгенхофера и других.^[3][4] Он был использован в качестве основы для стандартов запросы и утверждения в географические информационные системы (ГИС) и пространственные базы данных.

Матричная модель

В ДЭ-9ИМ Модель построена на базе 3х3 пересечение матрица с формой:

${\displaystyle \operatorname {DE9IM} (a,b)={\begin{bmatrix}\dim(I(a)\cap I(b))&\dim(I(a)\cap B(b))&\dim(I(a)\cap E(b))\\\dim(B(a)\cap I(b))&\dim(B(a)\cap B(b))&\dim(B(a)\cap E(b))\\\dim(E(a)\cap I(b))&\dim(E(a)\cap B(b))&\dim(E(a)\cap E(b))\end{bmatrix}}}$

(1)

куда ${\displaystyle \dim }$ это измерение из пересечение (∩) из интерьер (Я), граница (Группа внешний вид (E) геометрий а и б.

Условия интерьер и граница в этой статье используются в том смысле, который используется в алгебраической топологии и теории многообразий, а не в смысле, используемом в общей топологии: например, внутренняя часть отрезка прямой - это отрезок без его концов, а его граница - это только две конечные точки. (в общей топологии внутренняя часть линейного сегмента на плоскости пуста, а линейный сегмент является его собственной границей).

В обозначениях операторов топологического пространства матричные элементы могут быть также выражены как

я(а)=а^о    B(а)=∂а    E(а)=ае

(2)

Размер пустые наборы (∅) обозначаются как −1 или F (ложный). Размерность непустых множеств (¬∅) обозначается максимальным числом измерений пересечения, в частности 0 за точки, 1 за линии, 2 за области. Затем домен модели {0,1,2,F}.

Упрощенная версия ${\displaystyle \dim(x)}$ значения получены отображение значений {0,1,2} к Т (true), поэтому использование логический домен {Т,F}. Матрица, обозначенная операторами, может быть выражена как

${\displaystyle \operatorname {bin} (\operatorname {DE9IM} (a,b))=\operatorname {9IM} (a,b)={\begin{bmatrix}a^{o}\cap b^{o}\neq \emptyset &a^{o}\cap \partial {b}\neq \emptyset &a^{o}\cap b^{e}\neq \emptyset \\\partial {a}\cap b^{o}\neq \emptyset &\partial {a}\cap \partial {b}\neq \emptyset &\partial {a}\cap b^{e}\neq \emptyset \\a^{e}\cap b^{o}\neq \emptyset &a^{e}\cap \partial {b}\neq \emptyset &a^{e}\cap b^{e}\neq \emptyset \end{bmatrix}}}$

(3)

Элементы матрицы могут быть названы, как показано ниже:

${\displaystyle {\begin{bmatrix}II&IB&IE\\BI&BB&BE\\EI&EB&EE\end{bmatrix}}}$

(4)

Обе формы матриц с размерными и логическими областями могут быть сериализованный в качестве "ДЭ-9ИМ строковые коды", которые представляют их в виде однострочной строки. С 1999 г. строковые коды есть стандарт^[5] формат.

Для проверки вывода или анализа шаблонов значение матрицы (или строковый код) можно проверить с помощью символа "маска ": желаемое выходное значение с необязательным звездочка символы как подстановочные знаки - то есть, "*"с указанием выходных позиций, о которых разработчик не заботится (свободные значения или" неважные позиции "). Область элементов маски: {0,1,2,F,*}, или же {Т,F,*} для булевой формы.

Более простые модели 4-пересечение и 9-Перекресток были предложены раньше ДЭ-9ИМ для выражения пространственные отношения^[6] (и возникли термины 4IM и 9IM). Их можно использовать вместо ДЭ-9ИМ для оптимизации вычислений, когда входные условия удовлетворяют определенным ограничениям.

Иллюстрация

Визуально для двух перекрывающихся полигональных геометрий это выглядит так:^[7]

б

а

Интерьер Граница Внешний вид Интерьер   ${\displaystyle \dim[I(a){\color {red}\cap }I(b)]=2}$     ${\displaystyle \dim[I(a){\color {red}\cap }B(b)]=1}$     ${\displaystyle \dim[I(a){\color {red}\cap }E(b)]=2}$   Граница   ${\displaystyle \dim[B(a){\color {red}\cap }I(b)]=1}$     ${\displaystyle \dim[B(a){\color {red}\cap }B(b)]=0}$     ${\displaystyle \dim[B(a){\color {red}\cap }E(b)]=1}$   Внешний вид   ${\displaystyle \dim[E(a){\color {red}\cap }I(b)]=2}$     ${\displaystyle \dim[E(a){\color {red}\cap }B(b)]=1}$     ${\displaystyle \dim[E(a){\color {red}\cap }E(b)]=2}$

При чтении слева направо и сверху вниз ДЭ-9ИМ(а,б) строковый код '212101212', компактное представление ${\displaystyle II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2}$.

Пространственные предикаты

Пространственные предикаты находятся топологически инвариантный двоичный пространственные отношения на основе ДЭ-9ИМ. Для простоты использования «именованные пространственные предикаты» были определены для некоторых общих отношений.

В пространственный предикат функции которые могут быть получены (выражены масками) из ДЭ-9ИМ включают:^[4][8]

Предикаты, определенные с помощью масок домена {Т,F,*}

Имя (синоним)	Матрица пересечения и строка кода маски (логическое ИЛИ между матрицами)				Значение и определение[4]	Эквивалент
Равно	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				II ∧ ~IE ∧ ~БЫТЬ ∧ ~EI ∧ ~EB (5) а и б топологически равный. «Две геометрии топологически равны, если их внутренности пересекаются, и никакая часть внутренней или границы одной геометрии не пересекает внешнюю часть другой».[9]	В & Содержит
	Т * F ** FFF *
Непересекающийся	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				~ II ∧ ~IB ∧ ~БИ ∧ ~BB (6) а и б находятся непересекающийся: у них нет общего. Они образуют набор отключен геометрии.	не пересекает
	FF * FF ****
Прикосновения (встречает)	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$		~ II ∧ (IB ∨ БИ ∨ BB) (7) а касается б: у них есть хоть одна общая черта, но их внутренности не пересекаются.
	FT *******	F ** T *****	F *** т ****
Содержит	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				II ∧ ~EI ∧ ~EB (8) а содержит б: геометрия б лежит в а, и интерьеры пересекаются. Другое определение: "а содержит б если только нет точек б лежать во внешности а, и хотя бы одна точка внутри б лежит в интерьере а".[10]	В(б,а)
	Т ***** FF *
Охватывает	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	(II ∨ IB ∨ БИ ∨ BB) ∧ ~EI ∧ ~EB (9) а охватывает б: геометрия б лежит в а. Другие определения: «По крайней мере, одна точка б лежит в а, и нет смысла б лежит во внешности а"или" Каждая точка б точка (внутренность или граница) а".	Покрыт(б,а)
	Т ***** FF *	* Т **** FF *	*** Т ** ФФ *	**** Т * FF *

Предикаты, которые могут быть получены из вышеизложенного с помощью логическое отрицание или инверсия параметра (транспонирование матрицы ), как указано в последнем столбце:

Пересекает	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	а пересекает б: геометрии а и б имеют хотя бы одну общую черту.	не непересекающийся
	Т ********	* Т *******	*** Т *****	**** Т ****
В (внутри)	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				а внутри б: а лежит в интерьере б.	Содержит(б,а)
	Т * F ** F ***
Покрыт	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {T} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	а покрывается б (расширяет В): геометрия а лежит в б. Другие определения: «По крайней мере, одна точка а лежит в б, и нет смысла а лежит во внешности б"или" Каждая точка а точка (внутренность или граница) б".	Охватывает(б,а)
	Т * F ** F ***	* TF ** F ***	** FT * F ***	** F * TF ***

Предикаты, использующие входные измерения и определенные с масками домена {0,1,Т,*}

Кресты ${\displaystyle \dim(a)\neq \dim(b)}$ или же dim (любой) = 1	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {0} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$		а кресты б: у них есть некоторые, но не все внутренние точки, общие, и размер пересечения меньше, чем размер хотя бы одной из них. Правила выбора маски проверяются только когда ${\displaystyle \dim(a)\neq \dim(b)}$, кроме строковых / строковых входов, иначе ложно:[11] (II=0) для линий, (II ∧ IE) когда ${\displaystyle \dim(a)<\dim(b)}$,   (II ∧ EI) когда ${\displaystyle \dim(a)>\dim(b)}$ (10)
	Т * Т ****** ${\displaystyle \dim(a)<\dim(b)}$	Т ***** Т ** ${\displaystyle \dim(a)>\dim(b)}$	0******** dim (любой) = 1
Перекрытия ${\displaystyle \dim(a)=\dim(b)}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {1} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$			а перекрывает б: у них есть некоторые, но не все общие точки, они имеют одинаковое измерение, а пересечение внутренних частей двух геометрий имеет такое же измерение, как и сами геометрии. Правила выбора маски проверяются только когда ${\displaystyle \dim(a)=\dim(b)}$, иначе неверно: (II ∧ IE ∧ EI) для точек или поверхностей, (II=1 ∧ IE ∧ EI) для линий (11)
	Т * Т *** Т ** dim = 0 или 2	1 * Т *** Т ** dim = 1

Заметь:

• В топологически равный определение не подразумевает, что они имеют одинаковые точки или даже что они принадлежат к одному классу.
• Выход ${\displaystyle \operatorname {DE-9IM} (a,b)}$ иметь информацию, содержащуюся в списке всех интерпретируемых предикатов о геометриях а и б.
• Все предикаты вычисляются с помощью масок. Только Кресты и Перекрытия есть дополнительные условия о ${\displaystyle \dim(a)}$ и ${\displaystyle \dim(b)}$.

• Все коды строк маски заканчиваются на *. Это потому что EE тривиально верно и поэтому не дает никакой полезной информации.
• В Равно маска Т * F ** FFF *, это «слияние» Содержит (Т ***** FF *) и В (Т * F ** F ***): (II ∧ ~EI ∧ ~EB) ∧ (II ∧ ~IE ∧ ~БЫТЬ).
• Маска Т ***** FF * встречается в определении обоих Содержит и Охватывает. Охватывает это более инклюзивное отношение. В частности, в отличие от Содержит он не различает точки на границе и внутри геометрии. В большинстве ситуаций Охватывает следует использовать вместо Содержит.
• Аналогично маска Т * F ** F *** встречается в определении обоих В и Покрыт. В большинстве ситуаций Покрыт следует использовать вместо В.

Характеристики

Пространственные предикаты обладают следующими свойствами: бинарные отношения:

• Рефлексивный: Равно, содержит, покрывает, покрыто, пересекает, внутри
• Антирефлексивный: Непересекающийся
• Симметричный: Равенство, пересечение, пересечение, касание, перекрытие
• Переходный: Равно, содержит, покрывает, покрыто, внутри

Интерпретация

Примеры пространственных отношений.

Выбор терминологии и семантики для пространственных предикатов основан на разумных соглашениях и традициях топологических исследований.^[4]Такие отношения как Пересекает, Непересекающийся, Прикосновения, В, Равно (между двумя геометриями а и б) имеют очевидную семантику:^[10][12]

Равно

а = б то есть (а ∩ б = а) ∧ (а ∩ б = б)

В

а ∩ б = а

Пересекает

а ∩ б ≠ ∅

Прикосновения

(а ∩ б ≠ ∅) ∧ (а^ο ∩ б^ο = ∅)

Предикаты Содержит и В в их определении есть тонкие аспекты, противоречащие интуиции.^[10] линия L который полностью содержится в границе многоугольника п является нет считается содержащимся в п. Эту причуду можно выразить как «Многоугольники не содержат границ». Эта проблема вызвана последним предложением Содержит определение выше: «по крайней мере одна точка внутренней части B лежит внутри A». В этом случае предикат Охватывает имеет более интуитивную семантику (см. определение), избегая рассмотрения границ.

Для лучшего понимания размерность входных данных может использоваться как оправдание для постепенного введения семантической сложности:

Отношения между	Соответствующие предикаты	Семантика добавлена
точка / точка	Равно, Непересекающийся	Другие допустимые предикаты сворачиваются в Равно.
точка / линия	добавляет Пересекает	Пересекает это уточнение Равно: "равная точка на линии".
линия / линия	добавляет Прикосновения, Кресты, ...	Прикосновения это уточнение Пересекает, только о "границах". Кресты Речь идет о «только одной точке».

Покрытие возможных результатов матрицы

Количество возможных результатов в логическом 9IM матрица 2⁹= 512, а в ДЭ-9ИМ матрица 3⁹= 6561. Процент этих результатов, удовлетворяющих определенному предикату, определяется следующим образом:

Вероятность	Имя
93.7%	Пересекает
43.8%	Прикосновения
25%	Кресты (для допустимых вводов 0% в противном случае)
23.4%	Охватывает и Покрыт
12.5%	Содержит, Перекрытия (для допустимых вводов 0% в противном случае) и В
6.3%	Непересекающийся
3.1%	Равно

В обычных приложениях геометрии пересекаются априори, и остальные отношения проверяются.

Составные предикаты "Пересекает ИЛИ ЖЕ Непересекающийся" и "Равно ИЛИ ЖЕ Разные"иметь сумму 100% (всегда верные предикаты), но"Охватывает ИЛИ ЖЕ Покрыт"имеют 41%, это не сумма, потому что они не являются логическими дополнениями или независимыми отношениями; то же самое"Содержит ИЛИ ЖЕ В", которые имеют 21%. Сумма 25% + 12,5% = 37,5% получается при игнорировании перекрытия строк в"Кресты ИЛИ ЖЕ Перекрытия", потому что допустимые входные наборы не пересекаются.

Запросы и утверждения

В ДЭ-9ИМ предлагает полное описательное утверждение о двух входных геометриях. Это математическая функция, представляющая полный комплект всех возможных отношений о двух объектах, например Таблица истинности, то Трехстороннее сравнение, а Карта Карно или Диаграмма Венна. Каждое выходное значение похоже на строку таблицы истинности, которая представляет отношения определенных входов.

Как показано выше, результат "212101212" получился из ДЭ-9ИМ(а,б) является полным описанием всех топологических отношений между конкретными геометриями. а и б. Это говорит нам, что ${\displaystyle II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2}$.

С другой стороны, если мы проверим такие предикаты, как Пересекает(а,б) или же Прикосновения(а,б) - для того же примера у нас есть "Пересекает=истинный и Прикосновения=истинный"- это неполное описание" всех топологических отношений ". Предикаты также ничего не говорят о размерности геометрий (неважно, если а и б являются линиями, областями или точками).

Эта независимость от типа геометрии и отсутствие полнота, на предикаты, полезны для общие вопросы о двух геометриях:

	внутренняя / граница / внешняя семантика	обычная смысловая
Утверждения	более наглядный " а и б имеют ДЭ-9ИМ (а,б)='212101212' "	менее описательный " а Касается б "
Запросы	более строгий "Показать все пары геометрий, где ДЭ-9ИМ (а,б)='212101212' "	более общий "Показать все пары геометрий, где Прикосновения(а,б) "

Для обычных приложений использование пространственные предикаты также оправдано тем, что человек читаемый чем ДЭ-9ИМ описания: типичный пользователь лучше интуитивно понимает предикаты (чем набор пересечений внутренних / внешних / внутренних поверхностей).

Предикаты полезны семантический в обычные приложения, поэтому полезно переводить ДЭ-9ИМ описание в список всех связанных предикатов,^[13][14] это похоже на процесс литья между двумя разными семантическими типами. Примеры:

• Строковые коды "0F1F00102" и "0F1FF0102"иметь семантику"Пересечения, пересечения и перекрытия".
• Строковый код "1FFF0FFF2"иметь семантику"Равно".
• Строковые коды "F01FF0102", "FF10F0102", "FF1F00102", "F01FFF102", и "FF1F0F1F2"иметь семантику"Пересечения и прикосновения".

Стандарты

В Открытый геопространственный консорциум (OGC) стандартизировал типичные пространственные предикаты (Contains, Crosses, Intersects, Touches и т. Д.) Как логические функции, а модель DE-9IM,^[15] как функция, возвращающая строку (код DE-9IM), с доменом {0,1,2,F}, смысл 0= точка, 1= линия, 2= площадь и F= "пустой набор". Этот строковый код DE-9IM представляет собой стандартизированный формат для обмена данными.

В Простой доступ к функциям (ISO 19125) стандарт,^[16] в главе 7.2.8 «Подпрограммы SQL для типа Geometry» в качестве поддерживаемых подпрограмм рекомендуется SQL / MM Пространственный^[17] (ISO 13249-3, часть 3: Пространственный) 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_Кресты, ST_Within, ST_Contains, ST_Overlaps и ST_Relate.

DE-9IM в стандартах OGC использует следующие определения внутренних и границ для основных типов стандартной геометрии OGC:^[18]

Подтипы	Тусклый	Интерьер (я)	граница (B)
Point, MultiPoint	0	Точка, Точки	Пустой
LineString, Линия	1	Точки, которые остались после удаления граничных точек.	Две конечные точки.
LinearRing	1	Все точки по геометрии.	Пустой.
MultilineString	1	Точки, которые остались после удаления граничных точек.	Те точки, которые находятся в границах нечетного числа его элементов (кривых).
Многоугольник	2	Очки внутри колец.	Набор колец.
Мультиполигон	2	Очки внутри колец.	Набор колец его элементов (многоугольников).
УВЕДОМЛЕНИЕ: внешние точки (E) точки п не в интерьер или же граница, поэтому не требует дополнительной интерпретации, E (p) = not (I (p) или B (p)).

Реализация и практическое использование

Большинство пространственных баз данных, таких как PostGIS, реализует ДЭ-9ИМ () модель стандартными функциями:^[19] ST_Relate, ST_Equals, ST_Intersectsи т. д. Функция ST_Relate (а, б) выводит стандартные OGC Строковый код DE-9IM.

Примеры: две геометрии, а и б, который пересекается и касается точки (например, с ${\displaystyle \dim(B(a)\cap I(b))=0}$ и ${\displaystyle \dim(I(a)\cap I(b))=F}$), возможно ST_Relate (a, b) = 'FF1F0F1F2' или же ST_Relate (a, b) = 'FF10F0102' или же ST_Relate (a, b) = 'FF1F0F1F2'. Это также удовлетворяет ST_Intersects (a, b) = истина и ST_Touches (a, b) = истина.Когда ST_Relate (a, b) = '0FFFFF212', возвращаемый код DE-9IM имеет семантику «Пересечения (a, b) & Crosses (a, b) & Within (a, b) & CoveredBy (a, b)», то есть возвращает истинный на булевом выражении 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 (а, б) строка в ST_RelateMatch () функция.^[21]Когда используешь ST_Relate (a, b, маска), он возвращает логическое значение. Примеры:

• ST_Relate (a, b, '* FF * FF212') возвращается истинный когда ST_Relate (а, б) является 0FFFFF212 или же 01FFFF212, и возвращает ложный когда 01FFFF122 или же 0FF1FFFFF.
• ST_RelateMatch ('0FFFFF212', '* FF * FF212') и ST_RelateMatch ('01FFFF212', 'TTF * FF212') находятся истинный, ST_RelateMatch ('01FFFF122', '* FF * FF212') является ложный.

Синонимы

• «Матрица Эгенгофера» - это синоним 9IM Матрица логической области 3x3.^[22]
• «Клементини-Матрикс» - синоним ДЭ-9ИМ Матрица 3x3 из {0,1,2,F} домен.^[22]
• «Операторы Эгенгофера» и «операторы Клементини» иногда относятся к матричным элементам как II, IEи т. д., которые можно использовать в логических операциях. Пример: предикат "грамм₁ содержит грамм₂"может быть выражено"⟨грамм₁| II ∧ ~ EI ∧ ~ EB |грамм₁⟩", который можно преобразовать в синтаксис маски, Т ***** FF *.
• Предикаты "встречает" - синоним касается; «внутри» - это синоним в
• Oracle^[14] "ANYINTERACT" - синоним пересекает и "OVERLAPBDYINTERSECT" является синонимом перекрывает. Его "OVERLAPBDYDISJOINT" не имеет соответствующего именованного предиката.
• В Расчет соединения регионов операторы предлагают несколько синонимов для предикаты: непересекающийся постоянный ток (отключен), касается EC (внешнее подключение), равно это EQ. Другое, например Перекрытия как PO (частично перекрывающиеся), нужен контекстный анализ или композиция.^[23][24]

Смотрите также

Стандарты: Простой доступ к функциям (ISO 19125) Открытый геопространственный консорциум GeoSPARQL

Программного обеспечения: Пространственная база данных Объектно-ориентированная пространственная база данных FOSS: Пакет топологии JTS ТРАВА ГИС ГДАЛ (библиотека) PostGIS

Похожие темы: Геопространственная топология Карта Карно (с двумя переменными) Оператор отношения Пространственный анализ Пространственное отношение Пространственно-временные рассуждения

Рекомендации

1. Клементини, Элисео; Ди Феличе, Паолино; ван Остером, Питер (1993). «Небольшой набор формальных топологических отношений, пригодных для взаимодействия с конечным пользователем». В Авеле Давид; Ooi, Beng Chin (ред.). Достижения в области пространственных баз данных: Третий международный симпозиум, SSD '93, Сингапур, 23–25 июня 1993 г.. Конспект лекций по информатике. 692/1993. Springer. С. 277–295. Дои:10.1007/3-540-56869-7_16.
2. Клементини, Элисео; Шарма, Джаянт; Эгенхофер, Макс Дж. (1994). «Моделирование топологических пространственных отношений: стратегии обработки запросов». Компьютеры и графика. 18 (6): 815–822. Дои:10.1016/0097-8493(94)90007-8.
3. Egenhofer, M.J .; Франзоза, Р. Д. (1991). «Точечно-множественные топологические пространственные отношения». Int. J. GIS. 5 (2): 161–174. Дои:10.1080/02693799108927841.
4. Egenhofer, M.J .; Херринг, Дж. Р. (1990). «Математическая основа для определения топологических отношений» (PDF). Архивировано из оригинал (PDF) на 14.06.2010.
5. "OpenGIS Спецификация простых функций для SQL », Версия 1.1, был выпущен 5 мая 1999 года. Это был первый международный стандарт, устанавливающий соглашения о формате для Строковые коды DE-9IM, и имена «Именованных предикатов пространственных отношений на основе DE-9IM» (см. раздел с этим заголовком).
6. М. Дж. Эгенхофер, Дж. Шарма и Д. Марк (1993) "Критическое сравнение моделей 4-пересечений и 9-пересечений для пространственных отношений: формальный анализ В архиве 2010-06-14 на Wayback Machine ", В: Авто-Carto XI В архиве 2014-09-25 на Wayback Machine.
7. Глава 4. Использование PostGIS: управление данными и запросы
8. JTS: класс IntersectionMatrix, Vivid Solutions, Inc., архивировано с оригинал на 2011-03-21
9. Технические условия СТС 2003 г.
10. М. Дэвис (2007 г.) "Причуды пространственного предиката "Содержит" ".
11. ST_Crosses
12. Câmara, G .; Freitas, U.M .; Казанова, М. А. (1995). "Алгебры полей и объектов для ГИС-операций". CiteSeerX  10.1.1.17.991.
13. А ДЭ-9ИМ переводчик всех связанных предикатов пространственного отношения.
14. Примечание. В Пространственная функция Oracle SDO_RELATE () В архиве 2013-07-21 в Wayback Machine выполнять только частичный перевод внутри, предлагая пользователю маску для проверяемого списка предикатов, вместо строки DE-9IM.
15. «Спецификация реализации OpenGIS для географической информации - Простой доступ к функциям - Часть 2: опция SQL», OGC, http://www.opengeospatial.org/standards/sfs
16. Open Geospatial Consortium Inc. (2007), «Стандарт реализации OpenGIS® для географической информации - простой доступ к функциям - Часть 2: опция SQL», Документ OGC 06-104r4 версия 1.2.1 (обзор от 04.08.2010).
17. ISO 13249-3 Часть 3: Пространственные, краткое содержание в Пакеты мультимедиа и приложений SQL (SQL / MM) В архиве 2010-02-14 в Wayback Machine.
18. «Энциклопедия ГИС» под редакцией Шаши Шекхара и Хуэй Сюн. SpringerScience 2008. стр. 242
19. ST_Relate () PostGIS функция онлайн-документация.
20. Тестовый пример JTS «точка A в одной из точек B», http://www.vividsolutions.com/jts/tests/Run1Case4.html В архиве 2016-03-04 в Wayback Machine
21. ST_RelateMatch () PostGIS функция онлайн-документация.
22. «Энциклопедия ГИС», С. Шехар, Х. Сюн. ISBN  978-0-387-35975-5.
23. «Исчисление многомерных связей» (2017), http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf
24. «Идентификация отношений в исчислении связей регионов: 9-пересечение, уменьшенное до 3+ -предикатов пересечения» (2013), https://pdfs.semanticscholar.org/8184/abc9b25ed340f9195cc904249bda415bb0c3.pdf

внешняя ссылка

• Теория множества точек и матрица DE-9IM
• Иллюстрированное руководство для DE-9IM