DE-9IM

DE-9IM
Name	DE-9IM
Alternative names	Dimensionally Extended Nine-Intersection Model
Domain	Geographic information systems
Introduced	1990s
Standardised by	Open Geospatial Consortium, International Organization for Standardization
Related to	R-tree, Geographic Information System, Topology (mathematics)

DE-9IM

The DE-9IM model is a formal spatial topology model used in Geographic Information System standards to describe spatial relations between two geometries. It provides a compact, expressive schema that enables interoperability among Open Geospatial Consortium services, International Organization for Standardization standards, and implementations in libraries such as GEOS, JTS Topology Suite, and PostGIS. The model underpins topological query capabilities in systems developed by organizations like Esri and projects such as QGIS.

Definition and Purpose

DE-9IM defines topological relationships in terms of intersections between the interior, boundary, and exterior of two geometries. Its purpose is to provide an unambiguous, machine-readable signature that can distinguish relations like disjoint, overlap, contain, and equal—relations required by applications developed by NASA, European Space Agency, United Nations spatial analyses, and national mapping agencies such as United States Geological Survey and Ordnance Survey. The model supports standardized spatial predicates used in specifications from the Open Geospatial Consortium and interoperable services operated by institutions like Google, Microsoft, and Amazon Web Services.

Matrix Structure and Elements

The model represents spatial relations as a 3×3 intersection matrix with nine elements corresponding to intersections between the interior, boundary, and exterior of two geometries. Each cell records either the dimension of the intersection (−1 for empty, 0 for point, 1 for line, 2 for area) or a Boolean condition, depending on representation used in libraries such as JTS Topology Suite and GEOS. The nine entries map to ordered pairs drawn from {Interior, Boundary, Exterior} for geometry A and geometry B; this encoding enables comparison against canonical patterns used in standards published by the International Organization for Standardization and query languages like OGC Simple Features.

Topological Predicates and Queries

Common predicates derived from the matrix include Disjoint, Intersects, Touches, Crosses, Within, Contains, Overlaps, and Equals—operators exposed in implementations such as PostGIS, SpatiaLite, and GIS modules in QGIS and ArcGIS from Esri. Each predicate corresponds to specific constraints on matrix entries; for example, Contains requires that the intersection of A's interior with B's exterior be empty, a condition used in cadastral workflows by agencies like Land Registry (England and Wales) and spatial analytics by firms such as Esri and Atlassian-integrated platforms. Query languages and APIs in SQL extensions for spatial data allow WHERE clauses that invoke these predicates to filter datasets managed by systems like PostgreSQL, Oracle Database, and Microsoft SQL Server.

Computational Methods and Implementations

Algorithmic computation of the nine-intersection matrix relies on robust planar topology operations: polygon overlay, segment intersection, boundary extraction, and point-in-polygon tests. Libraries implementing these operations include JTS Topology Suite (Java), GEOS (C++), Shapely (Python bindings to GEOS), and native engines in PostGIS and SpatiaLite. Performance considerations drive use of spatial indexes such as R-tree and algorithms like sweep-line and plane-sweep employed in software from Boost C++ Libraries and projects like CGAL. Numerical robustness and handling of geodetic coordinates motivate techniques from geodesy work by National Geospatial-Intelligence Agency and precision-aware strategies used in OSGeo projects.

Examples and Use Cases

Applied examples span urban planning by municipalities like New York City Department of City Planning, environmental assessment projects by United Nations Environment Programme, routing and navigation by HERE Technologies and TomTom, and cadastral mapping by Land Registry (England and Wales). Use-case scenarios include detecting overlaps between zoning polygons, testing whether a road centerline crosses a protected-area boundary, and validating topological integrity in digitized parcel datasets. Educational references and case studies using DE-9IM are found in curricula at institutions such as Massachusetts Institute of Technology, University of Oxford, and ETH Zurich, and in GIS training resources from Esri.

Standards and Interoperability

DE-9IM is incorporated into the Open Geospatial Consortium Simple Features Access standard and the ISO 19125 family under International Organization for Standardization governance, enabling consistent semantics across implementations by vendors and open-source projects. Interoperability is further achieved through web service standards like OGC Web Feature Service and OGC Web Map Service, and exchange formats such as GeoJSON and GML where server and client software from Esri, QGIS, MapServer, and GeoServer implement compatible topological predicates. Compliance matrices and test suites maintained by the Open Geospatial Consortium and conformance testing by national bodies ensure consistent behavior in industrial, governmental, and research deployments.

Category:Spatial analysis Category:Geographic information systems Category:Topological data analysis