Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
DE-9IM
open-in-new
<h2 id="matrix-model">Matrix model</h2> <p>The DE-9IM model is based on a 3×3 <a href="/facts/Intersection/hVW6QFWD">intersection</a> <a href="/facts/Matrix_(mathematics)/qa8FI4ko">matrix</a> with the form: </p> <table><tbody><tr><td> DE9IM ( a , b ) = [ dim ( I ( a ) ∩ I ( b ) ) dim ( I ( a ) ∩ B ( b ) ) dim ( I ( a ) ∩ E ( b ) ) dim ( B ( a ) ∩ I ( b ) ) dim ( B ( a ) ∩ B ( b ) ) dim ( B ( a ) ∩ E ( b ) ) dim ( E ( a ) ∩ I ( b ) ) dim ( E ( a ) ∩ B ( b ) ) dim ( E ( a ) ∩ E ( b ) ) ] {\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}}} </td> <td></td> <td>1</td></tr></tbody></table> <p>where dim {\displaystyle \dim } is the <a href="/facts/Dimension/0ktmUyac">dimension</a> of the <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> (∩) of the <a href="/facts/Interior_of_a_manifold/rXPERJtu">interior</a> (I), <a href="/facts/Boundary_of_a_manifold/rXPERJtu">boundary</a> (B), and <a href="/facts/Exterior_(topology)/qA5bnjxm">exterior</a> (E) of geometries <i>a</i> and <i>b</i>. </p><p>The terms <i>interior</i> and <i>boundary</i> in this article are used in the sense used in algebraic topology and manifold theory, not in the sense used in general topology: for example, the interior of a line segment is the line segment without its endpoints, and its boundary is just the two endpoints (in general topology, the interior of a line segment in the plane is empty and the line segment is its own boundary). </p><p>In the notation of topological space operators, the matrix elements can be expressed also as </p> <table><tbody><tr><td><i>I</i>(<i>a</i>)=<i>a</i>o <i>B</i>(<i>a</i>)=∂<i>a</i> <i>E</i>(<i>a</i>)=<i>a</i><i>e</i></td> <td></td> <td>2</td></tr></tbody></table> <p>The dimension of <a href="/facts/Empty_set/ffEk3eA6">empty sets</a> (∅) are denoted as −1 or F (false). The dimension of non-empty sets (¬∅) are denoted with the maximum number of dimensions of the intersection, specifically 0 for <a href="/facts/Point_(geometry)/6YPAvX2a">points</a>, 1 for <a href="/facts/Line_(geometry)/gJqsr4Gj">lines</a>, 2 for <a href="/facts/Area/KsNG1G9t">areas</a>. Then, the <a href="/facts/Data_domain/4oDqjYsd">domain</a> of the model is {0,1,2,F}. </p><p>A simplified version of dim ( x ) {\displaystyle \dim(x)} values are obtained mapping the values {0,1,2} to T (true), so using the <a href="/facts/Boolean_domain/9cYq9TC1">boolean domain</a> {T,F}. The matrix, denoted with operators, can be expressed as </p> <table><tbody><tr><td> bin ( DE9IM ( a , b ) ) = 9IM ( a , b ) = [ a o ∩ b o ≠ ∅ a o ∩ ∂ b ≠ ∅ a o ∩ b e ≠ ∅ ∂ a ∩ b o ≠ ∅ ∂ a ∩ ∂ b ≠ ∅ ∂ a ∩ b e ≠ ∅ a e ∩ b o ≠ ∅ a e ∩ ∂ b ≠ ∅ a e ∩ b e ≠ ∅ ] {\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}}} </td> <td></td> <td>3</td></tr></tbody></table> <p>The elements of the matrix can be named as shown below: </p> <table><tbody><tr><td> [ I I I B I E B I B B B E E I E B E E ] {\displaystyle {\begin{bmatrix}II&IB&IE\\BI&BB&BE\\EI&EB&EE\end{bmatrix}}} </td> <td></td> <td>4</td></tr></tbody></table> <p>Both matrix forms, with dimensional and boolean domains, can be <a href="/facts/Serialization/T00auFvv">serialized</a> as "<i>DE-9IM string codes</i>", which represent them in a single-line string pattern. Since 1999 the <i>string codes</i> have a standard<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> format. </p><p>For output checking or pattern analysis, a matrix value (or a string code) can be checked by a "<a href="/facts/Mask_(computing)/d9Cu1A1Y">mask</a>": a desired output value with optional <a href="/facts/Asterisk/qwmtPW5V">asterisk</a> symbols as <a href="/facts/Wildcard_character/LErwSxvh">wildcards</a> — that is, "*" indicating output positions that the designer does not care about (free values or "don't-care positions"). The domain of the mask elements is {0,1,2,F,*}, or {T,F,*} for the boolean form. </p><p>The simpler models <i>4-Intersection</i> and <i>9-Intersection</i> were proposed before DE-9IM for expressing <i>spatial relations</i><a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> (and originated the terms <i>4IM</i> and <i>9IM</i>). They can be used instead of the DE-9IM to optimize computation when input conditions satisfy specific constraints. </p> <h3>Illustration</h3> <p>Visually, for two overlapping polygonal geometries, the result of the function DE_9IM(<i>a</i>,<i>b</i>) looks like:<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a> </p> <table><tbody><tr><td></td><td><table><tbody><tr><td><i>b</i> </td></tr></tbody></table></td></tr><tr><td><table><tbody><tr><td><i>a</i></td></tr></tbody></table></td><td><table><tbody><tr><th></th><th>Interior</th><th>Boundary</th><th>Exterior</th></tr><tr><td>Interior</td><td><p> dim [ I ( a ) ∩ I ( b ) ] = 2 {\displaystyle \dim[I(a){\color {red}\cap }I(b)]=2} </p></td><td><p> dim [ I ( a ) ∩ B ( b ) ] = 1 {\displaystyle \dim[I(a){\color {red}\cap }B(b)]=1} </p></td><td><p> dim [ I ( a ) ∩ E ( b ) ] = 2 {\displaystyle \dim[I(a){\color {red}\cap }E(b)]=2} </p></td></tr><tr><td>Boundary</td><td><p> dim [ B ( a ) ∩ I ( b ) ] = 1 {\displaystyle \dim[B(a){\color {red}\cap }I(b)]=1} </p></td><td><p> dim [ B ( a ) ∩ B ( b ) ] = 0 {\displaystyle \dim[B(a){\color {red}\cap }B(b)]=0} </p></td><td><p> dim [ B ( a ) ∩ E ( b ) ] = 1 {\displaystyle \dim[B(a){\color {red}\cap }E(b)]=1} </p></td></tr><tr><td>Exterior</td><td><p> dim [ E ( a ) ∩ I ( b ) ] = 2 {\displaystyle \dim[E(a){\color {red}\cap }I(b)]=2} </p></td><td><p> dim [ E ( a ) ∩ B ( b ) ] = 1 {\displaystyle \dim[E(a){\color {red}\cap }B(b)]=1} </p></td><td><p> dim [ E ( a ) ∩ E ( b ) ] = 2 {\displaystyle \dim[E(a){\color {red}\cap }E(b)]=2} </p></td></tr></tbody></table></td></tr></tbody></table> <p>This matrix can be <a href="/facts/Serialization/T00auFvv">serialized</a>. Reading from left-to-right and top-to-bottom, the result is I I = 2 , I B = 1 , I E = 2 , B I = 1 , B B = 0 , B E = 1 , E I = 2 , E B = 1 , E E = 2 {\displaystyle 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'. </p> <h2 id="spatial-predicates">Spatial predicates</h2> <p>Any <a href="/facts/Topological_property/vbJR18Sx">topological property</a> based on a DE-9IM <a href="/facts/Binary_relation/r9BwGgaK">binary</a> <a href="/facts/Spatial_relation/6RFIl1ul">spatial relation</a> is a spatial predicate. For ease of use "named spatial predicates" have been defined for some common relations, which later became standard predicates. The <i>spatial predicate <a href="/facts/Subroutine/9vFJrg0A">functions</a></i> that can be derived from DE-9IM include:<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> <a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> </p> Predicates defined with masks of domain {T,F,*}: <table><tbody><tr><th>Name (synonym)</th><th colspan="4">Intersection matrix and mask code string(<a href="/facts/Boolean_algebra/VkCToAmg">boolean OR</a> between matrices)</th><th>Meaning and definition<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a></th><th>Equivalent</th></tr><tr><th rowspan="2">Equals</th><td colspan="4"> [ T ∗ F ∗ ∗ F F F ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><table><tbody><tr><td><i>II</i> ∧ ~<i>IE</i> ∧ ~<i>BE</i> ∧ ~<i>EI</i> ∧ ~<i>EB</i></td> <td></td> <td>5</td></tr></tbody></table><i>a</i> and <i>b</i> are topologically <a href="/facts/Equality_(relational_operator)/nTXrhxN2">equal</a>. "Two geometries are topologically equal if their interiors intersect and no part of the interior or boundary of one geometry intersects the exterior of the other".<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a></td><td rowspan="2"><i>Within</i> & <i>Contains</i></td></tr><tr><td>T*F**FFF*</td><td></td><td></td><td></td></tr><tr><th rowspan="2">Disjoint</th><td colspan="4"> [ F F ∗ F F ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><table><tbody><tr><td><i>~II</i> ∧ ~<i>IB</i> ∧ ~<i>BI</i> ∧ ~<i>BB</i></td> <td></td> <td>6</td></tr></tbody></table><i>a</i> and <i>b</i> are <a href="/facts/Disjoint_sets/nLr8XRVd">disjoint</a>: they have no points in common. They form a set of <a href="/facts/Disconnected_(topology)/5CUTxfoA">disconnected</a> geometries.</td><td rowspan="2"><i>not Intersects</i></td></tr><tr><td>FF*FF****</td><td></td><td></td><td></td></tr><tr><th rowspan="2">Touches(meets)</th><td> [ F T ∗ ∗ ∗ ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ F ∗ ∗ T ∗ ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td colspan="2"> [ F ∗ ∗ ∗ T ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><table><tbody><tr><td><i>~II</i> ∧ (<i>IB</i> ∨ <i>BI</i> ∨ <i>BB</i>)</td> <td></td> <td>7</td></tr></tbody></table><i>a</i> touches <i>b</i>: they have at least one point in common, but their interiors do not intersect.</td><td rowspan="2"></td></tr><tr><td>FT*******</td><td>F**T*****</td><td colspan="2">F***T****</td></tr><tr><th rowspan="2">Contains</th><td colspan="4"> [ T ∗ ∗ ∗ ∗ ∗ F F ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><table><tbody><tr><td><i>II</i> ∧ ~<i>EI</i> ∧ ~<i>EB</i></td> <td></td> <td>8</td></tr></tbody></table><i>a</i> contains <i>b</i>: geometry <i>b</i> lies in <i>a</i>, and the interiors intersect. Another definition: "<i>a</i> contains <i>b</i> <a href="/facts/If_and_only_if/bYSxGJ66">iff</a> no points of <i>b</i> lie in the exterior of <i>a</i>, and at least one point of the interior of <i>b</i> lies in the interior of <i>a</i>".<a class="footnote-ref" id="fnref:12" href="#fn:12"><sup>12</sup></a></td><td rowspan="2"><i>Within</i>(<i>b</i>,<i>a</i>)</td></tr><tr><td colspan="4">T*****FF*</td></tr><tr><th rowspan="2">Covers</th><td> [ T ∗ ∗ ∗ ∗ ∗ F F ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ T ∗ ∗ ∗ ∗ F F ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ ∗ ∗ T ∗ ∗ F F ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ ∗ ∗ ∗ T ∗ F F ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><table><tbody><tr><td>(<i>II</i> ∨ <i>IB</i> ∨ <i>BI</i> ∨ <i>BB</i>) ∧ ~<i>EI</i> ∧ ~<i>EB</i></td> <td></td> <td>9</td></tr></tbody></table><i>a</i> covers <i>b</i>: geometry <i>b</i> lies in <i>a</i>. Other definitions: "At least one point of <i>b</i> lies in <i>a</i>, and no points of <i>b</i> lie in the exterior of <i>a</i>", or "Every point of <i>b</i> is a point of (the interior or boundary of) <i>a</i>".</td><td rowspan="2"><i>CoveredBy</i>(<i>b</i>,<i>a</i>)</td></tr><tr><td>T*****FF*</td><td>*T****FF*</td><td>***T**FF*</td><td>****T*FF*</td></tr></tbody></table> Predicates that can be obtained from the above by <a href="/facts/Negation/q5AQBvBj">logical negation</a> or parameter inversion (<a href="/facts/Transposed_matrix/8wmsagGS">matrix transposition</a>), as indicated by the last column: <table><tbody><tr><th rowspan="2">Intersects</th><td> [ T ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ T ∗ ∗ ∗ ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ ∗ ∗ T ∗ ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ ∗ ∗ ∗ T ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><i>a</i> <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersects</a> <i>b</i>: geometries <i>a</i> and <i>b</i> have at least one point in common.</td><td rowspan="2"><i>not Disjoint</i></td></tr><tr><td>T********</td><td>*T*******</td><td>***T*****</td><td>****T****</td></tr><tr><th rowspan="2">Within (inside)</th><td colspan="4"> [ T ∗ F ∗ ∗ F ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><i>a</i> is within <i>b</i>: <i>a</i> lies in the interior of <i>b</i>.</td><td rowspan="2"><i>Contains</i>(<i>b</i>,<i>a</i>)</td></tr><tr><td colspan="4">T*F**F***</td></tr><tr><th rowspan="2">CoveredBy</th><td> [ T ∗ F ∗ ∗ F ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ T F ∗ ∗ F ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ ∗ F T ∗ F ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ ∗ ∗ F ∗ T F ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {T} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2"><i>a</i> is covered by <i>b</i> (extends <i>Within</i>): geometry <i>a</i> lies in <i>b</i>. Other definitions: "At least one point of <i>a</i> lies in <i>b</i>, and no points of <i>a</i> lie in the exterior of <i>b</i>", or "Every point of <i>a</i> is a point of (the interior or boundary of) <i>b</i>".</td><td rowspan="2"><i>Covers</i>(<i>b</i>,<i>a</i>)</td></tr><tr><td>T*F**F***</td><td>*TF**F***</td><td>**FT*F***</td><td>**F*TF***</td></tr></tbody></table> Predicates that utilize the input dimensions, and are defined with masks of domain {0,1,T,*}: <table><tbody><tr><th rowspan="2">Crosses dim ( a ) ≠ dim ( b ) {\displaystyle \dim(a)\neq \dim(b)} or dim(any) = 1</th><td> [ T ∗ T ∗ ∗ ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td> [ T ∗ ∗ ∗ ∗ ∗ T ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td colspan="2"> [ 0 ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {0} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2" colspan="2"><i>a</i> crosses <i>b</i>: they have some but not all interior points in common, and the dimension of the intersection is less than that of at least one of them. The following mask selection rules must only be checked when dim ( a ) ≠ dim ( b ) {\displaystyle \dim(a)\neq \dim(b)} (except for line / line inputs, which <i>are</i> allowed), otherwise the predicate is false:<a class="footnote-ref" id="fnref:13" href="#fn:13"><sup>13</sup></a><table><tbody><tr><td>(<i>II</i>=0) for lines, (<i>II</i> ∧ <i>IE</i>) when dim ( a ) < dim ( b ) {\displaystyle \dim(a)<\dim(b)} , (<i>II</i> ∧ <i>EI</i>) when dim ( a ) > dim ( b ) {\displaystyle \dim(a)>\dim(b)} </td> <td></td> <td>10</td></tr></tbody></table></td></tr><tr><td>T*T****** dim ( a ) < dim ( b ) {\displaystyle \dim(a)<\dim(b)} </td><td>T*****T** dim ( a ) > dim ( b ) {\displaystyle \dim(a)>\dim(b)} </td><td colspan="2">0******** dim(any) = 1</td></tr><tr><th rowspan="2">Overlaps dim ( a ) = dim ( b ) {\displaystyle \dim(a)=\dim(b)} </th><td> [ T ∗ T ∗ ∗ ∗ T ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td colspan="3"> [ 1 ∗ T ∗ ∗ ∗ T ∗ ∗ ] {\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {1} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}} </td><td rowspan="2" colspan="2"><i>a</i> overlaps <i>b</i>: they have some but not all points in common, they have the same dimension, and the intersection of the interiors of the two geometries has the same dimension as the geometries themselves. The following mask selection rules must only be checked when dim ( a ) = dim ( b ) {\displaystyle \dim(a)=\dim(b)} , otherwise the predicate is false:<table><tbody><tr><td>(<i>II</i> ∧ <i>IE</i> ∧ <i>EI</i>) for points or surfaces, (<i>II</i>=1 ∧ <i>IE</i> ∧ <i>EI</i>) for lines</td> <td></td> <td>11</td></tr></tbody></table></td></tr><tr><td>T*T***T** dim = 0 or 2</td><td colspan="2">1*T***T** dim = 1</td></tr></tbody></table> <p>Notice that: </p> <ul><li>The <i>topologically equal</i> definition does not imply that they have the same points or even that they are of the same class.</li></ul> <ul><li>The output of D E - 9 I M ( a , b ) {\displaystyle \operatorname {DE-9IM} (a,b)} have the information contained in a list of all interpretable predicates about geometries <i>a</i> and <i>b</i>.</li></ul> <ul><li>All predicates are computed by masks. Only <i>Crosses</i> and <i>Overlaps</i> have additional conditions about dim ( a ) {\displaystyle \dim(a)} and dim ( b ) {\displaystyle \dim(b)} .</li></ul> <ul><li>All mask string codes end with *. This is because <i>EE</i> is trivially true, and thus provides no useful information.</li></ul> <ul><li>The <i>Equals</i> mask, T*F**FFF*, is the "merge" of <i>Contains</i> (T*****FF*) and <i>Within</i> (T*F**F***): (<i>II</i> ∧ ~<i>EI</i> ∧ ~<i>EB</i>) ∧ (<i>II</i> ∧ ~<i>IE</i> ∧ ~<i>BE</i>).</li></ul> <ul><li>The mask T*****FF* occurs in the definition of both <i>Contains</i> and <i>Covers</i>. <i>Covers</i> is a more inclusive relation. In particular, unlike <i>Contains</i> it does not distinguish between points in the boundary and in the interior of geometries. For most situations, <i>Covers</i> should be used in preference to <i>Contains</i>.</li></ul> <ul><li>Similarly, the mask T*F**F*** occurs in the definition of both <i>Within</i> and <i>CoveredBy</i>. For most situations, <i>CoveredBy</i> should be used in preference to <i>Within</i>.</li></ul> <ul><li>Historically, other terms and other formal approaches have been used to express <i>spatial predicates</i>; for example <a href="/facts/Region_connection_calculus/FPmhJrJ9">region connection calculus</a> was introduced in 1992 by<a class="footnote-ref" id="fnref:14" href="#fn:14"><sup>14</sup></a> Randell, Cohn and Cohn.</li></ul> <h3>Properties</h3> <p>The spatial predicates have the following properties of <a href="/facts/Binary_relation/r9BwGgaK">binary relations</a>: </p> <ul><li><a href="/facts/Reflexive_relation/NzTytEg9">Reflexive</a>: Equals, Contains, Covers, CoveredBy, Intersects, Within</li> <li><a href="/facts/Reflexive_relation/NzTytEg9">Anti-reflexive</a>: Disjoint</li> <li><a href="/facts/Symmetric_relation/ekCWDIAH">Symmetric</a>: Equals, Intersects, Crosses, Touches, Overlaps</li> <li><a href="/facts/Transitive_relation/9r90y50r">Transitive</a>: Equals, Contains, Covers, CoveredBy, Within</li></ul> <h3>Interpretation</h3> <p>The choice of terminology and semantics for the spatial predicates is based on reasonable conventions and the tradition of topological studies.<a class="footnote-ref" id="fnref:15" href="#fn:15"><sup>15</sup></a> Relationships such as <i>Intersects</i>, <i>Disjoint</i>, <i>Touches</i>, <i>Within</i>, <i>Equals</i> (between two geometries <i>a</i> and <i>b</i>) have an obvious semantic:<a class="footnote-ref" id="fnref:16" href="#fn:16"><sup>16</sup></a><a class="footnote-ref" id="fnref:17" href="#fn:17"><sup>17</sup></a> </p> <i>Equals</i> <i>a</i> = <i>b</i> that is (<i>a</i> ∩ <i>b</i> = <i>a</i>) ∧ (<i>a</i> ∩ <i>b</i> = <i>b</i>) <i>Within</i> <i>a</i> ∩ <i>b</i> = <i>a</i> <i>Intersects</i> <i>a</i> ∩ <i>b</i> ≠ ∅ <i>Touches</i> (<i>a</i> ∩ <i>b</i> ≠ ∅) ∧ (<i>a</i>ο ∩ <i>b</i>ο = ∅) <p>The predicates <i>Contains</i> and <i>Within</i> have subtle aspects to their definition which are contrary to intuition. For example,<a class="footnote-ref" id="fnref:18" href="#fn:18"><sup>18</sup></a> a line <i>L</i> which is completely contained in the boundary of a polygon <i>P</i> is <i>not</i> considered to be contained in <i>P</i>. This quirk can be expressed as "Polygons do not contain their boundary". This issue is caused by the final clause of the <i>Contains</i> definition above: "at least one point of the interior of B lies in the interior of A". For this case, the predicate <i>Covers</i> has more intuitive semantics (see definition), avoiding boundary considerations. </p><p>For better understanding, the dimensionality of inputs can be used as justification for a gradual introduction of semantic complexity: </p> <table><tbody><tr><th>Relations between</th><th>Appropriate predicates</th><th>Semantic added</th></tr><tr><td>point/point</td><td><i>Equals</i>, <i>Disjoint</i></td><td>Other valid predicates collapses into <i>Equals</i>.</td></tr><tr><td>point/line</td><td>adds <i>Intersects</i></td><td><i>Intersects</i> is a refinement of <i>Equals</i>: "some equal point at the line".</td></tr><tr><td>line/line</td><td>adds <i>Touches</i>, <i>Crosses</i>, ...</td><td><i>Touches</i> is a refinement of <i>Intersects</i>, about "boundaries" only. <i>Crosses</i> is about "only one point".</td></tr></tbody></table> <h3>Coverage on possible matrix results</h3> <p>The number of possible results in a boolean <i>9IM</i> matrix is 29=512, and in a DE-9IM matrix is 39=6561. The percentage of these results that satisfy a specific predicate is determined as following, </p> <table><tbody><tr><th scope="col">Probability</th><th scope="col">Name</th></tr><tr><td> 93.7%</td><td><i>Intersects</i></td></tr><tr><td> 43.8%</td><td><i>Touches</i></td></tr><tr><td> 25%</td><td><i>Crosses</i> (for valid inputs, 0% otherwise)</td></tr><tr><td> 23.4%</td><td><i>Covers</i> and <i>CoveredBy</i></td></tr><tr><td> 12.5%</td><td><i>Contains</i>, <i>Overlaps</i> (for valid inputs, 0% otherwise) and <i>Within</i></td></tr><tr><td> 6.3%</td><td><i>Disjoint</i></td></tr><tr><td> 3.1%</td><td><i>Equals</i></td></tr></tbody></table> <p>On usual applications the geometries intersects <i>a priori</i>, and the other relations are checked. </p><p>The composite predicates "<i>Intersects</i> OR <i>Disjoint</i>" and "<i>Equals</i> OR <i>Different</i>" have the sum 100% (always true predicates), but "<i>Covers</i> OR <i>CoveredBy</i>" have 41%, that is not the sum, because they are neither logical complements or independent relations; similarly "<i>Contains</i> OR <i>Within</i>", have 21%. The sum 25 % + 12.5 % = 37.5 % is obtained when ignoring overlapping lines in "<i>Crosses</i> OR <i>Overlaps</i>", because the valid input sets are disjoint. </p> <h2 id="queries-and-assertions">Queries and assertions</h2> <p>The <i>DE-9IM</i> offers a full descriptive assertion about the two input geometries. It is a mathematical function that represents a <a href="/facts/Functional_completeness/ncyHAsHH">complete set</a> of all possible relations about two entities, like a <a href="/facts/Truth_table/4KsmArDW">Truth table</a>, the <a href="/facts/Three-way_comparison/3yHfCsLS">Three-way comparison</a>, a <a href="/facts/Karnaugh_map/saFd8oNl">Karnaugh map</a> or a <a href="/facts/Venn_diagram/Vkh8fVtD">Venn diagram</a>. Each output value is like a truth table line, that represent relations of specific inputs. </p><p>As illustrated above, the output '212101212' resulted from <i>DE-9IM</i>(<i>a</i>,<i>b</i>) is a complete description of all topologic relations between specific geometries <i>a</i> and <i>b</i>. It says to us that I I = 2 , I B = 1 , I E = 2 , B I = 1 , B B = 0 , B E = 1 , E I = 2 , E B = 1 , E E = 2 {\displaystyle II=2,\,IB=1,\,IE=2,\,BI=1,\,BB=0,\,BE=1,\,EI=2,\,EB=1,\,EE=2} . </p><p>By other hand, if we check predicates like <i>Intersects</i>(<i>a</i>,<i>b</i>) or <i>Touches</i>(<i>a</i>,<i>b</i>) — for the same example we have "<i>Intersects</i>=true and <i>Touches</i>=true" — it is an incomplete description of "all topologic relations". Predicates also do not say any thing about the dimensionality of the geometries (it doesn't matter if <i>a</i> and <i>b</i> are lines, areas or points). </p><p>This independence of geometry-type and the lack of <a href="/facts/Completeness_(logic)/GzK9zLnu">completeness</a>, on <i>predicates</i>, are useful for <a href="/facts/Query_language/Sa6K4xXM">general queries</a> about two geometries: </p> <table><tbody><tr><td></td><th>interior/boundary/exterior semantic</th><th>usual semantic</th></tr><tr><th>Assertions</th><td>more descriptive " <i>a</i> and <i>b</i> have DE-9IM(<i>a</i>,<i>b</i>)='212101212' "</td><td>less descriptive " <i>a Touches b</i> "</td></tr><tr><th>Queries</th><td>more restrictive" Show all pair of geometries where DE-9IM(<i>a</i>,<i>b</i>)='212101212' "</td><td>more general" Show all pair of geometries where <i>Touches</i>(<i>a</i>,<i>b</i>) "</td></tr></tbody></table> <p>For usual applications, the use of <i>spatial predicates</i> also is justified by being more <a href="/facts/Human-readable_medium/GDE1fpHT">human-readable</a> than <i>DE-9IM</i> descriptions: a typical user have better intuition about predicates (than a set of interiors/border/exterior intersections). </p><p>Predicates have useful <a href="/facts/Semantics_(computer_science)/JEP1zyBv">semantic</a> into usual applications, so it is useful the translation of a <i>DE-9IM</i> description into a list of all associated predicates,<a class="footnote-ref" id="fnref:19" href="#fn:19"><sup>19</sup></a><a class="footnote-ref" id="fnref:20" href="#fn:20"><sup>20</sup></a> that is like a <a href="/facts/Type_conversion/FuPD945T">casting process</a> between the two different semantic types. Examples: </p> <ul><li>The string codes "0F1F00102" and "0F1FF0102" have the semantic of "<i>Intersects & Crosses & Overlaps</i>".</li> <li>The string code "1FFF0FFF2" have the semantic of "<i>Equals</i>".</li> <li>The string codes "F01FF0102", "FF10F0102", "FF1F00102", "F01FFF102", and "FF1F0F1F2" have the semantic of "<i>Intersects & Touches</i>".</li></ul> <h3>Standards</h3> <p>The <a href="/facts/Open_Geospatial_Consortium/uDKbX6Cl">Open Geospatial Consortium</a> (OGC) has standardized the typical spatial predicates (Contains, Crosses, Intersects, Touches, etc.) as boolean functions, and the DE-9IM model,<a class="footnote-ref" id="fnref:21" href="#fn:21"><sup>21</sup></a> as a function that returns a string (the DE-9IM code), with domain of {0,1,2,F}, meaning 0=point, 1=line, 2=area, and F="empty set". This DE-9IM string code is a standardized format for data interchange. </p><p>The <a href="/facts/Simple_Feature_Access/R8bwfcrs">Simple Feature Access</a> (ISO 19125) standard,<a class="footnote-ref" id="fnref:22" href="#fn:22"><sup>22</sup></a> in the chapter 7.2.8, "SQL routines on type Geometry", recommends as supported routines the <i>SQL/MM Spatial</i><a class="footnote-ref" id="fnref:23" href="#fn:23"><sup>23</sup></a> (ISO 13249-3 Part 3: Spatial) <i>ST_Dimension</i>, <i>ST_GeometryType</i>, <i>ST_IsEmpty</i>, <i>ST_IsSimple</i>, <i>ST_Boundary</i> for all Geometry Types. 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: <i>ST_Equals</i>, <i>ST_Disjoint</i>, <i>ST_Intersects</i>, <i>ST_Touches</i>, <i>ST_Crosses</i>, <i>ST_Within</i>, <i>ST_Contains</i>, <i>ST_Overlaps</i> and <i>ST_Relate</i>. </p><p>The DE-9IM in the OGC standards use the following definitions of Interior and Boundary, for the main OGC standard geometry types:<a class="footnote-ref" id="fnref:24" href="#fn:24"><sup>24</sup></a> </p> <table><tbody><tr><th>Subtypes</th><th>Dim</th><th>Interior (I)</th><th>boundary (B)</th></tr><tr><td>Point, MultiPoint</td><td>0</td><td>Point, Points</td><td>Empty</td></tr><tr><td>LineString, Line</td><td>1</td><td>Points that are left when the boundary points are removed.</td><td>Two end points.</td></tr><tr><td>LinearRing</td><td>1</td><td>All points along the geometry.</td><td>Empty.</td></tr><tr><td>MultilineString</td><td>1</td><td>Points that are left when the boundary points are removed.</td><td>Those points that are in the boundaries of an odd number of its elements (curves).</td></tr><tr><td>Polygon</td><td>2</td><td>Points within the rings.</td><td>Set of rings.</td></tr><tr><td>MultiPolygon</td><td>2</td><td>Points within the rings.</td><td>Set of rings of its elements (polygons).</td></tr><tr><td colspan="4">NOTICE: exterior points (E) are points <i>p</i> not in the <i>interior</i> or <i>boundary</i>, so not need extra interpretation, E(p)=not(I(p) or B(p)).</td></tr></tbody></table> <h3>Implementation and practical use</h3> <p>Most spatial databases, such as <a href="/facts/PostGIS/a3vdt50J">PostGIS</a>, implements the <i>DE-9IM()</i> model by the standard functions:<a class="footnote-ref" id="fnref:25" href="#fn:25"><sup>25</sup></a> ST_Relate, ST_Equals, ST_Intersects, etc. The function ST_Relate(a,b) outputs the standard OGC's <i>DE-9IM string code</i>. </p><p>Examples: two geometries, <i>a</i> and <i>b</i>, that intersects and touches with a point (for instance with dim ( B ( a ) ∩ I ( b ) ) = 0 {\displaystyle \dim(B(a)\cap I(b))=0} and dim ( I ( a ) ∩ I ( b ) ) = F {\displaystyle \dim(I(a)\cap I(b))=F} ), can be ST_Relate(a,b)='FF1F0F1F2' or ST_Relate(a,b)='FF10F0102' or ST_Relate(a,b)='FF1F0F1F2'. It also satisfies ST_Intersects(a,b)=true and ST_Touches(a,b)=true. When ST_Relate(a,b)='0FFFFF212', the returned DE-9IM code have the semantic of "Intersects(a,b) & Crosses(a,b) & Within(a,b) & CoveredBy(a,b)", that is, returns true on the boolean expression ST_Intersects(a,b) AND ST_Crosses(a,b) AND ST_Within(a,b) AND ST_Coveredby(a,b). </p><p>The use of ST_Relate() is faster than direct computing of a set of correspondent predicates.<a class="footnote-ref" id="fnref:26" href="#fn:26"><sup>26</sup></a> There are cases where using ST_Relate() is the only way to compute a complex predicate — see the example of the code 0FFFFF0F2,<a class="footnote-ref" id="fnref:27" href="#fn:27"><sup>27</sup></a> of a point that not "crosses" a multipoint (an object that is a set of points), but predicate <i>Crosses</i> (when defined by a mask) returns <i>true</i>. </p><p>It is usual to <a href="/facts/Function_overloading/wL27p4rD">overload</a> the ST_Relate() by adding a mask parameter, or use a returned ST_Relate(a,b) string into the ST_RelateMatch() function.<a class="footnote-ref" id="fnref:28" href="#fn:28"><sup>28</sup></a> When using ST_Relate(a,b,mask), it returns a boolean. Examples: </p> <ul><li>ST_Relate(a,b,'*FF*FF212') returns <i>true</i> when ST_Relate(a,b) is 0FFFFF212 or 01FFFF212, and returns <i>false</i> when 01FFFF122 or 0FF1FFFFF.</li> <li>ST_RelateMatch('0FFFFF212','*FF*FF212') and ST_RelateMatch('01FFFF212','TTF*FF212') are <i>true</i>, ST_RelateMatch('01FFFF122','*FF*FF212') is <i>false</i>.</li></ul> <h2 id="synonyms">Synonyms</h2> <ul><li>"Egenhofer-Matrix" is a synonym for the <i>9IM</i> 3x3 matrix of boolean domain.<a class="footnote-ref" id="fnref:29" href="#fn:29"><sup>29</sup></a></li> <li>"Clementini-Matrix" is a synonym for the DE-9IM 3x3 matrix of {0,1,2,F} domain.<a class="footnote-ref" id="fnref:30" href="#fn:30"><sup>30</sup></a></li> <li>"Egenhofer operators" and "Clementini operators" are sometimes a reference to matrix elements as <i>II</i>, <i>IE</i>, etc. that can be used in boolean operations. Example: the predicate "<i>G1</i> contains <i>G2</i>" can be expressed by "⟨<i>G1</i>| II ∧ ~EI ∧ ~EB |<i>G1</i>⟩", that can be translated to mask syntax, T*****FF*.</li> <li>Predicates "meets" is a synonym for <i>touches</i>; "inside" is a synonym for <i>within</i></li> <li>Oracle's<a class="footnote-ref" id="fnref:31" href="#fn:31"><sup>31</sup></a> "ANYINTERACT" is a synonym for <i>intersects</i> and "OVERLAPBDYINTERSECT" is a synonym for <i>overlaps</i>. Its "OVERLAPBDYDISJOINT" does not have a corresponding named predicate.</li> <li>In <a href="/facts/Region_connection_calculus/FPmhJrJ9">Region connection calculus</a> operators offer some synonyms for predicates: <i>disjoint</i> is DC (disconnected), <i>touches</i> is EC (externally connected), <i>equals</i> is EQ. Other, like <i>Overlaps</i> as PO (partially overlapping), need context analysis or composition.<a class="footnote-ref" id="fnref:32" href="#fn:32"><sup>32</sup></a><a class="footnote-ref" id="fnref:33" href="#fn:33"><sup>33</sup></a></li></ul> <h2 id="see-also">See also</h2> <table><tbody><tr><td>Standards:<ul><li><a href="/facts/Simple_feature_access/R8bwfcrs">Simple feature access</a> (ISO 19125)</li><li><a href="/facts/Open_Geospatial_Consortium/uDKbX6Cl">Open Geospatial Consortium</a></li><li><a href="/facts/GeoSPARQL/Kxx3yccN">GeoSPARQL</a></li></ul></td><td> </td><td>Software:<ul><li><a href="/facts/Spatial_database/wzPAetLd">Spatial database</a></li><li><a href="/facts/Object-based_spatial_database/csdMtQ1r">Object-based spatial database</a></li><li><a href="/facts/Free_and_open-source_software/1cHtjLCB">FOSS</a>:<ul><li><a href="/facts/JTS_Topology_Suite/NBW70QDB">JTS Topology Suite</a></li><li><a href="/facts/GRASS_GIS/B4CMHcad">GRASS GIS</a></li><li><a href="/facts/GDAL/oAo5CuIn">GDAL</a> (library)</li><li><a href="/facts/PostGIS/a3vdt50J">PostGIS</a></li></ul></li></ul></td><td> </td><td>Related topics:<ul><li><a href="/facts/Geospatial_topology/NKQtdEqa">Geospatial topology</a></li><li><a href="/facts/Karnaugh_map/saFd8oNl">Karnaugh (2-variable) map</a></li><li><a href="/facts/Relational_operator/nTXrhxN2">Relational operator</a></li><li><a href="/facts/Spatial_analysis/R6rlDzRl">Spatial analysis</a></li><li><a href="/facts/Spatial_relation/6RFIl1ul">Spatial relation</a></li><li><a href="/facts/Spatial%E2%80%93temporal_reasoning/5P0XlqC4">Spatial–temporal reasoning</a></li></ul></td></tr></tbody></table> <h2 id="external-links">External links</h2> <ul><li><a href="http://docs.geotools.org/latest/userguide/library/jts/dim9.html">Point Set Theory and the DE-9IM Matrix</a></li> <li><a href="https://web.archive.org/web/20131206005929/http://edndoc.esri.com/arcsde/9.1/general_topics/understand_spatial_relations.htm">Illustrated Tutorial for DE-9IM</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. Vol. 692/1993. Springer. pp. 277–295. doi:10.1007/3-540-56869-7_16. ISBN 978-3-540-56869-8. <a href="978-3-540-56869-8" target="_blank">978-3-540-56869-8</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>Egenhofer, M.J.; Franzosa, R.D. (1991). "Point-set topological spatial relations". Int. J. GIS. 5 (2): 161–174. doi:10.1080/02693799108927841. <a href="https://doi.org/10.1080%2F02693799108927841" target="_blank">https://doi.org/10.1080%2F02693799108927841</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Egenhofer, M.J.; Herring, J.R. (1990). "A Mathematical Framework for the Definition of Topological Relationships" (PDF). Proceedings of the 4th International Symposium on Spatial Data Handling. Archived from the original (PDF) on 2010-06-14. <a href="https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf" target="_blank">https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>The "OpenGIS Simple Features Specification For SQL", Revision 1.1, was released at May 5, 1999. It was the first international standard to establish the format conventions for DE-9IM string codes, and the names of the "Named Spatial Relationship predicates based on the DE-9IM" (see section with this title). <a href="/wiki/OpenGIS" target="_blank">/wiki/OpenGIS</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>M. J. Egenhofer, J. Sharma, and D. Mark (1993) "A Critical Comparison of the 4-Intersection and 9-Intersection Models for Spatial Relations: Formal Analysis Archived 2010-06-14 at the Wayback Machine", In: Auto-Carto XI Archived 2014-09-25 at the Wayback Machine. <a href="http://www.spatial.maine.edu/~max/4Vs9.pdf" target="_blank">http://www.spatial.maine.edu/~max/4Vs9.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> <li id="fn:7"><p>Chapter 4. Using PostGIS: Data Management and Queries <a href="http://www.postgis.org/docs/using_postgis_dbmanagement.html#DE-9IM" target="_blank">http://www.postgis.org/docs/using_postgis_dbmanagement.html#DE-9IM</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li> <li id="fn:8"><p>Egenhofer, M.J.; Herring, J.R. (1990). "A Mathematical Framework for the Definition of Topological Relationships" (PDF). Proceedings of the 4th International Symposium on Spatial Data Handling. Archived from the original (PDF) on 2010-06-14. <a href="https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf" target="_blank">https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li> <li id="fn:9"><p>JTS: Class IntersectionMatrix, Vivid Solutions, Inc., archived from the original on 2011-03-21 <a href="https://web.archive.org/web/20110321145301/http://www.vividsolutions.com/jts/javadoc/com/vividsolutions/jts/geom/IntersectionMatrix.html" target="_blank">https://web.archive.org/web/20110321145301/http://www.vividsolutions.com/jts/javadoc/com/vividsolutions/jts/geom/IntersectionMatrix.html</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li> <li id="fn:10"><p>Egenhofer, M.J.; Herring, J.R. (1990). "A Mathematical Framework for the Definition of Topological Relationships" (PDF). Proceedings of the 4th International Symposium on Spatial Data Handling. Archived from the original (PDF) on 2010-06-14. <a href="https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf" target="_blank">https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li> <li id="fn:11"><p>JTS Technical Specifications of 2003. <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li> <li id="fn:12"><p>M. Davis (2007), "Quirks of the 'Contains' Spatial Predicate". <a href="http://lin-ear-th-inking.blogspot.com.br/2007/06/subtleties-of-ogc-covers-spatial.html" target="_blank">http://lin-ear-th-inking.blogspot.com.br/2007/06/subtleties-of-ogc-covers-spatial.html</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></p></li> <li id="fn:13"><p>ST_Crosses <a href="http://postgis.org/docs/ST_Crosses.html" target="_blank">http://postgis.org/docs/ST_Crosses.html</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></p></li> <li id="fn:14"><p>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. <a href="#fnref:14" class="footnote-back-ref">↩</a></p></li> <li id="fn:15"><p>Egenhofer, M.J.; Herring, J.R. (1990). "A Mathematical Framework for the Definition of Topological Relationships" (PDF). Proceedings of the 4th International Symposium on Spatial Data Handling. Archived from the original (PDF) on 2010-06-14. <a href="https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf" target="_blank">https://web.archive.org/web/20100614161335/http://www.spatial.maine.edu/~max/MJEJRH-SDH1990.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></p></li> <li id="fn:16"><p>M. Davis (2007), "Quirks of the 'Contains' Spatial Predicate". <a href="http://lin-ear-th-inking.blogspot.com.br/2007/06/subtleties-of-ogc-covers-spatial.html" target="_blank">http://lin-ear-th-inking.blogspot.com.br/2007/06/subtleties-of-ogc-covers-spatial.html</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></p></li> <li id="fn:17"><p>Câmara, G.; Freitas, U. M.; Casanova, M. A. (1995). "Fields and Objects Algebras for GIS Operations". Proceedings of III Brazilian Symposium on GIS. pp. 407–424. CiteSeerX 10.1.1.17.991. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></p></li> <li id="fn:18"><p>M. Davis (2007), "Quirks of the 'Contains' Spatial Predicate". <a href="http://lin-ear-th-inking.blogspot.com.br/2007/06/subtleties-of-ogc-covers-spatial.html" target="_blank">http://lin-ear-th-inking.blogspot.com.br/2007/06/subtleties-of-ogc-covers-spatial.html</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></p></li> <li id="fn:19"><p>A DE-9IM translator, of all associated predicates of a spatial relation. <a href="https://github.com/ppKrauss/postgis-st-relate-summary" target="_blank">https://github.com/ppKrauss/postgis-st-relate-summary</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></p></li> <li id="fn:20"><p>Note. The Oracle's spatial function SDO_RELATE() Archived 2013-07-21 at the Wayback Machine do only a partial translation, internally, offering to user a mask for a or-list of predicates to be checked, instead the DE-9IM string. <a href="http://docs.oracle.com/cd/B19306_01/appdev.102/b14255/sdo_operat.htm#i78531" target="_blank">http://docs.oracle.com/cd/B19306_01/appdev.102/b14255/sdo_operat.htm#i78531</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></p></li> <li id="fn:21"><p>"OpenGIS Implementation Specification for Geographic information - Simple feature access - Part 2: SQL option", OGC, http://www.opengeospatial.org/standards/sfs <a href="/wiki/Open_Geospatial_Consortium" target="_blank">/wiki/Open_Geospatial_Consortium</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></p></li> <li id="fn:22"><p>Open Geospatial Consortium Inc. (2007), "OpenGIS® Implementation Standard for Geographic information - Simple feature access - Part 2: SQL option", OGC document 06-104r4 version 1.2.1 (review of 2010-08-04). <a href="/wiki/Open_Geospatial_Consortium" target="_blank">/wiki/Open_Geospatial_Consortium</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></p></li> <li id="fn:23"><p>ISO 13249-3 Part 3: Spatial, summarized in SQL Multimedia and Application Packages (SQL/MM) Archived 2010-02-14 at the Wayback Machine. <a href="http://www.sigmod.org/record/issues/0112/standards.pdf" target="_blank">http://www.sigmod.org/record/issues/0112/standards.pdf</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></p></li> <li id="fn:24"><p>"Encyclopedia of GIS", edited by Shashi Shekhar and Hui Xiong. SpringerScience 2008. pg. 242 <a href="#fnref:24" class="footnote-back-ref">↩</a></p></li> <li id="fn:25"><p>ST_Relate() PostGIS function online documentation. <a href="/wiki/PostGIS" target="_blank">/wiki/PostGIS</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></p></li> <li id="fn:26"><p>Chapter 4. Using PostGIS: Data Management and Queries <a href="http://www.postgis.org/docs/using_postgis_dbmanagement.html#DE-9IM" target="_blank">http://www.postgis.org/docs/using_postgis_dbmanagement.html#DE-9IM</a> <a href="#fnref:26" class="footnote-back-ref">↩</a></p></li> <li id="fn:27"><p>JTS test case of "point A within one of B points", http://www.vividsolutions.com/jts/tests/Run1Case4.html Archived 2016-03-04 at the Wayback Machine <a href="http://www.vividsolutions.com/jts/tests/Run1Case4.html" target="_blank">http://www.vividsolutions.com/jts/tests/Run1Case4.html</a> <a href="#fnref:27" class="footnote-back-ref">↩</a></p></li> <li id="fn:28"><p>ST_RelateMatch() PostGIS function online documentation. <a href="/wiki/PostGIS" target="_blank">/wiki/PostGIS</a> <a href="#fnref:28" class="footnote-back-ref">↩</a></p></li> <li id="fn:29"><p>"Encyclopedia of GIS", S. Shekhar, H. Xiong. ISBN 978-0-387-35975-5. <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:29" class="footnote-back-ref">↩</a></p></li> <li id="fn:30"><p>"Encyclopedia of GIS", S. Shekhar, H. Xiong. ISBN 978-0-387-35975-5. <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:30" class="footnote-back-ref">↩</a></p></li> <li id="fn:31"><p>Note. The Oracle's spatial function SDO_RELATE() Archived 2013-07-21 at the Wayback Machine do only a partial translation, internally, offering to user a mask for a or-list of predicates to be checked, instead the DE-9IM string. <a href="http://docs.oracle.com/cd/B19306_01/appdev.102/b14255/sdo_operat.htm#i78531" target="_blank">http://docs.oracle.com/cd/B19306_01/appdev.102/b14255/sdo_operat.htm#i78531</a> <a href="#fnref:31" class="footnote-back-ref">↩</a></p></li> <li id="fn:32"><p>"Multidimensional Region Connection Calculus" (2017), http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf <a href="http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf" target="_blank">http://qrg.northwestern.edu/qr2017/papers/QR2017_paper_8.pdf</a> <a href="#fnref:32" class="footnote-back-ref">↩</a></p></li> <li id="fn:33"><p>Sabharwal, Chaman L.; Leopold, Jennifer L. (2013). "Identification of Relations in Region Connection Calculus: 9-Intersection Reduced to 3 + -Intersection Predicates". Advances in Soft Computing and Its Applications. Lecture Notes in Computer Science. Vol. 8266. pp. 362–375. doi:10.1007/978-3-642-45111-9_32. ISBN 978-3-642-45110-2. <a href="978-3-642-45110-2" target="_blank">978-3-642-45110-2</a> <a href="#fnref:33" class="footnote-back-ref">↩</a></p></li> </ol>