ДЭ-9ИМ

Расширенная по измерениям модель 9-пересечений ( DE-9IM ) — это топологическая модель и стандарт , используемый для описания пространственных отношений двух регионов (две геометрии в двух измерениях , R ²), в геометрии , топологии множества точек , геопространственной топологии и областях, связанных с компьютерным пространственным анализом . Пространственные отношения, выраженные моделью, инвариантны к вращения , перемещения и масштабирования преобразованиям .

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

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

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

Модель DE-9IM основана на пересечений матрице 3×3 вида:

\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 )

где ⁠ $\dim$ ⁠ — размерность пересечения внутренней (∩) части (I), границы (B) и внешней части (E) геометрий a и b .

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

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

Я (а) = а тот B (а)=\partial а E (а)= а и

( 2 )

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

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

\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 )

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

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

( 4 )

Обе формы матриц, с размерными и логическими доменами, могут быть сериализованы как « строковые коды DE-9IM », которые представляют их в виде однострочного строкового шаблона. С 1999 года строковые коды имеют стандарт ^[5] формат.

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

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

Иллюстрация

Визуально для двух перекрывающихся полигональных геометрий результат функции DE_9IM( a , b ) выглядит так: ^[7]

б

а

	Интерьер	Граница	Экстерьер
Интерьер	$\dim[I(a){\color {red}\cap }I(b)]=2$	$\dim[I(a){\color {red}\cap }B(b)]=1$	$\dim[I(a){\color {red}\cap }E(b)]=2$
Граница	$\dim[B(a){\color {red}\cap }I(b)]=1$	$\dim[B(a){\color {red}\cap }B(b)]=0$	$\dim[B(a){\color {red}\cap }E(b)]=1$
Экстерьер	$\dim[E(a){\color {red}\cap }I(b)]=2$	$\dim[E(a){\color {red}\cap }B(b)]=1$	$\dim[E(a){\color {red}\cap }E(b)]=2$

Эту матрицу можно сериализовать . Читая слева направо и сверху вниз, результат: ⁠ $II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2$ ⁠ . Итак, в компактном представлении строковый код равен ' 212101212 '.

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

Любое топологическое свойство DE-9IM, , основанное на бинарном пространственном отношении является пространственным предикатом . Для простоты использования для некоторых общих отношений были определены «именованные пространственные предикаты», которые позже стали стандартными предикатами.Функции пространственных предикатов : , которые можно получить из DE-9IM, включают ^[4]^[8]

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

Имя (синоним) Матрица пересечений и строка кода маски
( логическое ИЛИ между матрицами) Значение и определение ^[4] Эквивалент

Равно

{\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

II \land ~ IE \land ~ BE \land ~ EI \land ~ EB

( 5 )

a и b топологически равны . «Две геометрии топологически равны, если их внутренности пересекаются и ни одна часть внутренней части или границы одной геометрии не пересекает внешнюю часть другой». ^[9]

Внутри и содержит

T*F**FFF*

Непересекающийся

{\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

~II \land ~ IB \land ~ BI \land ~ BB

( 6 )

a и b : не пересекаются у них нет общей точки. Они образуют набор несвязных геометрий.

не пересекается

FF*FF****

Прикосновения
(встречается)

{\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

~II \land (IB \lor BI \lor BB)

( 7 )

a касается b : они имеют хотя бы одну общую точку, но их внутренности не пересекаются.

FT******* F**T***** F***T****

Содержит

{\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

II \land ~ EI \land ~ EB

( 8 )

a содержит b : геометрия b лежит в a , а внутренности пересекаются. Другое определение: « a содержит b тогда и только тогда, когда никакие точки b не лежат во внешности a , и по крайней мере одна точка внутренней части b лежит внутри a ». ^[10]

Внутри ( б , а )

T*****FF*

Обложки

{\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

(II \lor IB \lor BI \lor BB) \land ~ EI \land ~ EB

( 9 )

a покрывает b : геометрия b лежит в a . Другие определения: «По крайней мере одна точка b лежит в a , и ни одна точка b не лежит снаружи a » или «Каждая точка b является точкой (внутренней или границей) a ».

Покрыто ( б , а )

T*****FF* *T****FF* ***T**FF* ****T*FF*

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

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

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

Кресты
⁠

\dim(a)\neq \dim(b)

⁠ или

тусклый(любой) = 1

{\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {0} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

a пересекает b : у них есть некоторые, но не все общие внутренние точки, и размерность пересечения меньше, чем размерность хотя бы одной из них. Следующие правила выбора маски необходимо только проверять в том случае, если ⁠

\dim(a)\neq \dim(b)

⁠ (кроме ввода строк/строк, которые разрешены ), в противном случае предикат имеет значение false : ^[11]

(II =0)

для линий,

(II \land IE),

когда ⁠

\dim(a)<\dim(b)

⁠ ,

(II \land EI)

когда ⁠

\dim(a)>\dim(b)

⁠

( 10 )

T*T******
⁠ $\dim(a)<\dim(b)$ ⁠ T*****T**
⁠ $\dim(a)>\dim(b)$ ⁠ 0********
$тусклый(любой) = 1$

Перекрытия
⁠

\dim(a)=\dim(b)

⁠

{\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

{\Bigl [}{\begin{smallmatrix}\mathrm {1} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}

a перекрывается с b : у них есть некоторые, но не все общие точки, они имеют одинаковую размерность, а пересечение внутренних частей двух геометрий имеет то же измерение, что и сами геометрии. Следующие правила выбора маски необходимо только проверять в том случае, если ⁠

\dim(a)=\dim(b)

⁠ , в противном случае предикат ложен :

(II \land IE \land EI)

для точек или поверхностей,

(II =1 \land IE \land EI)

для линий

( 11 )

T*T***T**
$тусклый = 0 или 2$ 1*T***T**
$тусклый = 1$

Обратите внимание:

Топологически равное определение не означает, что они имеют одинаковые точки или даже принадлежат к одному классу.

Выход ⁠ $\operatorname {DE-9IM} (a,b)$ ⁠ иметь информацию, содержащуюся в списке всех интерпретируемых предикатов о геометриях a и b .

Все предикаты вычисляются по маскам. Только кресты и перекрытия имеют дополнительные условия о ⁠ $\dim(a)$ ⁠ и ⁠ $\dim(b)$ ⁠ .

Все коды строк маски заканчиваются на *. Это связано с тем, что EE тривиально верен и, следовательно, не дает никакой полезной информации.

Маска «Равно» , T*F**FFF*, представляет собой «слияние» Содержит ( T*****FF*) и Внутри ( T*F**F***): $(II \land ~ EI \land ~ EB) \land (II \land ~ IE \land ~ BE)$ .

Маска T*****FF* встречается в определении как Содержит , так и Обложек . Обложки — более инклюзивное отношение. В частности, в отличие от Содержит, он не различает точки на границе и внутри геометрии. В большинстве ситуаций Covers следует использовать вместо contains .

Аналогично, маска T*F**F*** встречается в определении как Within , так и CoveredBy . В большинстве ситуаций CoveredBy следует использовать вместо Within .

использовались другие термины и другие формальные подходы Исторически для выражения пространственных предикатов ; например, исчисление связей регионов было введено в 1992 году ^[12] Рэнделл, Кон и Кон.

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

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

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

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

Выбор терминологии и семантики пространственных предикатов основан на разумных соглашениях и традициях топологических исследований. ^[4]Такие отношения, как Intersects , Disjoint , Touches , Within , Equals (между двумя геометриями a и b ), имеют очевидную семантику: ^[10]^[13]

Равно: а знак равно б то есть ( а ∩ б знак равно а ) ∧ ( а ∩ б знак равно б )
В пределах: а ∩ б = а
Пересекается: а ∩ б ≠ ∅
Прикосновения: ( а ∩ b ≠ ∅) ∧ ( а ^тот ∩ б ^тот = ∅)

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

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

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

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

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

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

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

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

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

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

Как показано выше, выходные данные «212101212» в результате DE-9IM ( a , b ) представляют собой полное описание всех топологических отношений между конкретными геометриями a и b . Это говорит нам, что ⁠ $II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2$ ⁠ .

С другой стороны, если мы проверяем такие предикаты, как Intersects ( a , b ) или Touches ( a , b ) — для того же примера мы имеем « Intersects = правда и касается = true » — это неполное описание «всех топологических отношений».Предикаты также ничего не говорят о размерности геометрии (неважно, являются ли a и b линиями, площадями или точками).

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

	внутренняя/граничная/внешняя семантика	обычная семантика
Утверждения	более описательный " a и b имеют $DE-9IM(a, b)='212101212'$ "	менее описательный « а касается б »
Запросы	более ограничительный " Показать все пары геометрий, где $DE-9IM(a, b)='212101212'$ "	более общий «Показать все пары геометрий, где касается ( a , b )»

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

Предикаты имеют полезную семантику в обычных приложениях, поэтому полезно перевести описание DE-9IM в список всех связанных предикатов. ^[14]^[15] это похоже на процесс сопоставления двух разных семантических типов. Примеры:

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

Стандарты

Открытый геопространственный консорциум (OGC) стандартизировал типичные пространственные предикаты (содержит, кресты, пересечения, касания и т. д.) как логические функции, а модель DE-9IM ^[16] как функция, возвращающая строку (код DE-9IM) с доменом { 0 , 1 , 2 , F }, что означает 0 = точка, 1 = линия, 2 = площадь и F = «пустой набор». Этот строковый код DE-9IM представляет собой стандартизированный формат обмена данными.

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

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

Подтипы	Дим	Интерьер ( $Я$ )	граница ( $Б$ )
Точка, Многоточка	0	Точка, Очки	Пустой
ЛинияСтрока, Линия	1	Точки, которые остаются после удаления граничных точек.	Две конечные точки.
ЛинейныйКольцо	1	Все точки по геометрии.	Пустой.
Многострочная строка	1	Точки, которые остаются после удаления граничных точек.	Те точки, которые находятся в границах нечетного числа его элементов (кривых).
Полигон	2	Точки внутри колец.	Набор колец.
Мультиполигон	2	Точки внутри колец.	Набор колец его элементов (многоугольников).
ВНИМАНИЕ: внешние точки (E) — это точки p , не находящиеся внутри или на границе , поэтому дополнительная интерпретация не требуется. E(p)=not(I(p) или B(p)) .

Внедрение и практическое использование

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

Примеры: две геометрии a и b , которые пересекаются и касаются точки (например, ⁠ $\dim(B(a)\cap I(b))=0$ ⁠ и ⁠ $\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)=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, ^[21] точки, которая не «пересекает» мультиточку (объект, представляющий собой набор точек), но предикат Crosses (если он определен маской) возвращает true .

Обычно перегружают ST_Relate(), добавив параметр маски,или используйте возвращенный ST_Relate(a,b) в строку Функция ST_RelateMatch() . ^[22]При использовании ST_Relate(a,b,mask) возвращает логическое значение. Примеры:

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

Синонимы

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

См. также

Стандарты:

Программное обеспечение:

Связанные темы:

Ссылки

^ Клементини, Элисео; Ди Феличе, Паолино; ван Остером, Питер (1993). «Небольшой набор формальных топологических отношений, подходящих для взаимодействия с конечным пользователем». У Авеля, Давид; Оой, Бенг Чин (ред.). Достижения в области пространственных баз данных: Третий международный симпозиум, SSD '93, Сингапур, 23–25 июня 1993 г., материалы . Конспекты лекций по информатике. Том. 692/1993. Спрингер. стр. 277–295. дои : 10.1007/3-540-56869-7_16 . ISBN 978-3-540-56869-8 .
^ Клементини, Элисео; Шарма, Джаянт; Эгенхофер, Макс Дж. (1994). «Моделирование топологических пространственных отношений: стратегии обработки запросов». Компьютеры и графика . 18 (6): 815–822. дои : 10.1016/0097-8493(94)90007-8 .
^ Эгенхофер, MJ; Францоза, РД (1991). «Топологические пространственные отношения множества точек» . Межд. Дж. ГИС . 5 (2): 161–174. дои : 10.1080/02693799108927841 .
^ Перейти обратно: ^а ^б ^с ^д Эгенхофер, MJ; Херринг, младший (1990). «Математическая основа определения топологических отношений» (PDF) . Материалы 4-го Международного симпозиума по обработке пространственных данных . Архивировано из оригинала (PDF) 14 июня 2010 г.
^ « Спецификация простых функций OpenGIS для SQL», редакция 1.1 , была выпущена 5 мая 1999 года. Это был первый международный стандарт, устанавливающий соглашения о формате для строковых кодов DE-9IM и имена «Именованных предикатов пространственных отношений». на базе ДЭ-9ИМ» (см. раздел с этим заголовком).
^ М. Дж. Эгенхофер, Дж. Шарма и Д. Марк (1993) « Критическое сравнение моделей с 4 и 9 пересечениями для пространственных отношений: формальный анализ. Архивировано 14 июня 2010 г. в Wayback Machine », В: Auto -Carto XI. Архивировано 25 сентября 2014 г. в Wayback Machine .
^ Перейти обратно: ^а ^б Глава 4. Использование PostGIS: управление данными и запросы
^ JTS: Class IntersectionMatrix , Vivid Solutions, Inc., заархивировано из оригинала 21 марта 2011 г.
^ Технические характеристики СТС 2003 г.
^ Перейти обратно: ^а ^б ^с М. Дэвис (2007), « Особенности пространственного предиката «содержит ».
^ ST_Кресты
^ Рэнделл, округ Колумбия; Цюи, З; Кон, АГ (1992). «Пространственная логика, основанная на регионах и связях». 3-й Межд. Конф. по представлению знаний и рассуждениям . Морган Кауфманн. стр. 165–176.
^ Камара, Г.; Фрейтас, UM; Казанова, Массачусетс (1995). «Алгебра полей и объектов для операций ГИС». CiteSeerX 10.1.1.17.991 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Переводчик DE-9IM всех связанных предикатов пространственного отношения.
^ Перейти обратно: ^а ^б Примечание. Оракула Пространственная функция SDO_RELATE(). Архивировано 21 июля 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 августа 2010 г.).
^ ISO 13249-3, часть 3: Пространственные, обобщенные в SQL Multimedia and Application Packages (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 по функции Электронная документация .
^ Перейти обратно: ^а ^б «Энциклопедия ГИС», С. Шекхар, Х. Сюн. ISBN 978-0-387-35975-5 .
^ «Исчисление соединений многомерных регионов» (2017), http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf
^ Сабхарвал, Чаман Л.; Леопольд, Дженнифер Л. (2013). «Идентификация отношений в исчислении связей регионов: 9-пересечений уменьшено до 3 + -предикатов пересечения». Достижения в области мягких вычислений и их приложений . Конспекты лекций по информатике. Том. 8266. стр. 362–375. дои : 10.1007/978-3-642-45111-9_32 . ISBN 978-3-642-45110-2 .

Внешние ссылки

[1] Клементини, Элисео; Ди Феличе, Паолино; ван Остером, Питер (1993). «Небольшой набор формальных топологических отношений, подходящих для взаимодействия с конечным пользователем». У Авеля, Давид; Оой, Бенг Чин (ред.). Достижения в области пространственных баз данных: Третий международный симпозиум, SSD '93, Сингапур, 23–25 июня 1993 г., материалы . Конспекты лекций по информатике. Том. 692/1993. Спрингер. стр. 277–295. дои : 10.1007/3-540-56869-7_16 . ISBN 978-3-540-56869-8 .

[2] Клементини, Элисео; Шарма, Джаянт; Эгенхофер, Макс Дж. (1994). «Моделирование топологических пространственных отношений: стратегии обработки запросов». Компьютеры и графика . 18 (6): 815–822. дои : 10.1016/0097-8493(94)90007-8 .

[3] Эгенхофер, MJ; Францоза, РД (1991). «Топологические пространственные отношения множества точек» . Межд. Дж. ГИС . 5 (2): 161–174. дои : 10.1080/02693799108927841 .

[sdh1990-4] Перейти обратно: ^а ^б ^с ^д Эгенхофер, MJ; Херринг, младший (1990). «Математическая основа определения топологических отношений» (PDF) . Материалы 4-го Международного симпозиума по обработке пространственных данных . Архивировано из оригинала (PDF) 14 июня 2010 г.

[firstStd-5] « Спецификация простых функций OpenGIS для SQL», редакция 1.1 , была выпущена 5 мая 1999 года. Это был первый международный стандарт, устанавливающий соглашения о формате для строковых кодов DE-9IM и имена «Именованных предикатов пространственных отношений». на базе ДЭ-9ИМ» (см. раздел с этим заголовком).

[4vs9-6] М. Дж. Эгенхофер, Дж. Шарма и Д. Марк (1993) « Критическое сравнение моделей с 4 и 9 пересечениями для пространственных отношений: формальный анализ. Архивировано 14 июня 2010 г. в Wayback Machine », В: Auto -Carto XI. Архивировано 25 сентября 2014 г. в Wayback Machine .

[PostGISch4-7] Перейти обратно: ^а ^б Глава 4. Использование PostGIS: управление данными и запросы

[8] JTS: Class IntersectionMatrix , Vivid Solutions, Inc., заархивировано из оригинала 21 марта 2011 г.

[9] Технические характеристики СТС 2003 г.

[davis2007-10] Перейти обратно: ^а ^б ^с М. Дэвис (2007), « Особенности пространственного предиката «содержит ».

[ST_Crosses-11] ST_Кресты

[12] Рэнделл, округ Колумбия; Цюи, З; Кон, АГ (1992). «Пространственная логика, основанная на регионах и связях». 3-й Межд. Конф. по представлению знаний и рассуждениям . Морган Кауфманн. стр. 165–176.

[cafrca-13] Камара, Г.; Фрейтас, UM; Казанова, Массачусетс (1995). «Алгебра полей и объектов для операций ГИС». CiteSeerX 10.1.1.17.991 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[14] Переводчик DE-9IM всех связанных предикатов пространственного отношения.

[SDO_RELATE-15] Перейти обратно: ^а ^б Примечание. Оракула Пространственная функция SDO_RELATE(). Архивировано 21 июля 2013 г. на Wayback Machine. Внутренне выполняет только частичный перевод, предлагая пользователю маску для списка или списка предикатов, которые необходимо проверить, вместо строки DE-9IM.

[ogs1-16] «Спецификация реализации OpenGIS для географической информации. Простой доступ к функциям. Часть 2: опция SQL», OGC , http://www.opengeospatial.org/standards/sfs

[SFS2007-17] Open Geospatial Consortium Inc. (2007), «Стандарт реализации OpenGIS® для географическихинформация — Простой доступ к функциям — Часть 2: Опция SQL», документ OGC 06-104r4, версия 1.2.1 (обзор от 04 августа 2010 г.).

[18] ISO 13249-3, часть 3: Пространственные, обобщенные в SQL Multimedia and Application Packages (SQL/MM), заархивировано 14 февраля 2010 г. на Wayback Machine .

[19] «Энциклопедия ГИС», под редакцией Шаши Шекхара и Хуэй Сюн. SpringerScience 2008. стр. 242

[20] ST_Relate() PostGIS по функции Электронная документация .

[test1case4-21] Тестовый пример JTS «точка A внутри одной из точек B», http://www.vividsolutions.com/jts/tests/Run1Case4.html. Архивировано 4 марта 2016 г. на Wayback Machine.

[22] ST_RelateMatch() PostGIS по функции Электронная документация .

[encygis-23] Перейти обратно: ^а ^б «Энциклопедия ГИС», С. Шекхар, Х. Сюн. ISBN 978-0-387-35975-5 .

[24] «Исчисление соединений многомерных регионов» (2017), http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf

[25] Сабхарвал, Чаман Л.; Леопольд, Дженнифер Л. (2013). «Идентификация отношений в исчислении связей регионов: 9-пересечений уменьшено до 3 + -предикатов пересечения». Достижения в области мягких вычислений и их приложений . Конспекты лекций по информатике. Том. 8266. стр. 362–375. дои : 10.1007/978-3-642-45111-9_32 . ISBN 978-3-642-45110-2 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]