DE9IM
The Dimensionally Extended nineIntersection Model (DE9IM) is a topological model and a standard used to describe the spatial relations of two regions (two geometries in twodimensions, R^{2}), in Geometry, Pointset topology, Geospatial topology, and fields related to computer spatial analysis. Since the spatial relations expressed by the model are topological they are invariant to rotation, translation and scaling transformations.
The matrix provides an approach for classifying geometry relations. Roughly speaking, with a true/false matrix domain, there are 512 possible 2D topologic relations, that can be grouped into binary classification schemes. For English speakers, there are about 10 schemes (relations) that have a name that reflects their semantics (e.g. "Intersects", "Touches", "Equals", and others.) When testing two geometries against a scheme, the result of this test is a spatial predicate named by the scheme.
The model was developed by Clementini and others^{[1]}^{[2]} based on the seminal works of Egenhofer and others.^{[3]}^{[4]} It has been used as a basis for standards of queries and assertions in geographic information systems (GIS) and spatial databases.
Contents
Matrix model
The DE9IM model is based on a 3×3 intersection matrix with the form:

(1)
where is the maximum number of dimensions of the intersection (∩) of the interior (I), boundary (B), and exterior (E) of geometries a and b.
Note that in this article the words interior and boundary are used in the sense used in algebraic topology and manifold theory, not in the sense used in general topology: e.g. by the interior of a line segment we mean the line segment without its endpoints and by its boundary, the two endpoints (in the general topology sense, the interior of a line segment in the plane is empty and the line segment is its own boundary).
In the notation of topological space operators, the matrix elements can be expressed also as

I(a)=a^{o} B(a)=∂a E(a)=a^{e}
(2)
The dimension of empty sets (∅) are denoted as −1 or F (false). The dimension of nonempty sets (¬∅) are denoted with the maximum number of dimensions of the intersection, specifically 0 for points, 1 for lines, 2 for areas. Then, the domain of the model is {0,1,2,F}.
A simplified version of values are obtained mapping the values {0,1,2} to T (true), so using the boolean domain {T,F}. The matrix, denoted with operators, can be expressed as

(3)
Both matrix forms, with dimensional and boolean domains, can be serialized as "DE9IM string codes", which represent them in a singleline string pattern. Since 1999 the string codes have a standard^{[5]} format.
For output checking or pattern analysis, a matrix value (or a string code) can be checked by a "mask": a desired output value with optional asterisk symbols as wildcards — that is, "*" indicating output positions that the designer does not care about (free values or "don'tcare positions"). Then, the mask's domain is {0,1,2,F,*}, or {T,F,*} for the boolean form.
The simpler models 4Intersection and 9Intersection were proposed before DE9IM for expressing spatial relations^{[6]} (and originated the terms 4IM and 9IM). They can be used instead of the DE9IM to optimize computation when input conditions satisfy specific constraints.
Illustration
Visually, for two overlapping polygonal geometries, this looks like:^{[7]}




Reading from lefttoright and toptobottom, the DE9IM(a,b) string code is '212101212', the compact representation of .
Spatial predicates
Spatial predicates are binary invariant space relations based on the DE9IM. For ease of use "named spatial predicates" have been defined for some common relations.
The spatial predicate functions that can be derived (expressed by masks) from DE9IM include:^{[4]} ^{[8]}

(4)
Predicates defined with masks of domain {T,F,*}
Name (synonym)  Intersection matrix and mask code string (boolean OR between matrices) 
Meaning and definition^{[4]}^{[9]}  Equivalent  

Equals 

Within & Contains  
T*F**FFF* 

Disjoint 

not Intersects  
FF*FF**** 

Touches (meets) 


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

Contains 

Within(b,a)  
T*****FF* 

Covers 

CoveredBy(b,a)  
T*****FF* 
*T****FF* 
***T**FF* 
****T*FF* 
Predicates that can be obtained from the above by logic negation or parameter inversion (matrix transposition), as indicated by the last column:
Intersects  a intersects b: geometries a and b have at least one point in common.  not Disjoint  

T******** 
*T******* 
***T***** 
****T**** 

Within (inside) 
a is within b: a lies in the interior of b.  Contains(b,a)  
T*F**F*** 

CoveredBy  a is covered by b (extends Within): every point of a is a point of b, and the interiors of the two geometries have at least one point in common.  Covers(b,a)  
T*F**F*** 
*TF**F*** 
**FT*F*** 
**F*TF*** 
Predicates that utilize the input dimensions, and are defined with masks of domain {0,1,T,F,*}
Crosses or dim(any) = 1 
a crosses b: 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. Mask selection rules are checked only when , except by line/line inputs, otherwise is false:^{[12]}



T*T****** 
T*****T** 
0******** dim(any) = 1 

Overlaps 
a overlaps b: 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. Mask selection rules are checked only when , otherwise is false:


T*T***T** dim = 0 or 2 
1*T***T** dim = 1 
Notice that:
 The topologically equal definition does not imply that they have the same points or even that they are of the same class.
 The output of have the information contained in a list of all interpretable predicates about geometries a and b.
 All predicates are computed by masks. Only Crosses and Overlaps have additional conditions about and .
 All mask string codes end with
*
. This is because EE is trivially true, and thus provides no useful information.  The Equals mask,
T*F**FFF*
, is the "merge" of Contains (T*****FF*
) and Within (T*F**F***
): (II ∧ ~EI ∧ ~EB) ∧ (II ∧ ~IE ∧ ~BE).  There are no mask for situations involving complex types, like a Point/Multipoint situation. Example: with the above definition the code
0FFFFF0F2
have the Crosses predicate (satisfies the maskT*****T**
), but by a more rigorous definition, like the JTS definition, not.^{[13]}  The mask
T*****FF*
occurs in the definition of both Contains and Covers. Covers is a more inclusive relation. In particular, unlike Contains it does not distinguish between points in the boundary and in the interior of geometries. For most situations, Covers should be used in preference to Contains.^{[9]}  Similarly, the mask
T*F**F***
occurs in the definition of both Within and CoveredBy. For most situations, CoveredBy should be used in preference to Within.^{[9]}
Interpretation
The choice of terminology and semantics for the spatial predicates is based on reasonable conventions and the tradition of topological studies.^{[4]} Relationships such as Intersects, Disjoint, Touches, Within, Equals (between two geometries a and b) have an obvious semantic:^{[11]}^{[14]}
 Equals
 a = b that is (a ∩ b = a) ∧ (a ∩ b = b)
 Within
 a ∩ b = a
 Intersects
 a ∩ b ≠ ∅
 Touches
 (a ∩ b ≠ ∅) ∧ (a^{ο} ∩ b^{ο} = ∅)
The predicates Contains and Within have subtle aspects to their definition which are contrary to intuition. For example,^{[11]} a line L which is completely contained in the boundary of a polygon P is not considered to be contained in P. This quirk can be expressed as "Polygons do not contain their boundary". This issue is caused by the final clause of the Contains definition above: "at least one point of the interior of B lies in the interior of A". For this case, the predicate Covers has more intuitive semantics (see definition), avoiding boundary considerations.
For better understanding, the dimensionality of inputs can be used as justification for a gradual introduction of semantic complexity:

Relations between Appropriate predicates Semantic added point/point Equals, Disjoint Other valid predicates collapses into Equals. point/line adds Intersects Intersects is a refinement of Equals: "some equal point at the line". line/line adds Touches, Crosses, ... Touches is a refinement of Intersects, about "boundaries" only. Crosses is about "only one point".
Coverage on possible matrix results
The number of possible results in a boolean 9IM matrix is 2^{9}=512, and in a DE9IM matrix is 3^{9}=6561. The probability of one of these results come to satisfy a specific predicate is determined as following,
Probability  Name 

93.7%  Intersects 
43.8%  Touches 
25%  Crosses (for valid inputs, 0% otherwise) 
23.4%  Covers and CoveredBy 
12.5%  Contains, Overlaps (for valid inputs, 0% otherwise) and Within 
6.3%  Disjoint 
3.1%  Equals 
On usual applications the geometries intersects a priori, and the other relations are checked.
The composite predicates "Intersects OR Disjoint" and "Equals OR Different" have the sum 100% (always true predicates), but "Covers OR CoveredBy" have 41%, that is not the sum, because they are not logical complements neither independent relations; idem "Contains OR Within", that have 21%. The sum 25%+12.5%=37.5% is obtained when ignoring overlaping of lines in "Crosses OR Overlaps", because the valid input sets are disjoints.
Queries and assertions
The DE9IM offers a full descriptive assertion about the two input geometries. It is a mathematical function that represents a complete set of all possible relations about two entities, like a Truth table, the Threeway comparison, a Karnaugh map or a Venn diagram. Each output value is like a truth table line, that represent relations of specific inputs.
As illustrated above, the output '212101212' resulted from DE9IM(a,b) is a complete description of all topologic relations between specific geometries a and b. It say to us that .
By other hand, if we check predicates like Intersects(a,b) or Touches(a,b) — for the same example we have "Intersects=true and Touches=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 a and b are lines, areas or points).
This independence of geometrytype and the lack of completeness, on predicates, are useful for general queries about two geometries:

interior/boundary/exterior semantic usual semantic Assertions more descriptive
" a and b have DE9IM(a,b)='212101212' "less descriptive
" a Touches b "Queries more restrictive
" Show all pair of geometries where DE9IM(a,b)='212101212' "more general
" Show all pair of geometries where Touches(a,b) "
For usual applications, the use of spatial predicates also is justified by being more humanreadable than DE9IM descriptions: a typical user have better intuition about predicates (than a set of interiors/border/exterior intersections).
Predicates have useful semantic into usual applications, so it is useful the translation of a DE9IM description into a list of all associated predicates,^{[15]}^{[16]} that is like a casting process between the two different semantic types. Examples:
 The string codes "0F1F00102" and "0F1FF0102" have the semantic of "Intersects & Crosses & Overlaps".
 The string code "1FFF0FFF2" have the semantic of "Equals".
 The string codes "F01FF0102", "FF10F0102", "FF1F00102", "F01FFF102", and "FF1F0F1F2" have the semantic of "Intersects & Touches".
Standards
The Open Geospatial Consortium (OGC) has standardized the typical spatial predicates (Contains, Crosses, Intersects, Touches, etc.) as boolean functions, and the DE9IM model,^{[17]} as a function that returns a string (the DE9IM code), with domain of {0,1,2,F}, meaning 0=point, 1=line, 2=area, and F="empty set". This DE9IM string code is a standardized format for data interchange.
The Simple feature access (ISO 19125) standard,^{[18]} in the chapter 7.2.8, "SQL routines on type Geometry", recommends as supported routines the SQL/MM Spatial^{[19]} (ISO 132493 Part 3: Spatial) ST_Dimension, ST_GeometryType, ST_IsEmpty, ST_IsSimple, ST_Boundary 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: ST_Equals, ST_Disjoint, ST_Intersects, ST_Touches, ST_Crosses, ST_Within, ST_Contains, ST_Overlaps and ST_Relate.
The DE9IM in the OGC standards use the following definitions of Interior and Boundary, for the main OGC standard geometry types:^{[20]}
Subtypes  Dim  Interior (I)  boundary (B) 

Point, MultiPoint  0  Point, Points  Empty 
LineString, Line  1  Points that are left when the boundary points are removed.  Two end points. 
LinearRing  1  All points along the geometry.  Empty. 
MultilineString  1  Points that are left when the boundary points are removed.  Those points that are in the boundaries of an odd number of its elements (curves). 
Polygon  2  Points within the rings.  Set of rings. 
MultiPolygon  2  Points within the rings.  Set of rings of its elements (polygons). 
NOTICE: exterior points (E) are points p not in the interior or boundary, so not need extra interpretation, E(p)=not(I(p) or B(p)). 
Implementation and practical use
Most spatial databases, such as PostGIS, implements the DE9IM() model by the standard functions:^{[21]} ST_Relate
, ST_Equals
, ST_Intersects
, etc. The function ST_Relate(a,b)
outputs the standard OGC's DE9IM string code.
Examples: two geometries, a and b, that intersects and touches with a point (for instance with and ), 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 DE9IM 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)
.
The use of ST_Relate() is faster than direct computing of a set of correspondent predicates.^{[7]} There are cases where the use of ST_Relate() is the unique access form of a complex predicate — see the example of the code 0FFFFF0F2
,^{[13]} of a point that not "crosses" a multipoint (a object that is a set of points), but predicate Crosses (when defined by a mask) returns true.
It is usual also to overload the ST_Relate() by a mask parameter, or use a returned ST_Relate(a,b) string into the ST_RelateMatch() function.^{[22]} When using ST_Relate(a,b,mask), it returns a boolean. Examples:

ST_Relate(a,b,'*FF*FF212')
returns true whenST_Relate(a,b)
is0FFFFF212
or01FFFF212
, and returns false when01FFFF122
or0FF1FFFFF
. 
ST_RelateMatch('0FFFFF212','*FF*FF212')
andST_RelateMatch('01FFFF212','TTF*FF212')
are true,ST_RelateMatch('01FFFF122','*FF*FF212')
is false.
Synonyms
 "EgenhoferMatrix" is a synonym for the 9IM 3x3 matrix of boolean domain.^{[23]}
 "ClementiniMatrix" is a synonym for the DE9IM 3x3 matrix of {0,1,2,F} domain.^{[23]}
 "Egenhofer operators" and "Clementini operators" are sometimes a reference to matrix elements as II, IE, etc. that can be used in boolean operations. Example: the predicate "G_{1} contains G_{2}" can be expressed by "⟨G_{1} II ∧ ~EI ∧ ~EB G_{1}⟩", that can be translated to mask syntax,
T*****FF*
.  Predicates "meets" is a synonym for touches; "inside" is a synonym for within
 Oracle's^{[16]} "ANYINTERACT" is a synonym for intersects and "OVERLAPBDYINTERSECT" is a synonym for overlaps. Its "OVERLAPBDYDISJOINT" does not have a corresponding named predicate.
See also
Standards:

Software:  Related topics 
References
 ^ Clementini, Eliseo; Di Felice, Paolino; van Oosterom, Peter (1993). "A small set of formal topological relationships suitable for enduser interaction". In Abel, David; Ooi, Beng Chin. 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/3540568697_16.
 ^ 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/00978493(94)900078.
 ^ Egenhofer, M.J.; Franzosa, R.D. (1991). "Pointset topological spatial relations". Int. J. GIS. 5 (2): 161–174. doi:10.1080/02693799108927841.
 ^ ^{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 20100614.
 ^ 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 DE9IM string codes, and the names of the "Named Spatial Relationship predicates based on the DE9IM" (see section with this title).
 ^ M. J. Egenhofer, J. Sharma, and D. Mark (1993) "A Critical Comparison of the 4Intersection and 9Intersection Models for Spatial Relations: Formal Analysis", In: AutoCarto XI.
 ^ ^{a} ^{b} Chapter 4. Using PostGIS: Data Management and Queries
 ^ JTS: Class IntersectionMatrix, Vivid Solutions, Inc., archived from the original on 20110321
 ^ ^{a} ^{b} ^{c} Geometry
 ^ JTS Technical Specifications of 2003.
 ^ ^{a} ^{b} ^{c} M. Davis (2007), "Quirks of the 'Contains' Spatial Predicate".
 ^ ST_Crosses
 ^ ^{a} ^{b} JTS test case of "point A within one of B points", http://www.vividsolutions.com/jts/tests/Run1Case4.html
 ^ Câmara, G.; Freitas, U. M.; Casanova, M. A. (1995). "Fields and Objects Algebras for GIS Operations". CiteSeerX 10.1.1.17.991 .
 ^ A DE9IM translator, of all associated predicates of a spatial relation.
 ^ ^{a} ^{b} Note. The Oracle's spatial funcion SDO_RELATE() do only a partial translation, internally, offering to user a mask for a orlist of predicates to be checked, instead the DE9IM string.
 ^ "OpenGIS Implementation Specification for Geographic information  Simple feature access  Part 2: SQL option", OGC, http://www.opengeospatial.org/standards/sfs
 ^ Open Geospatial Consortium Inc. (2007), "OpenGIS® Implementation Standard for Geographic information  Simple feature access  Part 2: SQL option", OGC document 06104r4 version 1.2.1 (review of 20100804).
 ^ ISO 132493 Part 3: Spatial, summarized in SQL Multimedia and Application Packages (SQL/MM).
 ^ "Encyclopedia of GIS", edited by Shashi Shekhar and Hui Xiong. SpringerScience 2008. pg. 242
 ^ ST_Relate() PostGIS function online documentation.
 ^ ST_RelateMatch() PostGIS function online documentation.
 ^ ^{a} ^{b} "Encyclopedia of GIS", S. Shekhar, H. Xiong. ISBN 9780387359755.
External links
 Point Set Theory and the DE9IM Matrix
 Illustrated Tutorial for DE9IM