DE-9IM

The DE-9IM model is based on a 3×3 intersection matrix with the form:

${\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}}}$

(1)

where ${\displaystyle \dim }$ is the dimension of the intersection (∩) of the interior (I), boundary (B), and exterior (E) of geometries a and b.

The terms interior and boundary 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).

In the notation of topological space operators, the matrix elements can be expressed also as

I(a)=ao    B(a)=∂a    E(a)=ae

(2)

The dimension of empty sets (∅) 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 points, 1 for lines, 2 for areas. Then, the domain of the model is {0,1,2,F}.

A simplified version of ${\displaystyle \dim(x)}$ 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

${\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}}}$

(3)

The elements of the matrix can be named as shown below:

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

(4)

Both matrix forms, with dimensional and boolean domains, can be serialized as "DE-9IM string codes", which represent them in a single-line 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't-care positions"). The domain of the mask elements is {0,1,2,F,*}, or {T,F,*} for the boolean form.

The simpler models 4-Intersection and 9-Intersection were proposed before DE-9IM for expressing spatial relations[6] (and originated the terms 4IM and 9IM). They can be used instead of the DE-9IM to optimize computation when input conditions satisfy specific constraints.

Illustration

Visually, for two overlapping polygonal geometries, the result of the function DE_9IM(a,b) looks like:[7]

b

a

Interior Boundary Exterior Interior   ${\displaystyle \dim[I(a){\color {red}\cap }I(b)]=2}$     ${\displaystyle \dim[I(a){\color {red}\cap }B(b)]=1}$     ${\displaystyle \dim[I(a){\color {red}\cap }E(b)]=2}$   Boundary   ${\displaystyle \dim[B(a){\color {red}\cap }I(b)]=1}$     ${\displaystyle \dim[B(a){\color {red}\cap }B(b)]=0}$     ${\displaystyle \dim[B(a){\color {red}\cap }E(b)]=1}$   Exterior   ${\displaystyle \dim[E(a){\color {red}\cap }I(b)]=2}$     ${\displaystyle \dim[E(a){\color {red}\cap }B(b)]=1}$     ${\displaystyle \dim[E(a){\color {red}\cap }E(b)]=2}$

This matrix can be serialized. Reading from left-to-right and top-to-bottom, the result is ${\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'.

Any topological property based on a DE-9IM binary spatial relation is a spatial predicate. For ease of use "named spatial predicates" have been defined for some common relations, which later became standard predicates. The spatial predicate functions that can be derived 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]	Equivalent
Equals	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				II ∧ ~IE ∧ ~BE ∧ ~EI ∧ ~EB (5) a 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".[9]	Within & Contains
	T*F**FFF*
Disjoint	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				~II ∧ ~IB ∧ ~BI ∧ ~BB (6) a and b are disjoint: they have no point in common. They form a set of disconnected geometries.	not Intersects
	FF*FF****
Touches (meets)	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {F} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$		~II ∧ (IB ∨ BI ∨ BB) (7) a touches b: they have at least one point in common, but their interiors do not intersect.
	FT*******	F**T*****	F***T****
Contains	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				II ∧ ~EI ∧ ~EB (8) a contains b: geometry b lies in a, and the interiors intersect. 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".[10]	Within(b,a)
	T*****FF*
Covers	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {F} &\mathrm {F} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	(II ∨ IB ∨ BI ∨ BB) ∧ ~EI ∧ ~EB (9) a covers b: geometry b lies in a. Other definitions: "At least one point of b lies in a, and no point of b lies in the exterior of a", or "Every point of b is a point of (the interior or boundary of) a".	CoveredBy(b,a)
	T*****FF*	*T****FF*	***T**FF*	****T*FF*

Predicates that can be obtained from the above by logical negation or parameter inversion (matrix transposition), as indicated by the last column:

Intersects	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {T} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	a intersects b: geometries a and b have at least one point in common.	not Disjoint
	T********	*T*******	***T*****	****T****
Within (inside)	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$				a is within b: a lies in the interior of b.	Contains(b,a)
	T*F**F***
CoveredBy	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {T} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {T} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {*} &\mathrm {*} &\mathrm {F} \\\mathrm {*} &\mathrm {T} &\mathrm {F} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	a is covered by b (extends Within): geometry a lies in b. Other definitions: "At least one point of a lies in b, and no point of a lies in the exterior of b", or "Every point of a is a point of (the interior or boundary of) b".	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,*}:

Crosses ${\displaystyle \dim(a)\neq \dim(b)}$ or dim(any) = 1	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {0} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$		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 ${\displaystyle \dim(a)\neq \dim(b)}$, except by line/line inputs, otherwise is false:[11] (II=0) for lines,   (II ∧ IE) when ${\displaystyle \dim(a)<\dim(b)}$,   (II ∧ EI) when ${\displaystyle \dim(a)>\dim(b)}$ (10)
	T*T****** ${\displaystyle \dim(a)<\dim(b)}$	T*****T** ${\displaystyle \dim(a)>\dim(b)}$	0******** dim(any) = 1
Overlaps ${\displaystyle \dim(a)=\dim(b)}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {T} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$	${\displaystyle {\Bigl [}{\begin{smallmatrix}\mathrm {1} &\mathrm {*} &\mathrm {T} \\\mathrm {*} &\mathrm {*} &\mathrm {*} \\\mathrm {T} &\mathrm {*} &\mathrm {*} \end{smallmatrix}}{\Bigr ]}}$			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 ${\displaystyle \dim(a)=\dim(b)}$, otherwise is false: (II ∧ IE ∧ EI) for points or surfaces,   (II=1 ∧ IE ∧ EI) for lines (11)
	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 ${\displaystyle \operatorname {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 have additional conditions about ${\displaystyle \dim(a)}$ and ${\displaystyle \dim(b)}$.

• 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).

• 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.

• 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.

• Historically, other terms and other formal approaches have been used to express spatial predicates; for example region connection calculus was introduced in 1992 by[12] Randell, Cohn and Cohn.

Interpretation

Examples of spatial relations.

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:[10][13]

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,[10] 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".

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 says to us that ${\displaystyle 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 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 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,[14][15] 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".

• "Egenhofer-Matrix" is a synonym for the 9IM 3x3 matrix of boolean domain.[23]
• "Clementini-Matrix" is a synonym for the DE-9IM 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₁ contains G₂" can be expressed by "⟨G₁| II ∧ ~EI ∧ ~EB |G₁⟩", that can be translated to mask syntax, T*****FF*.
• Predicates "meets" is a synonym for touches; "inside" is a synonym for within
• Oracle's[15] "ANYINTERACT" is a synonym for intersects and "OVERLAPBDYINTERSECT" is a synonym for overlaps. Its "OVERLAPBDYDISJOINT" does not have a corresponding named predicate.
• In Region connection calculus operators offer some synonyms for predicates: disjoint is DC (disconnected), touches is EC (externally connected), equals is EQ. Other, like Overlaps as PO (partially overlapping), need context analysis or composition.[24][25]

• Point Set Theory and the DE-9IM Matrix
• Illustrated Tutorial for DE-9IM