DE-9IM

DE-9IM(Dimensionally Extended 9-Intersection Model, DE-9IM)은 기하학, 점 집합 위상, 지리공간 위상, 컴퓨터 공간 분석과 관련된 분야에서 두 영역(2차원 기하학, R²)의 공간 관계를 기술하는 데 사용되는 위상학적 모델이자 표준이다. 모델에 의해 표현된 공간적 관계는 회전, 번역 및 스케일링 변형에 불변하다.

행렬은 지오메트리 관계를 분류하기 위한 접근방식을 제공한다. 대략, 참/거짓 매트릭스 도메인을 사용하면, 이진 분류 체계로 그룹화할 수 있는 512개의 가능한 2D 토폴로지 관계가 있다. 영어에는 "간격", "터치", "평등"과 같은 약 10개의 계략(관계)이 포함되어 있다. 두 가지 기하학적 구조를 한 체계에 대해 시험할 때, 그 결과는 체계에 의해 명명된 공간적 술어가 된다.

이 모델은 클레멘티니^[1]^[2] 등이 에겐호퍼 등의 세미나를 바탕으로 개발했다.^[3]^[4] 지리정보시스템(GIS)과 공간 데이터베이스에서의 질의·주장 표준의 근거로 이용되어 왔다.

행렬 모형

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$ $[\displaystyle \dim }$ 은(는) 내부(I), 경계(B) 및 기하학적 a와 b의 외부(E)의 치수다 $\dim$ .

이 글에서 내부와 경계라는 용어는 대수적 위상 및 다지관 이론에서 사용되는 의미로 사용되며, 예를 들어 선 세그먼트의 내부는 그 끝점이 없는 선 세그먼트이며, 그 경계는 두 끝점(일반 위상에서는 선 세그먼트의 내부)에 불과하다. 평면이 비어 있고 선 세그먼트가 자체 경계임).

위상학적 공간 연산자의 표기법에서는 행렬 원소도 다음과 같이 표현할 수 있다.

I (a)= b o (a)=b(a)= a (a)=a(a)= a e)

(2)

빈 집합( dimension)의 치수는 -1 또는 -1로 표시된다. F(거짓말) 비빈 집합( dimension dimension)의 치수는 교차점의 최대 치수 수로 표시되며, 특히 점의 경우 0, 선의 경우 1, 면적의 경우 2가 표시된다. 그러면 모델의 도메인이 {0,1,2,F}이(가) 된다.

값 {0,1,2}을(를) T(참)에 매핑하기 위해 $\dim(x)$ $){\displaystyle \dim(x)}$ 값의 $\dim(x)$ 단순화된 버전을 얻으므로 부울 도메인 {T,F}을(를) 사용하십시오. 연산자와 함께 표시된 행렬은 다음과 같이 표현할 수 있다.

\operatorname {bin}(\operatorname {DE9IM})(a,b)=\cHB 이름 {9IM}(a,b)={\begin{bmatrix}a^{제일의 것이다}\cap b^{제일의 것이다}\neq \emptyset&a^{제일의 것이다}\cap\partial{b}\neq \emptyset&a^{제일의 것이다}\cap\\\partial{를}\cap b^{제일의 것이다}\neq \emptyset 및 \emptyset b^{e}\neq,\partial{를}\cap\partial{b}\neq \emptyset&\partial{를}\cap b^{e}\neq \emptyset \\a^{e}\cap b^{제일의 것이다}\neq \emptyset&a^{e}\cap\partial{b}\neq \emptyset&a^{e}\ca.pb^{e}\neq \emptyset \end{bmatrix}}

(3)

행렬의 원소는 다음과 같이 명명할 수 있다.

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

(4)

치수 및 부울 도메인을 포함한 두 매트릭스 양식은 모두 "DE-9"로 직렬화할 수 있다.IM 문자열 코드"는 단일 줄 문자열 패턴으로 이를 나타낸다. 1999년 이래로 문자열 코드는 표준^[5] 형식을 가지고 있다.

출력 확인 또는 패턴 분석의 경우 매트릭스 값(또는 문자열 코드)은 "마스크"로 확인할 수 있다. 원하는 출력 값(선택 사항인 별표 기호가 와일드카드로 표시됨), 즉 설계자가 상관하지 않는 출력 위치(자유 값 또는 "관리하지 않는 위치")를 나타내는 "*"이다. 마스크 요소의 도메인은 부울 형식에 대해 {0,1,2,F,*} 또는 {T,F,*}이다.

DE-9 이전에 보다 단순한 모델인 4-인터섹션과 9-인터섹션이 제안되었다.공간 관계를^[6] 표현하기 위한 IM (그리고 4IM과 9IM이라는 용어의 유래) DE-9 대신 사용할 수 있다.IM은 입력 조건이 특정 제약조건을 만족시킬 때 계산을 최적화한다.

삽화

겹치는 두 폴리곤 기하학적 구조의 경우 DE_9 함수의 결과IM(a,b)은 다음과 같이 보인다.^[7]

b

a

	실내	경계	외부
실내	$\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$

이 매트릭스는 연재할 수 있다. Reading from left-to-right and top-to-bottom, the result is $II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2$ . So, in a compact representation as string code is '212101212'.

공간 술어

DE-9에 기초한 위상학적 특성IM 이항 공간관계는 공간적 술어다. 사용 편의성을 위해 "공간 술어 이름"은 일부 공통 관계에 대해 정의되었으며, 이는 나중에 표준 술어가 되었다. DE-9에서 도출할 수 있는 공간적 술어함수IM은 다음을 포함한다.^[4]

{T,F,*} 도메인의 마스크로 정의된 술어:

이름(동기어) 교차로 행렬 및 마스크 코드 문자열
(매트릭스 사이의 부울 OR) 의미와 정의^[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****

터치스
(iii)

{\displaystyle {\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} &\mathrm {*} &\mathrmatrm {*} &\mathrmatrm {*} &\mathr} \end{smatrix}{bigr}}}}}}}}}\matrix}{bigr)

{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} &\mathrm {*} &\mathrmatrm {*} &\mathrmatrm {*} &\mathr} \end{smatrix}{bigr}}}}}}}}}\bigr

{\displaystyle {\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {T} &\mathrm {*} &\mathrmatrm {*} &\mathrmatrm {*} &\mathr} \end{smatrix}{bigr}}}}}}}}}}\matrix}}\bigr.

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

(7)

a touch 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는 a의 외관에는 b의 점이 없고, b의 내부에는 적어도 하나의 점이 a의 내부에 있다"는 것이다.^[10]

내부(b,a)

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 covers b: 기하학적 b는 a에 있다. 다른 정의: "b의 최소 한 지점은 a에 있고, b의 어떤 지점도 a의 외관에 있지 않다" 또는 "b의 모든 지점은 a의 (내부 또는 경계) 지점이다"

커버드바이(b,a)

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

마지막 열에서 표시한 대로 논리적 부정 또는 파라미터 반전(매트릭스 전환)을 통해 위에서 얻을 수 있는 술어:

교차점	${\begin{smallmatrix}\mathrm {T} &\mathrm {} &\mathrm {} &\mathrm {} &\mathrmatrm {} &\mathrmatrm {*} &\mathr} \end{bigr}}}}}}}$	${\begin{smallmatrix}\mathrm {} &\mathrm {} &\mathrm {} &\mathrm {} &\mathrmatrm {} &\mathrmatrm {} &\mathr} \end{smatrix{bigr}}}}}}}}}}\matrix {bigr}\matrix}}}}}}}}}}}\matrix {bigr$	${\begin{smallmatrix}\mathrm {} &\mathrm {T} &\mathrm {} &\mathrm {} &\mathrmatrm {} &\mathrmatrm {*} &\mathr} \end{bigr}}}}}}}$	${\begin{smallmatrix}\mathrm {} &\mathrm {} &\mathrm {T} &\mathrm {} &\mathrmatrm {} &\mathrmatrm {*} &\mathr} \end{smatrix{bigr}}}}}}}}}}\matrix {bigr}}\matrix}}}}}}}$	a 교차점 b: 기하학적 도형 a와 b는 적어도 하나의 공통점을 가지고 있다.	분리되지 않음
교차점	`T********`	`T******`	`*T***`	`**T**`	a 교차점 b: 기하학적 도형 a와 b는 적어도 하나의 공통점을 가지고 있다.	분리되지 않음
안쪽에 (iii)	${\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {} &\mathrm {F} \\\mathrm {} &\mathrm {} &\mathrm {F} \\\mathrm {} &\mathrm {} &\mathrm {} \end{smallmatrix}}{\Bigr ]}$				a는 b 안에 있다: a는 b의 내부에 있다.	포함(b,a)
안쪽에 (iii)	`TFF**`				a는 b 안에 있다: a는 b의 내부에 있다.	포함(b,a)
커버드비	${\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에 놓여있다. 다른 정의: "b에 적어도 하나의 점이 있고 b의 외관에 있는 점이 없다" 또는 "a의 모든 점은 b의 (내부 또는 경계)의 점"이다.	커버(b,a)
커버드비	`TFF**`	`TFF**`	`*FTF***`	`*FTF***`		커버(b,a)

입력 차원을 활용하고 {0,1,T,*} 도메인의 마스크로 정의되는 술어:

십자가

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

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

( )

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

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

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

(

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

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

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

또는

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

딤(any) = 1

{\displaystyle {\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} &\mathrm {*} &\mathrmatrm {*} &\mathrmatrm {*} &\mathr} \end{smatrix}{bigr}}}}}}}}}}}\matmatmatmatrix}}{bigr}\bigr.

{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} &\mathrm {*} &\mathrmatrm {*} &\mathrmatrm {*} &\mathr} \end{smatrix}{bigr}}}}}{bigr}}}}{bigr}\matrix}

{\displaystyle {\begin{smallmatrix}\mathrm {0} &\mathrm {*} &\mathrm {*} &\mathrm {*} &\mathrmatr {*} &\mathrmatrm {*} &\mathr} \end{smatrix{bigr}}}}}}}}}}}}}}}}}}}}}}}}}}}\mathr}\matrix {smatrix {smatrix \m

a cross b: 그들은 일부지만 모든 내부 지점이 공통적인 것은 아니며, 교차점의 치수는 적어도 하나 이상의 지점보다 작다. 마스크 선택 규칙은 선/선 입력을 제외하고

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

( )

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

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

(

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

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

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

이

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

가) 잘못된 경우에만 확인되며 그렇지 않은 경우:^[11]

(II =0)

라인의 경우, (

II

ie

IE

)

\dim(a)<\dim(b)

때 (

\dim(a)<\dim(b)

IE)

\dim(a)<\dim(b)

(

\dim(a)<\dim(b)

dim ( b )

\dim(a)>\dim(b)

>

\dim(a)>\dim(b)

때 (

\dim(a)>\dim(b)

dim(

a

)

\dim(a)>\dim(b)

dim(b)

,

\dim(a)<\dim(b)

(

II

∧

EI)

displaysty \dim(a)\dim(b)

(10)

T*T******
$\displaystyle \cHB(a)}$ T*****T**
$[\displaystyle \property(a)]\properties(b)}$ 0********
$딤(any) = 1$

\dim(a)=\dim(b)

\dim(a)=\dim(b)

(

\dim(a)=\dim(b)

)

\dim(a)=\dim(b)

=

\dim(a)=\dim(b)

(

\dim(a)=\dim(b)

)

\dim(a)=\dim(b)

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

{\displaystyle {\begin{smallmatrix}\mathrm {1} &\mathrm {*} &\mathrm {*} &\mathrm {*} &\mathrmatrm {*} &\mathrmatrm {*} &\mathr} \end{smatrix}{bigr}}}}{bigr}}}}}}}}}}}{bigr.

a 중첩 b: 그들은 일부지만 모든 공통점은 가지고 있지 않고, 같은 치수를 가지고 있으며, 두 기하학의 내부 교차점은 기하학 그 자체와 같은 치수를 가지고 있다.

\dim(a)=\dim(b)

dim ( )

\dim(a)=\dim(b)

=

\dim(a)=\dim(b)

\dim(a)=\dim(b)

( b

\dim(a)=\dim(b)

)

\dim(a)=\dim(b)

이

\dim(a)=\dim(b)

가) 거짓인 경우에만 마스크 선택 규칙이 확인됨:

(II

∧

IE

∧

EI)

점 또는 표면의 경우 (

II =1

ie

IE i

EI

)

(11)

T*T***T**
$딤 = 0 또는 2$ 1*T***T**
$딤 = 1$

다음 사항에 유의하십시오.

위상학적으로 동등한 정의는 같은 점을 가지고 있거나 심지어 같은 등급이라는 것을 의미하지 않는다.

$\operatorname {DE-9IM} (a,b)$ $\operatorname {DE-9IM} (a,b)$ - $\operatorname {DE-9IM} (a,b)$ $\operatorname {DE-9IM} (a,b)$ $\operatorname {DE-9IM} (a,b)$ $\operatorname {DE-9IM} (a,b)$ ( a $\operatorname {DE-9IM} (a,b)$ , $\operatorname {DE-9IM} (a,b)$ ) ${\displaystyle \operatorname {DE-9$ 출력 $IM}(a,b)}$ 에는 기하학적 a와 b에 대한 해석 가능한 모든 술어의 목록에 포함된 정보가 있다 $\operatorname {DE-9IM} (a,b)$ .

모든 술어는 마스크로 계산한다. $\dim(a)$ 및 겹침에만 $\dim(a)$ ) $\dim(a)$ 및 $\dim(a)$ $\dim(b)$ $\dim(b)$ 에 대한 추가 조건이 있다 $\dim(b)$

모든 마스크 문자열 코드는 다음으로 끝남 *이것은 EE가 사소한 사실이기 때문에 유용한 정보를 제공하지 않기 때문이다.

Equals 마스크, T*F**FFF*는 포함의 "merge"이다(T*****FF*) 및 내부 ()T*F**F***): ( $II$ $\land$ ~ $EI$ $\land$ ~ $EBE) \land$ ( $II$ $\land$ ~ $IE$ $\land$ ~ $BE)$

마스크 T*****FF* 포함 및 덮개의 정의에서 발생한다. 커버는 좀 더 포괄적인 관계다. 특히 Include와는 달리 경계와 기하학적 내부에서의 점을 구분하지 않는다. 대부분의 경우 커버는 포함보다 우선하여 사용해야 한다.

마찬가지로 마스크도 T*F**F*** Inside 및 CoveredBy의 정의에서 발생한다. 대부분의 경우 Inside보다 CoveredBy를 사용해야 한다.

역사적으로, 공간 술어를 표현하기 위해 다른 용어들과 다른 공식적인 접근법이 사용되어왔다. 예를 들어 지역 연결 미적분은 랜델, 콘, 콘에 의해^[12] 1992년에 도입되었다.

특성.

공간 술어는 이항 관계의 다음과 같은 특성을 가지고 있다.

반사성: 등가, 포함, 덮개, 덮개, 교차점, 내부
반반복성: 불연속
대칭: 같음, 교차, 교차, 터치, 겹침
타동성: 등가, 포함, 커버, 커버, 커버드바이, 내부

해석

공간 관계의 예.

공간 술어에 대한 용어와 의미론의 선택은 합리적인 관습과 위상학 연구의 전통에 기초한다.^[4] 교차점, 불절음, 접촉, 내부, 등호(두 기하학적 a와 b 사이)와 같은 관계에는 분명한 의미가 있다.^[10]^[13]

등수: a = b: (a ∩ b = a) ( (a b b = b)
안쪽에: a ∩ b = a
교차점: ∩ b ≠ ∅ ∅
터치스: (a ∩ b ≠ ∅) ∧ (a^ο^ο b = ∅)

술어는 '포함'과 '내부'는 직관에 반하는 미묘한 측면을 가지고 있다. 예를 들어,^[10] 다각형 P의 경계에 완전히 포함되는 L 선은 P에 포함된 것으로 간주되지 않는다. 이 괴짜는 "폴리곤은 그들의 경계를 포함하지 않는다"라고 표현될 수 있다. 이 문제는 위의 '포함' 정의의 마지막 조항인 'B의 내부 중 적어도 한 지점은 A의 내부에 있다'에 의해 발생한다. 이 경우에, 용어 커버는 경계 고려를 피하면서 더 직관적인 의미론(정의 참조)을 가지고 있다.

보다 나은 이해를 위해 입력물의 차원성은 의미 복잡성의 점진적 도입을 위한 정당성으로 사용될 수 있다.

사이의 관계	적절한 술어	의미 추가됨
포인트/포인트	등가, 분리	다른 유효한 술어는 동등으로 붕괴된다.
포인트/라인	교차점 추가	교차점은 등가: "선상에서 같은 점"의 정교함이다.
줄/줄	터치, 크로스, ...	Touch는 "경계"에 대해서만 Crosses를 정교하게 다듬은 것이다. 크로스는 "단 1점"에 관한 것이다.

가능한 매트릭스 결과에 대한 적용 범위

부울 9가 될 수 있는 결과 수IM 행렬은 2⁹=512이고 DE-9에서IM 매트릭스는⁹ 3=6561이다. 특정 술어를 만족시키는 이러한 결과의 백분율은 다음과 같이 결정된다.

확률	이름
93.7%	교차점
43.8%	터치스
25%	교차(유효한 입력의 경우, 그렇지 않은 경우 0%)
23.4%	커버 및 커버드바이
12.5%	포함, 중복(유효한 입력의 경우 0%) 및 내부
6.3%	디스조인트
3.1%	등수

일반적인 용도에서 기하학적 구조는 선험적 요소와 교차하며, 다른 관계를 점검한다.

복합 술어 "간격 OR Disjoint"와 "Equals OR Differences"는 합계가 100%(항상 참된 술어)이지만 "Covers OR CoveredBy"는 41%로, 독립적 관계를 모두 논리적 보완이 아니기 때문에 합계가 아니다. idem "내부 OR 포함"는 21%이다. 25%+12.5%=37.5%의 합은 유효한 입력 세트가 분리되어 있기 때문에 "교차 OR 중복"에서 라인의 중복을 무시할 때 얻는다.

질의 및 주장

DE-9IM은 두 입력 기하학에 대해 완전한 서술적 주장을 제공한다. 그것은 진리표, 삼원 비교, 카노 지도 또는 벤 도표와 같은 두 실체에 대해 가능한 모든 관계의 완전한 집합을 나타내는 수학적 함수다. 각 출력 값은 특정 입력의 관계를 나타내는 진실 표 선과 같다.

위에서 설명한 것처럼 DE-9IM(a,b)에서 도출된 출력 '2121012'는 특정 기하학적 a와 b 사이의 모든 토폴로지 관계에 대한 완전한 설명이다. It says to us that $II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2$ .

다른 한편으로는, 만약 우리가 Crosses(a,b)나 Touchs(a,b)와 같은 술어를 체크한다면, 같은 예에서 우리는 "Intersects=true and Touch=true"를 가지고 있다. 이것은 "모든 토폴로지 관계"에 대한 불완전한 설명이다. 술어는 기하학의 차원성에 대해서도 아무 말도 하지 않는다(a와 b가 선, 영역 또는 점인 것은 중요하지 않다).

술어에 대한 기하형식의 독립성과 완전성의 결여는 다음 두 가지 기하형상에 대한 일반적인 질의에 유용하다.

	내적/내적/내적 의미론적 의미	통상적인 의미론
주장	좀 더 서술적인 " a와 b는 $DE-9IM(a, b)='2121012'$ 를 갖는다."	덜 서술적인 " a Touch b "
쿼리	더 제한적인 " $DE-9IM(a, b)='2121012'$ 가 있는 모든 기하학적 구조를 표시하십시오."	보다 일반적 " Touch(a,b)가 "인 모든 기하학 쌍을 표시하십시오.

일반적인 용도의 경우, 공간 술어의 사용은 또한 DE-9보다 사람이 더 잘 읽을 수 있는 것으로 정당화된다.IM 설명: 일반적인 사용자는 술어에 대해 더 나은 직관을 가지고 있다(내부/국경/외부 교차점 집합보다).

술어는 일반적인 응용 프로그램에 유용한 의미론을 가지고 있으므로 DE-9의 번역이 유용하다.IM을 관련된 모든 술어의 목록에 기술하는 것은 ^[14]^[15]두 개의 다른 의미 유형들 사이의 주조 과정과 같다. 예:

문자열 코드 "0F1F00102" 및 "0F1"FF0102"는 "인터섹스 & 크로스 & 오버랩"의 의미를 갖는다.
문자열 코드 "1FFF0FF2"는 "Equals"의 의미를 갖는다.
문자열 코드 "F01FF0102", "FF10F0102", "FF1F00102", "F01FFF102", "FF1F1F2"는 "절개 & 터치"의 의미를 갖는다.

표준

OGC(Open Geospatial Consortium)는 대표적인 공간 술어(Continents, Cross, Crosss, Touchs 등)를 부울 함수로 표준화하였으며, DE-9는 DE-9이다.IM 모델,^[16] 문자열을 반환하는 함수(DE-9)IM 코드)는 0=포인트, 1=라인, 2=면적, F="빈 집합"을 의미하는 {0,1,2,F} 도메인의 경우. 이번 DE-9IM 문자열 코드는 데이터 교환을 위한 표준화된 형식이다.

Simple Feature Access(^[17]ISO 19125) 표준은 7.2.8장 "유형 지오메트리의 SQL 루틴"에서 SQL/MM Spatial^[18](ISO 13249-3 Part 3: Spatial) ST_Dimension, ST_Geometry를 지원되는 루틴으로 권장한다.모든 지오메트리 유형에 대한 유형, ST_IsSimple, ST_Boundary. The same standard, consistent with the definitions of relations in "Part 1, Clause 6.1.2.3" of the SQL/MM, recommends (shall be supported) the function labels: ST_Equals, ST_Disjoint, ST_Intersects, ST_Touches, ST_Crosses, ST_Within, ST_Contains, ST_Overlaps and ST_Relate.

DE-9OGC 표준의 IM은 주요 OGC 표준 기하학적 형태에 대해 내부 및 경계 정의를 사용한다.^[19]

하위 유형	어둡다	실내( $I$ )	경계( $B$ )
점, 멀티포인트	0	점, 점	비어 있음
라인스트링, 라인	1	경계점이 제거될 때 남아 있는 점.	두 개의 끝점.
선형 링	1	지오메트리를 따라 있는 모든 점.	비어 있다.
멀티라인 스트링	1	경계점이 제거될 때 남아 있는 점.	원소의 홀수(곡선)의 경계에 있는 점.
폴리곤	2	반지 안의 포인트.	반지 세트.
멀티폴리곤	2	반지 안의 포인트.	원소의 링 세트(폴리곤)
주의사항: 외부 점(E)은 내부 또는 경계에 없는 점 p이므로 추가 해석이 필요하지 않음, E(p)=not(I(p) 또는 B(p)

구현 및 실제 사용

포스트와 같은 대부분의 공간 데이터베이스GIS, 표준 기능에 의해 DE-9IM() 모델을 구현한다.^[20] ST_Relate, ST_Equals, ST_Intersects, 등. 기능 ST_Relate(a,b) 표준 OGC의 DE-9 출력IM 문자열 코드.

Examples: two geometries, a and b, that intersects and touches with a point (for instance with $\dim(B(a)\cap I(b))=0$ and ${\displaystyle \dim(I(a)\cap I(b))$ $=F}$ )) $\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 코드는 "Intersects(a,b) & Cross(a,b) & Inner(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_Realate()를 사용하는 것이 복잡한 술어를 계산하는 유일한 방법인 경우가 있다 — 코드의 예 참조 0FFFFF0F2다중점(점 집합인 객체)을 "교차"하지 않고 십자(마스크로 정의한 경우)라는 술어가 참으로 반환되는 지점의 경우.^[21]

일반적으로 마스크 파라미터를 추가하여 ST_Realate()에 과부하를 가하거나, 반환된 ST_Realate(a,b) 문자열을 ST_RealateMatch() 함수에 사용하는 것이 일반적이다.^[22] 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') 거짓이다.

동의어

"Egenhofer-Matrix"는 부울 도메인의 9IM 3x3 매트릭스와 동의어다.^[23]
"클레멘티니 매트릭스"는 DE-9의 동의어다.{0,1,2,F} 도메인의 IM 3x3 매트릭스.^[23]
"Egenhofer 연산자"와 "Clementini 연산자"는 부울 연산에 사용할 수 있는 II, IE 등으로 매트릭스 요소를 참조하는 경우가 있다. 예: "G₁₂ 포함 G"라는 술어는 "⟨ $G 1$ $II \land ~EI \land ~EB G 1$ ⟩"로 표현할 수 있으며, 이는 마스크 구문으로 번역될 수 있다. T*****FF*.
술어 "미트"는 터치의 동의어, "내부"는 내면의 동의어다.
오라클의 "ANYINTERACT"는^[15] 교차점의 동의어, "OverlapBDYINTERGET"는 중복의 동의어다. 그것의 "OverlapBDYDISJONE"에는 해당 명명된 술어가 없다.
지역 연결에서 미적분 연산자는 술어에 대한 몇 가지 동의어를 제공한다. 즉, Disconnection은 DC(연결되지 않음), touch는 EC(영구적으로 연결됨), eQ(동일함. 기타, PO로서 겹침(부분적으로 겹침)과 같이, 상황에 맞는 분석이나 구성이 필요하다.^[24]^[25]

참고 항목

표준:

소프트웨어:

공간 데이터베이스
객체 기반 공간 데이터베이스
FOSS:
- JTS 토폴로지 제품군
- GRASS GIS
- GDAL(도서관)
- PostGIS

참조

^ Clementini, Eliseo; Di Felice, Paolino; van Oosterom, Peter (1993). "A small set of formal topological relationships suitable for end-user interaction". In Abel, David; Ooi, Beng Chin (eds.). Advances in Spatial Databases: Third International Symposium, SSD '93 Singapore, June 23–25, 1993 Proceedings. Lecture Notes in Computer Science. 692/1993. Springer. pp. 277–295. doi:10.1007/3-540-56869-7_16. ISBN 978-3-540-56869-8.
^ Clementini, Eliseo; Sharma, Jayant; Egenhofer, Max J. (1994). "Modelling topological spatial relations: Strategies for query processing". Computers & Graphics. 18 (6): 815–822. doi:10.1016/0097-8493(94)90007-8.
^ Egenhofer, M.J.; Franzosa, R.D. (1991). "Point-set topological spatial relations". Int. J. GIS. 5 (2): 161–174. doi:10.1080/02693799108927841.
^ Jump up to: ^a ^b ^c ^d Egenhofer, M.J.; Herring, J.R. (1990). "A Mathematical Framework for the Definition of Topological Relationships" (PDF). Archived from the original (PDF) on 2010-06-14. Cite 저널은 필요로 한다. journal= (도움말)
^ "OpenGIS Simple Features Specification for SQL" 개정 1.1은 1999년 5월 5일에 발표되었다. DE-9 포맷 규약을 확립한 최초의 국제 표준이었다.IM 문자열 코드 및 "DE-9IM 기반의 명명된 공간 관계 술어" 이름(이 제목이 있는 섹션 참조)
^ M. J. 에겐호퍼, J. 샤르마, D. 마크(1993) "공간 관계에 대한 4-절과 9-절 모델의 비판적 비교: 공식 분석 웨이백 머신에 보관" 2010-06-14", In: Auto-Carto XI 웨이백 머신에 보관 2014-09-25
^ Jump up to: ^a ^b 제4장 포스트 사용GIS: 데이터 관리 및 쿼리
^ JTS: Class IntersectionMatrix, Vivid Solutions, Inc., archived from the original on 2011-03-21
^ JTS 기술 사양 2003.
^ Jump up to: ^a ^b ^c M. Davis(2007) "Contents' Spatial 술어의 수량".
^ ST_크로스
^ Randell, D.A.; Cui, Z; Cohn, A.G. (1992). "A spatial logic based on regions and connection". 3rd Int. Conf. on Knowledge Representation and Reasoning. Morgan Kaufmann. pp. 165–176.
^ Câmara, G.; Freitas, U. M.; Casanova, M. A. (1995). "Fields and Objects Algebras for GIS Operations". CiteSeerX 10.1.1.17.991. Cite 저널은 필요로 한다. journal= (도움말)
^ DE-9IM 변환기, 모든 관련 공간 관계 술어.
^ Jump up to: ^a ^b 참고. Oracle의 공간 펑션 SSO_REALATE() 2013-07-21 Wayback Machine에서 아카이브된 2013-07-21은 내부적으로 부분 변환만 수행하므로 DE-9 대신 사용자가 술어의 또는 목록을 확인할 수 있도록 마스크 제공IM 스트링.
^ "OpenGIS 구현 사양 지리 정보 - 단순 기능 액세스 - Part 2: SQL 옵션", OGC, http://www.opengeospatial.org/standards/sfs
^ 오픈 지리공간 컨소시엄 주식회사(2007), "오픈"GIS® 지리정보 구현 표준 - 단순 기능 액세스 - Part 2: SQL 옵션", OGC 문서 06-104r4 버전 1.2.1(2010-08-04 검토)
^ ISO 13249-3 제3부: 공간, SQL 멀티미디어 및 애플리케이션 패키지(SQL/MM) 웨이백 머신에 2010-02-14 보관.
^ 샤시 셰카르와 후이 시옹이 편집한 「GIS의 백과사전」. 스프링거사이언스 2008. 페이지 242
^ ST_Relate() PostGIS 함수의 온라인 설명서.
^ "B 지점 중 하나에 A 지점"의 JTS 테스트 사례, http://www.vividsolutions.com/jts/tests/Run1Case4.html 웨이백 머신에 2016-03-04 보관
^ ST_RealateMatch() PostGIS 함수의 온라인 설명서.
^ Jump up to: ^a ^b "GIS의 백과사전" S. 셰카르, H. 시옹. 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

외부 링크

[1] Clementini, Eliseo; Di Felice, Paolino; van Oosterom, Peter (1993). "A small set of formal topological relationships suitable for end-user interaction". In Abel, David; Ooi, Beng Chin (eds.). Advances in Spatial Databases: Third International Symposium, SSD '93 Singapore, June 23–25, 1993 Proceedings. Lecture Notes in Computer Science. 692/1993. Springer. pp. 277–295. doi:10.1007/3-540-56869-7_16. ISBN 978-3-540-56869-8.

[2] Clementini, Eliseo; Sharma, Jayant; Egenhofer, Max J. (1994). "Modelling topological spatial relations: Strategies for query processing". Computers & Graphics. 18 (6): 815–822. doi:10.1016/0097-8493(94)90007-8.

[3] Egenhofer, M.J.; Franzosa, R.D. (1991). "Point-set topological spatial relations". Int. J. GIS. 5 (2): 161–174. doi:10.1080/02693799108927841.

[sdh1990-4] Jump up to: ^a ^b ^c ^d Egenhofer, M.J.; Herring, J.R. (1990). "A Mathematical Framework for the Definition of Topological Relationships" (PDF). Archived from the original (PDF) on 2010-06-14. Cite 저널은 필요로 한다. journal= (도움말)

[firstStd-5] "OpenGIS Simple Features Specification for SQL" 개정 1.1은 1999년 5월 5일에 발표되었다. DE-9 포맷 규약을 확립한 최초의 국제 표준이었다.IM 문자열 코드 및 "DE-9IM 기반의 명명된 공간 관계 술어" 이름(이 제목이 있는 섹션 참조)

[4vs9-6] M. J. 에겐호퍼, J. 샤르마, D. 마크(1993) "공간 관계에 대한 4-절과 9-절 모델의 비판적 비교: 공식 분석 웨이백 머신에 보관" 2010-06-14", In: Auto-Carto XI 웨이백 머신에 보관 2014-09-25

[PostGISch4-7] Jump up to: ^a ^b 제4장 포스트 사용GIS: 데이터 관리 및 쿼리

[8] JTS: Class IntersectionMatrix, Vivid Solutions, Inc., archived from the original on 2011-03-21

[9] JTS 기술 사양 2003.

[davis2007-10] Jump up to: ^a ^b ^c M. Davis(2007) "Contents' Spatial 술어의 수량".

[ST_Crosses-11] ST_크로스

[12] Randell, D.A.; Cui, Z; Cohn, A.G. (1992). "A spatial logic based on regions and connection". 3rd Int. Conf. on Knowledge Representation and Reasoning. Morgan Kaufmann. pp. 165–176.

[cafrca-13] Câmara, G.; Freitas, U. M.; Casanova, M. A. (1995). "Fields and Objects Algebras for GIS Operations". CiteSeerX 10.1.1.17.991. Cite 저널은 필요로 한다. journal= (도움말)

[14] DE-9IM 변환기, 모든 관련 공간 관계 술어.

[SDO_RELATE-15] Jump up to: ^a ^b 참고. Oracle의 공간 펑션 SSO_REALATE() 2013-07-21 Wayback Machine에서 아카이브된 2013-07-21은 내부적으로 부분 변환만 수행하므로 DE-9 대신 사용자가 술어의 또는 목록을 확인할 수 있도록 마스크 제공IM 스트링.

[ogs1-16] "OpenGIS 구현 사양 지리 정보 - 단순 기능 액세스 - Part 2: SQL 옵션", OGC, http://www.opengeospatial.org/standards/sfs

[SFS2007-17] 오픈 지리공간 컨소시엄 주식회사(2007), "오픈"GIS® 지리정보 구현 표준 - 단순 기능 액세스 - Part 2: SQL 옵션", OGC 문서 06-104r4 버전 1.2.1(2010-08-04 검토)

[18] ISO 13249-3 제3부: 공간, SQL 멀티미디어 및 애플리케이션 패키지(SQL/MM) 웨이백 머신에 2010-02-14 보관.

[19] 샤시 셰카르와 후이 시옹이 편집한 「GIS의 백과사전」. 스프링거사이언스 2008. 페이지 242

[20] ST_Relate() PostGIS 함수의 온라인 설명서.

[test1case4-21] "B 지점 중 하나에 A 지점"의 JTS 테스트 사례, http://www.vividsolutions.com/jts/tests/Run1Case4.html 웨이백 머신에 2016-03-04 보관

[22] ST_RealateMatch() PostGIS 함수의 온라인 설명서.

[encygis-23] Jump up to: ^a ^b "GIS의 백과사전" S. 셰카르, H. 시옹. ISBN 978-0-387-35975-5

[24] 다차원 지역연계 미적분(2017), http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf

[25] "지역연계 미적분학에서의 관계식별: 9-간격 3+ -간격 술어로 감소"(2013), https://web.archive.org/web/20181001104247/https://pdfs.semanticscholar.org/8184/abc9b25ed340f9195cc904249bda415bb0c3.pdf

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

Search