DE-9IM

The () is a and a used to describe the of two regions (two , ), in , , , and fields related to . The spatial relations expressed by the model are invariant to , and 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 . The English language contains about 10 schemes (relations), such as "intersects", "touches" and "equals". When testing two geometries against a scheme, the result is a named by the scheme.

The model was developed by Clementini and others based on the seminal works of Egenhofer and others. It has been used as a basis for standards of and in (GIS) and .

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

where is the of the (∩) of the (I), (B), and (E) of geometries and .

The terms and 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

The dimension of (∅) are denoted as −1 or (false). The dimension of non-empty sets (¬∅) are denoted with the maximum number of dimensions of the intersection, specifically for , for , for . Then, the of the model is {,,,}.

A simplified version of values are obtained mapping the values {} to (true), so using the {,}. The matrix, denoted with operators, can be expressed as

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

Both matrix forms, with dimensional and boolean domains, can be as "", which represent them in a single-line string pattern. Since 1999 the have a format.

For output checking or pattern analysis, a matrix value (or a string code) can be checked by a "": a desired output value with optional symbols as — 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 {,,,,}, or {,,} for the boolean form.

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

Visually, for two overlapping polygonal geometries, the result of the function looks like:

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 . Reading from left-to-right and top-to-bottom, the result is .  So, in a compact representation as string code is ''.

Predicates defined with masks of domain {,,}:

Predicates that utilize the input dimensions, and are defined with masks of domain {,,,}:

By other hand, if we check predicates like (,) or (,) — for the same example we have "= and =" — 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 and are lines, areas or points).

• The string codes "" and "" have the semantic of "".
• The string code "" have the semantic of "".
• The string codes "", "", "", "", and "" have the semantic of "".

The (OGC) has standardized the typical spatial predicates (Contains, Crosses, Intersects, Touches, etc.) as boolean functions, and the DE-9IM model, as a function that returns a string (the DE-9IM code), with domain of {,,,}, meaning =point, =line, =area, and ="empty set". This DE-9IM string code is a standardized format for data interchange.

The use of is faster than direct computing of a set of correspondent predicates. There are cases where using is the only way to compute a complex predicate — see the example of the code , of a point that not "crosses" a multipoint (a object that is a set of points), but predicate (when defined by a mask) returns .

It is usual to the by adding a mask parameter, or use a returned string into the function. When using , it returns a boolean. Examples:

• "Clementini-Matrix" is a synonym for the 3x3 matrix of {,,,} domain.