This guide provides an introduction to the Dimensionally Extended Nine Intersection Matrix (DE-9IM) model on which the ILcd2DAdvancedBinaryTopology interface is based. An understanding of the key concepts of this model is required to create custom-defined topological relations.

You can find more information on the DE-9IM model in the OpenGIS Implementation Specification for Geographic information - Simple feature access.

Interior, boundary, and exterior

The DE-9IM model defines three disjoint sets for all shapes: the interior, the boundary, and the exterior. The interior and boundary sets are defined as follows for the following shapes:

  • Point

    • Interior: the point itself (0-dimensional).

    • Boundary: empty set, points are defined to have no boundary.

  • Open polyline

    • Interior: all points and segments, except the two endpoints (1-dimensional).

    • Boundary: the two endpoints (0-dimensional).

  • Closed polyline

    • Interior: all points and segments (1-dimensional).

    • Boundary: empty set.

  • Polygon

    • Interior: all points of the polygon, excluding the contour (2-dimensional).

    • Boundary: all points belonging to the contour of the polygon (1-dimensional).

  • Complex polygon

    • Interior: all points of the complex polygon, excluding the contours of the polygons (2-dimensional).

    • Boundary: all points belonging to at least one of the contours of the polygons (1-dimensional).

The following image provides a graphical illustration of these:

interior exterior boundary
Figure 1. Illustration of the interior, boundary, and exterior of different shapes

Intersection matrix

The (dimensionally extended nine) intersection matrix stores information about the way two shapes are topologically related. More specifically, the rows (columns) correspond with the interior, boundary, and exterior respectively of the first (second) shape. As a result, the DE-9IM is a 3x3 matrix containing nine elements.

This is illustrated in the table below where the first and second shape are denoted with S1 and S2, respectively.

S2 Interior

S2 Boundary

S2 Exterior

S1 Interior

*

*

*

S1 Boundary

*

*

*

S1 Exterior

*

*

*

Each matrix element contains the dimension of the intersection of the two corresponding regions. This dimension has one of the following values:

  • F: no intersection (False)

  • 0: 0-dimensional intersection

  • 1: 1-dimensional intersection

  • 2: 2-dimensional intersection

The image below shows an example of an intersection matrix of a complex polygon and a (poly)line. The complex polygon is the first shape, the line is the second shape.

shapes with de9im matrix
Figure 2. Example of an intersection matrix of a complex polygon and a (poly)line

Intersection matrix pattern

In the DE-9IM model, binary topological relations between two shapes are evaluated by:

  1. computing the intersection matrix of these two shapes

  2. checking whether this intersection matrix fulfills certain conditions

Each binary topological relation imposes its own set of conditions on the intersection matrix. In its simplest form, these conditions can be formulated as a single matrix pattern. A matrix pattern consists of a set of 9 pattern values, one for each element of the intersection matrix.

This pattern values can be one of the following:

  • T: the corresponding matrix element should be 0, 1 or 2

  • F: the corresponding matrix element should be F

  • *: the corresponding matrix element can be anything

  • 0: the corresponding matrix element should be 0

  • 1: the corresponding matrix element should be 1

  • 2: the corresponding matrix element should be 2

A single matrix pattern can be represented as a string of nine values in row major order (row by row).

For example, two shapes are disjoint if the interior and boundary of the first shape have no point in common with either the interior or boundary of the second shape. Therefore, the disjoint relation imposes that the first two elements of both the first and second row of the intersection matrix should be F(alse). This means that the disjoint relation corresponds with the single matrix pattern FF*FF****. The question whether two shapes are disjoint can then be answered by computing their intersection matrix and checking whether it matches this matrix pattern.

For instance, the complex polygon and polyline shown in Figure 2, “Example of an intersection matrix of a complex polygon and a (poly)line” have an intersection matrix 1020F1102 which does not match the pattern FF*FF**** so that we correctly find that both shapes are not disjoint.

Note that the interface ILcdIntersectionMatrixPattern in the Advanced GIS Engine component is not restricted to such a simple matrix pattern as mentioned above. An ILcdIntersectionMatrixPattern represents any set of conditions imposed on an intersection matrix of two shapes. In more complex cases, these conditions could be a logical combination of simple matrix patterns and/or depend on other parameters such as the dimension of the involved shapes. You can find an example of a more complex intersection matrix pattern in Creating a custom topology relation.