Predicates and DE-9IM
Spatial predicates answer yes/no questions about the relation of two geometries: do they intersect, does one contain the other, do they only touch. All of them are based on the full DE-9IM model of OGC and NetTopologySuite (ADR 0013) and compute exactly on the input coordinates, without a grid.
The intersection matrix
For two geometries a and b, a.Relate(b) returns an IntersectionMatrix: for each combination of interior (I), boundary (B) and exterior (E) of a and b, the dimension of their intersection (F = empty, 0 = points, 1 = lines, 2 = areas).
var square = Wkt.Read<IPolygon2D>("POLYGON((0 0, 10 0, 10 10, 0 10, 0 0))");
var edge = Wkt.Read<IPolyline2D>("LINESTRING(0 0, 10 0)"); // lies on the boundary of the square
Console.WriteLine(square.Contains(edge)); // False - DE-9IM: no point of the edge lies in the interior
Console.WriteLine(square.Covers(edge)); // True - boundary points count
Console.WriteLine(square.Touches(edge)); // True
Console.WriteLine(square.Relate(edge)); // FF2101FF2
The matrix is written row by row in the order I, B, E of a against I, B, E of b (II IB IE BI BB BE EI EB EE); the nine values are also available as properties (II, IB, …, EE). a.Relate(b, pattern) checks the matrix against a pattern of nine characters: T (not empty), F (empty), * (anything), 0, 1, 2 (exactly this dimension). For example T*F**F*** is "within".
Reading a pattern
A pattern has nine characters, one for each pair of the three parts of a and the three parts of b. The three parts of a geometry are its interior (I), its boundary (B) and its exterior (E): for an area the inside, the edge and the rest of the plane; for a line everything except its two end points, the end points, and the rest; for a point the point itself, nothing, and the rest. The nine positions, row by row:
interior of b |
boundary of b |
exterior of b |
|
|---|---|---|---|
interior of a |
1st (II) |
2nd (IB) |
3rd (IE) |
boundary of a |
4th (BI) |
5th (BB) |
6th (BE) |
exterior of a |
7th (EI) |
8th (EB) |
9th (EE) |
Each character says what the two parts share:
| Character | Means |
|---|---|
T |
they share something (points, a line or an area; the dimension does not matter) |
F |
they share nothing (empty) |
* |
does not matter |
0, 1, 2 |
they share exactly points (0), a line (1) or an area (2) |
T and F do not say that the predicate is true or false; the predicate is true if all nine positions fit its pattern. As an example, T*F**F*** is the pattern of Within: T at II, the interiors share something; F at IE, the interior of a shares nothing with the exterior of b; F at BE, neither does the boundary of a; the rest does not matter. In words: the interiors meet, and nothing of a sticks out of b. The matrix FF2101FF2 of the square and its edge above reads the same way: II F (the interiors share nothing), IE 2 (the inside of the square shares an area with the exterior of the edge), BI 1 (the boundary of the square and the interior of the edge share a line: the edge lies on it), BB 0 (the end points of the edge touch the boundary), and so on.
The predicates
All predicates are extension methods on IGeometry2D:
| Predicate | Meaning |
|---|---|
Intersects |
the geometries share at least one point |
Disjoint |
the geometries share no point (FF*FF****) |
Contains(a, b) |
b lies in a and they share an interior point (T*****FF*) |
Within(a, b) |
a lies in b (T*F**F***) |
Covers(a, b) |
no point of b lies outside a; boundary points count |
CoveredBy(a, b) |
no point of a lies outside b; boundary points count |
Touches |
the geometries meet only in boundary points |
Crosses |
the geometries cross (OGC; depends on the dimensions) |
Overlaps |
geometries of equal dimension overlap partially |
EqualsTopo |
the geometries are topologically equal (T*F**FFF*); false if one is empty |
Contains versus Covers is the difference that surprises most people: a polygon does not contain a line that lies on its boundary (the line has no point in the interior), but it covers it. If you mean "lies inside, the boundary counts", use Covers/CoveredBy.
Rules that apply to all predicates:
- Empty geometries. If a geometry is empty, only
Disjointis true; all other predicates are false, andRelatereturns a matrix of onlyF. - Area by even-odd. Areas follow the even-odd rule (ADR 0003).
- Line boundaries by mod-2. The end points of a line are its boundary, closed paths have no boundary, and for a polyline with several paths only an odd number of path ends at a point counts.
- Invalid input is handled deterministically and without exceptions, but without a guarantee that the predicates are consistent with one another.
The situations
The tables on the pages of the single predicates use the same 27 situations. a is the first, b the second geometry; the matrix is a.Relate(b) (The intersection matrix). A cell shows true where the predicate holds.
| Situation | Matrix | Intersects | Disjoint | Contains | Within | Covers | CoveredBy | Touches | Crosses | Overlaps | EqualsTopo |
|---|---|---|---|---|---|---|---|---|---|---|---|
| A point inside an area | 0FFFFF212 |
true | true | true | |||||||
| A point on the edge of an area | F0FFFF212 |
true | true | true | |||||||
| A point outside an area | FF0FFF212 |
true | |||||||||
| A point in a hole of an area | FF0FFF212 |
true | |||||||||
| A point on a line (not at its end) | 0FFFFF102 |
true | true | true | |||||||
| A point at the end of a line | F0FFFF102 |
true | true | true | |||||||
| A point at a bend (a vertex) inside a line | 0FFFFF102 |
true | true | true | |||||||
| A point beside a line | FF0FFF102 |
true | |||||||||
| Two equal points | 0FFFFFFF2 |
true | true | true | true | true | true | ||||
| Two lines that cross | 0F1FF0102 |
true | true | ||||||||
| Two lines that meet end to end | FF1F00102 |
true | true | ||||||||
| A line that ends on another line (a T) | FF10F0102 |
true | true | ||||||||
| Two lines that run together for a stretch | 1010F0102 |
true | true | ||||||||
| Two equal lines (one reversed) | 1FFF0FFF2 |
true | true | true | true | true | true | ||||
| A line inside an area | 1FF0FF212 |
true | true | true | |||||||
| A line that crosses the edge of an area | 1010F0212 |
true | true | ||||||||
| A line along the edge of an area | F1FF0F212 |
true | true | true | |||||||
| A line outside an area that ends on its edge | FF1F00212 |
true | true | ||||||||
| A line outside an area | FF1FF0212 |
true | |||||||||
| A small area inside a large one | 2FF1FF212 |
true | true | true | |||||||
| An area inside another, touching its edge from inside | 2FF11F212 |
true | true | true | |||||||
| Two areas that share an edge | FF2F11212 |
true | true | ||||||||
| Two areas that touch at a corner | FF2F01212 |
true | true | ||||||||
| Two areas that overlap | 212111212 |
true | true | ||||||||
| Two equal areas (other start point and direction) | 2FFF1FFF2 |
true | true | true | true | true | true | ||||
| Two areas apart | FF2FF1212 |
true | |||||||||
| An area inside a hole of another | FF2FF1212 |
true |
The geometries
| Situation | a |
b |
|---|---|---|
| A point inside an area | POINT (5 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A point on the edge of an area | POINT (10 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A point outside an area | POINT (15 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A point in a hole of an area | POINT (5 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0), (4 4, 6 4, 6 6, 4 6, 4 4)) |
| A point on a line (not at its end) | POINT (5 0) |
LINESTRING (0 0, 10 0) |
| A point at the end of a line | POINT (0 0) |
LINESTRING (0 0, 10 0) |
| A point at a bend (a vertex) inside a line | POINT (5 0) |
LINESTRING (0 0, 5 0, 5 5) |
| A point beside a line | POINT (5 1) |
LINESTRING (0 0, 10 0) |
| Two equal points | POINT (1 1) |
POINT (1 1) |
| Two lines that cross | LINESTRING (0 0, 10 10) |
LINESTRING (0 10, 10 0) |
| Two lines that meet end to end | LINESTRING (0 0, 5 5) |
LINESTRING (5 5, 10 0) |
| A line that ends on another line (a T) | LINESTRING (5 0, 5 5) |
LINESTRING (0 0, 10 0) |
| Two lines that run together for a stretch | LINESTRING (0 0, 10 0) |
LINESTRING (5 0, 15 0) |
| Two equal lines (one reversed) | LINESTRING (0 0, 10 0) |
LINESTRING (10 0, 0 0) |
| A line inside an area | LINESTRING (2 2, 8 8) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A line that crosses the edge of an area | LINESTRING (5 5, 15 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A line along the edge of an area | LINESTRING (0 0, 10 0) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A line outside an area that ends on its edge | LINESTRING (10 5, 15 5) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A line outside an area | LINESTRING (12 0, 12 10) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| A small area inside a large one | POLYGON ((2 2, 4 2, 4 4, 2 4, 2 2)) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| An area inside another, touching its edge from inside | POLYGON ((0 0, 5 0, 5 5, 0 5, 0 0)) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
| Two areas that share an edge | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((10 0, 20 0, 20 10, 10 10, 10 0)) |
| Two areas that touch at a corner | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((10 10, 20 10, 20 20, 10 20, 10 10)) |
| Two areas that overlap | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((5 0, 15 0, 15 10, 5 10, 5 0)) |
| Two equal areas (other start point and direction) | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((10 0, 10 10, 0 10, 0 0, 10 0)) |
| Two areas apart | POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0)) |
POLYGON ((20 0, 30 0, 30 10, 20 10, 20 0)) |
| An area inside a hole of another | POLYGON ((4.5 4.5, 5.5 4.5, 5.5 5.5, 4.5 5.5, 4.5 4.5)) |
POLYGON ((0 0, 10 0, 10 10, 0 10, 0 0), (4 4, 6 4, 6 6, 4 6, 4 4)) |
Exactness versus overlays
Predicates compute exactly on the coordinates you pass. Overlays round to a grid (Overlays, fill rules and the grid). For near-touches below the grid size, a.Intersects(b) can therefore be true while a.Intersection(b) is empty.
Exactness in practice, and the alternatives with a tolerance
The predicates demand numerical exactness: Intersects is true only if the two geometries share a point to the last bit of their coordinates. This is what makes the results reliable and consistent with each other, and it is what NetTopologySuite and JTS do. With measured or computed data it is almost never met: a coordinate is a rounded double, a point that you place on a line by clicking, by projecting or by computing lies, say, 4e-16 beside it, and a boundary shared by two parcels is only as exact as the two surveys. A point on a vertex is exact, because it has the very same numbers; a point on a segment is practically never exact.
If "close enough" is what you mean, which for survey data it is, say so with a tolerance. The library has no global tolerance for the predicates; it has the tools to ask for one:
double t = 0.01; // the tolerance, in the unit of your coordinates (here 1 cm)
bool intersects = a.IsWithinDistance(b, t); // Intersects: closer than t
bool disjoint = !a.IsWithinDistance(b, t); // Disjoint: farther than t
bool contains = a.Buffer(t).Contains(b); // Contains: b is in a, up to t over the edge
bool within = b.Buffer(t).Contains(a); // Within
bool covers = a.Buffer(t).Covers(b); // Covers
bool coveredBy = b.Buffer(t).Covers(a); // CoveredBy
bool touches = a.IsWithinDistance(b, t) && !a.Buffer(-t).Intersects(b); // Touches (areas): they meet, and overlap by less than t
bool overlaps = a.Buffer(-t).Intersects(b.Buffer(-t)) // Overlaps (areas): they overlap by more than t,
&& !a.Buffer(t).Covers(b) && !b.Buffer(t).Covers(a); // and neither lies in the other
bool equal = a.HausdorffDistance(b) <= t; // EqualsTopo: no vertex of one is farther than t from the other
| Predicate | With a tolerance t |
Reads as |
|---|---|---|
Intersects |
a.IsWithinDistance(b, t) |
the distance is at most t |
Disjoint |
!a.IsWithinDistance(b, t) |
the distance is more than t |
Contains(a, b) |
a.Buffer(t).Contains(b) |
b lies in a, or sticks out by at most t |
Within(a, b) |
b.Buffer(t).Contains(a) |
a lies in b, or sticks out by at most t |
Covers(a, b) |
a.Buffer(t).Covers(b) |
as Contains, boundary points count |
CoveredBy(a, b) |
b.Buffer(t).Covers(a) |
as Within, boundary points count |
Touches (areas) |
a.IsWithinDistance(b, t) && !a.Buffer(-t).Intersects(b) |
they meet, and overlap by less than t |
Overlaps (areas) |
a.Buffer(-t).Intersects(b.Buffer(-t)) && !a.Buffer(t).Covers(b) && !b.Buffer(t).Covers(a) |
they overlap by more than t, neither lies in the other |
EqualsTopo |
a.HausdorffDistance(b) <= t |
no vertex is farther than t from the other geometry (see below) |
Crosses, Relate |
none | see below |
Notes on the table:
IsWithinDistancestops as soon as it knows the answer and checks the envelopes first, so it is cheap. For many queries against one geometry usePrepare()andprepared.IsWithinDistance(b, t). None of these calls changesaorb; the buffers are new geometries.Bufferis the expensive part of the alternatives. For many tests against the samea, computea.Buffer(t)(anda.Buffer(-t)) once and keep it.Buffer(-t)shrinks an area; it works for polygons, not for lines or points, soTouchesandOverlapsas written are for areas. For a line or a point use the distance: they touch ifIsWithinDistance(b, t).HausdorffDistanceis discrete (it looks at vertices and, with adensifyFractionbelow 1, at points in between) and a lower bound; passdensifyFraction(for example 0.1) if the geometries have long segments. A vertex on a vertex is the case it decides exactly.CrossesandRelatehave no simple counterpart in distances: a crossing or a DE-9IM matrix is a statement about the interiors, and "almost crossing" has no single meaning. Ask for what you mean:IsWithinDistancefor "they meet", andNearestPointsfor where.- Or snap first, and ask the exact question (ADR 0046):
a.Touches(b.SnapTo(a, t, SnapMode.Vertices))moves the vertices ofbwithintofaonto it and inserts the vertices ofainto the segments ofb, so that a shared boundary becomes exact. This works for every predicate and forRelate, keeps the meaning of the exact predicates, and is the step that also helps the overlays andCut; it changesbby up tot. - To make data exact instead of the question tolerant, round it once to a grid on import (
ReducePrecision(0.01)). That makes vertices that lie within a cell identical, which helps where geometries meet at vertices, but it does not help a point on the middle of a segment (Measures and constructions).
The playground shows the distance next to every predicate for this reason, names the alternative with a tolerance below it, and says so when a false is only a rounding difference.
Repeated predicates: Prepare()
If you test many geometries against the same one (for example a polygon against thousands of points), prepare it once:
// a and b are the two polygons from the quick start.
// Several expensive predicates against the same geometry: prepare it once.
PreparedGeometry prepared = a.Prepare();
bool inside = prepared.Contains(Wkt.Read<IPolygon2D>("POLYGON((1 1, 2 1, 2 2, 1 2, 1 1))"));
// Full DE-9IM: matrix and pattern matching.
string matrix = a.Relate(b).ToString(); // "212101212"
A PreparedGeometry copies a snapshot of the coordinates and builds a segment index (and a point-in-polygon structure) from it. Later changes to the host object have no effect on it, which matters because host geometries are mutable. It offers Intersects, Disjoint, Contains, Covers, Within, CoveredBy and Touches, always with the same results as the unprepared predicates; the fast paths are used for Intersects/Disjoint and point-in-area, everything else runs through the exact Relate. A PreparedGeometry is thread-safe after construction (ADR 0024): prepare it once and share it between threads. It also answers Distance, IsWithinDistance and NearestPoints against other geometries, with the same results as the unprepared methods (only among equally near pairs may the nearest points differ).