DE 9IM

Matrix model

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

where dim 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

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

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 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"). Then, the mask's domain is {0,1,2,T,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 (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, this looks like:

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

Spatial predicates

Spatial predicates are binary invariant space relations based on the DE-9IM. 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 DE-9IM include:

Predicates defined with masks of domain {T,F,*}

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

Predicates that utilize the input dimensions, and are defined with masks of domain {0,1,T,F,*}

Notice that:

Interpretation

The choice of terminology and semantics for the spatial predicates is based on reasonable conventions and the tradition of topological studies. Relationships such as Intersects, Disjoint, Touches, Within, Equals (between two geometries a and b) have an obvious semantic:

The predicates Contains and Within have subtle aspects to their definition which are contrary to intuition. For example, 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:

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,

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 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 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:

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, that is like a casting process between the two different semantic types. Examples:

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, 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, in the chapter 7.2.8, "SQL routines on type Geometry", recommends as supported routines the SQL/MM Spatial (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:

Implementation and practical use

Most spatial databases, such as PostGIS, implements the DE-9IM() model by the standard functions: 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. 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, 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. When using ST_Relate(a,b,mask), it returns a boolean. Examples:

Synonyms