DE-9IM
The Dimensionally Extended 9-Intersection Model (DE-9IM) is a topological model and a standard used to describe the spatial relations of two regions (two geometries in two-dimensions, R 2 ), in geometry, point-set topology, geospatial…
≈ 5 min read
DE-9IM. encyclopegia.org, snapshot enwiki-001366469586. /a/de-9im
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The Dimensionally Extended 9-Intersection Model (DE-9IM) is a topological model and a standard used to describe the spatial relations of two regions (two geometries in two-dimensions, R 2 ), 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 (relations), 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 (GIS) and spatial databases. | align="center" valign="middle" | | |} 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 ' '.
Equals: a = b that is Within: Intersects: 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 (see definition), avoiding boundary considerations. For better understanding, the dimensionality of inputs can be used as justification for a gradual introduction of semantic complexity: The number of possible results in a boolean 9IM matrix is 2 9 =512, and in a DE-9IM matrix is 3 9 =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% (always true predicates), 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. By other hand, if we check predicates like Intersects(a,b) or Touches(a,b) — 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 (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: 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". Examples: two geometries, a and b, that intersects and touches with a point (for instance with and ), 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 , that is, returns 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 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 0FFFFF0F2 , of a point that not "crosses" a multipoint (an object that is a set of points), but predicate Crosses (when defined by a mask) returns true.
It is usual to overload the by adding a mask parameter, or use a returned string into the function. When using , it returns a boolean. Examples: ST_Relate(a,b,'*FF*FF212') returns true when ST_Relate(a,b) is 0FFFFF212 or 01FFFF212 , and returns false when 01FFFF122 or 0FF1FFFFF .
ST_RelateMatch('0FFFFF212','*FF*FF212') and ST_RelateMatch('01FFFF212','TTF*FF212') are true, ST_RelateMatch('01FFFF122','*FF*FF212') is false.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1366469586 under CC BY-SA 4.0; modifications have been made.