DE-9IM

The simplified models, 4-Intersection and 9-Intersection, proposed before DE-9IM for express spatial relations^[6] (and originating the labels 4IM and 9IM) can replace the DE-9IM to optimize calculations, when input conditions satisfy specific constraints.

Illustration

Visually, for two overlapping polygonal geometries, this looks like:^[7]

	b
a	Interior Boundary Exterior Interior   dim[I(a)∩I(b)] = 2     dim[I(a)∩B(b)] = 1     dim[I(a)∩E(b)] = 2   Boundary   dim[B(a)∩I(b)] = 1     dim[B(a)∩B(b)] = 0     dim[B(a)∩E(b)] = 1   Exterior   dim[E(a)∩I(b)] = 2     dim[E(a)∩B(b)] = 1     dim[E(a)∩E(b)] = 2

Reading from left-to-right and top-to-bottom, the resulted DE-9IM(a,b) string code is '212101212', a compacted form for say "II=2, IB=1, IE=2, BI=1, BB=0, BE=1, EI=2, EB=1, EE=2".

Spatial predicates

The model express important space relations because they are invariant to rotation, translation and scaling transformations; but, in its most general form the DE-9IM model is too complex to make it usable. So, the adoption of "named predicates" have been specified.

Spatial predicates are binary invariant space relations, with more usual semantics. The spatial predicate functions that can be derived (expressed by masks) from DE-9IM include:^{[4] [8]}

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]	Same
Equals					II ∧ ~IE ∧ ~BE ∧ ~EI ∧ ~EBa and b are topologically equal. "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".[10]	Within & Contains
	T*F**FFF*
Disjoint					~II ∧ ~IB ∧ ~BI ∧ ~BBa and b are disjoint, have no point in common. They form a set of disconnected geometries.	not Intersects
	FF*FF****
Touches (meets)					(~II ∧ IB) ∨ (~II ∧ BI) ∨ (~II ∧ BB)a touches b, they have at least one boundary point in common, but no interior points.
	FT*******	F**T*****	F***T****
Contains					II ∧ ~EI ∧ ~EBb is within a. Geometry b lies in the interior of a. Another definition: "a 'contains' b iff no points of b lie in the exterior of a, and at least one point of the interior of b lies in the interior of a".[11]	Within(b,a)
	T*****FF*
Covers					(II ∧ ~EI ∧ ~EB) ∨ (IB ∧ ~EI ∧ ~EB) ∨ (BI ∧ ~EI ∧ ~EB) ∨ (BB ∧ ~EI ∧ ~EB)a covers b. Geometry b lies in the interior of a (extends Contains). Other definitions: "no points of b lie in the exterior of a", or "Every point of b is a point of (the interior of) a".	CoveredBy(b,a)
	T*****FF*	*T****FF*	***T**FF*	****T*FF*

Predicates that can be obtained by the above, by logic negation or parameter inversion (matrix transposition):

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 checks the input dimensions, and are defined with masks of domain {0,1,T,F,*}

Crosses dim(a)≠dim(b) or dim(any)=0					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 dim(a)≠dim(b), except by point/point or line/line inputs, otherwise is false:[12] (II=0) for points or lines,   (II ∧ IE) when dim(a)<dim(b),   (II ∧ EI) when dim(a)>dim(b)
	T*T****** dim(a)<dim(b)	T*****T** dim(a)>dim(b)	0******** dim(any)=0
Overlaps dim(a)=dim(b)					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 dim(a)=dim(b), otherwise is false: (II ∧ IE ∧ EI) for points or surfaces,   (II=1 ∧ IE ∧ EI) for lines
	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 DE-9IM(a,b) 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 has adicional conditions about dim(a) and dim(b).

• All mask string codes ends with '*'. It is because EE have no extra 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 mask T*****T**), but by a more rigorous definition, like the JTS definition, not.^[13]

• The mask T*****FF* is within 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*** falls within the definition of both, Within and CoveredBy.

Interpretation

Examples of spatial relations.

The terminology used for translating the nine relations into more usual semantics, is based on reasonable conventions and the tradition of topological studies.^[4] Relationships (between two geometries a and b) such as Intersects, Disjoint, Touches, Within, Equals, 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 other ones, Covers, Contains, CoveredBy and Within, have subtle aspects to their definition which are contrary to intuition.

Example of "non-obvious predicates", that has an aspect of its definition which may produce unexpected behaviour:^[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". See the Contains definition above: the last clause, "at least one point of the interior of B lies in the interior of A", causes the trap. In this case, the predicate Covers has the intuitively expected semantics (see definition), avoiding boundary considerations.

For a better intuitive understand we can use the dimensionality of inputs, as justification to 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 flexibilization of Equals, "some equal point at the line".
line/line	adds Touches, Crosses, ...	Touches is a constraint of Intersects, about "only boundaries"; Crosses about "only one point".

Coverage on possible matrix results

The number of possible results in a boolean 9IM matrix is 2⁹=512, and in a DE-9IM matrix is 3⁹=6561. The probability of one of these results come to satisfy a specific predicate is determined as following,

• 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 another 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 DE-9IM 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 Three-way 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 DE-9IM(a,b) is a complete description of all topologic relations between specific geometries a and b. It say to us that "II=2, IB=1, IE=2, BI=1, BB=0, BE=1, EI=2, EB=1, EE=2".

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 not say any thing about the dimensionality of the geometries (no matter if a and b are lines, areas or points).

This independence of geometry-type 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 DE-9IM(a,b)='212101212' "		less descriptive " a Touches b "
Queries:	more restrictive " Show all pair of geometries where DE-9IM(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 human-readable than DE-9IM 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 DE-9IM 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 DE-9IM model,^[17] 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.

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 13249-3 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 DE-9IM in the OGC standards use the following definitions of Interior and Boundary, for the main OGC standard geometry types:^[20]

Implementation and practical use

Most spatial databases, such as PostGIS, implements the DE-9IM() model by the standard functions:^[21] ST_Relate, ST_Equals, ST_Intersects, etc. The function ST_Relate(a,b) outputs the standard OGC's DE-9IM string code.

Examples: two geometries, a and b, that intersects and touches with a point (for instance with dim(B(a)∩I(b))=0 and dim(I(a)∩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).

The use of st_relate() is faster than direct computing of a set of correspondent predicates.^[22] 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.^[23] When using st_relate(a,b,mask), it returns a boolean. Examples: