DE-9IM


The Dimensionally Extended 9-Intersection Model is a topological model and a [|standard] used to describe the spatial relations of two regions, in geometry, point-set topology, geospatial topology, and fields related to computer spatial analysis. The spatial relations expressed by the model 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. The English language contains about 10 schemes, such as "intersects", "touches" and "equals". When testing two geometries against a scheme, the result is a spatial predicate 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 queries and assertions in geographic information systems and spatial databases.

Matrix model

The DE-9IM model is based on a 3×3 intersection matrix with the form:
where is the dimension of the intersection of the interior, boundary, and exterior 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 the notation of topological space operators, the matrix elements can be expressed also as
The dimension of empty sets are denoted as −1 or . The dimension of non-empty sets are denoted with the maximum number of dimensions of the intersection, specifically for points, for lines, for areas. Then, the domain of the model is.
A simplified version of values are obtained mapping the values to , so using the boolean domain. 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 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 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.
The domain of the mask elements is, or for the boolean form.
The simpler models 4-Intersection and 9-Intersection were proposed before DE-9IM for expressing spatial relations. 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 looks like:
This matrix can be serialized. Reading from left-to-right and top-to-bottom, the result is. So, in a compact representation as string code is ''.

Spatial predicates

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:
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 and Within :.
  • 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 Randell, Cohn and Cohn.

    Properties

The spatial predicates have the following properties of binary relations:
  • Reflexive: Equals, Contains, Covers, CoveredBy, Intersects, Within
  • Anti-reflexive: Disjoint
  • Symmetric: Equals, Intersects, Crosses, Touches, Overlaps
  • Transitive: Equals, Contains, Covers, CoveredBy, Within

    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 have an obvious semantic:
; Equals: a = b that is ∧
; Within: a ∩ b = a
; Intersects: a ∩ b ≠ ∅
; Touches: ∧
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, 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 29=512, and in a DE-9IM matrix is 39=6561. The percentage of these results that 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%,
but "Covers OR CoveredBy" have 41%, that is not the sum, because they are neither logical complements or independent relations; similarly "Contains OR Within", have 21%. The sum 25 % + 12.5 % = 37.5 % is obtained when ignoring overlapping lines in "Crosses OR Overlaps", because the valid input sets are disjoint.

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 is a complete description of all topologic relations between specific geometries a and b. It says to us that.
By other hand, if we check predicates like Intersects or Touches — for the same example we have "Intersects= and Touches=" — it is an incomplete description of "all topologic relations".
Predicates also do not say any thing about the dimensionality of the geometries.
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.
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:
  • The string codes "" and "" have the semantic of "Intersects & Crosses & Overlaps".
  • The string code "" have the semantic of "Equals".
  • The string codes "", "", "", "", and "" have the semantic of "Intersects & Touches".

    Standards

The Open Geospatial Consortium has standardized the typical spatial predicates as boolean functions, and the DE-9IM model, as a function that returns a string, with domain of, meaning =point, =line, =area, and ="empty set". This DE-9IM string code is a standardized format for data interchange.
The Simple Feature Access standard, in the chapter 7.2.8, "SQL routines on type Geometry", recommends as supported routines the SQL/MM 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 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: