Chapter 5. Spatial Queries

According to the OpenGIS Simple Features Implementation Specification for SQL, "the basic approach to comparing two geometries is to make pair-wise tests of the intersections between the Interiors, Boundaries and Exteriors of the two geometries and to classify the relationship between the two geometries based on the entries in the resulting 'intersection' matrix."

In the theory of point-set topology, the points in a geometry embedded in 2-dimensional space are categorized into three sets:

The Dimensionally Extended 9-Intersection Model (DE-9IM) describes the spatial relationship between two geometries by specifying the dimensions of the 9 intersections between the above sets for each geometry. The intersection dimensions can be formally represented in a 3x3 intersection matrix.

For a geometry g the Interior, Boundary, and Exterior are denoted using the notation I(g), B(g), and E(g). Also, dim(s) denotes the dimension of a set s with the domain of {0,1,2,F}:

Using this notation, the intersection matrix for two geometries a and b is:

Visually, for two overlapping polygonal geometries, this looks like:

	Interior Boundary Exterior Interior dim( I(a) ∩ I(b) ) = 2 dim( I(a) ∩ B(b) = 1 dim( I(a) ∩ E(b) ) = 2 Boundary dim( B(a) ∩ I(b) ) = 1 dim( B(a) ∩ B(b) ) = 0 dim( B(a) ∩ E(b) ) = 1 Exterior dim( E(a) ∩ I(b) ) = 2 dim( E(a) ∩ B(b) ) = 1 dim( E(a) ∩ E(b) = 2

Reading from left to right and top to bottom, the intersection matrix is represented as the text string '212101212'.

For more information, refer to:

To make it easy to determine common spatial relationships, the OGC SFS defines a set of named spatial relationship predicates. PostGIS provides these as the functions ST_Contains, ST_Crosses, ST_Disjoint, ST_Equals, ST_Intersects, ST_Overlaps, ST_Touches, ST_Within. It also defines the non-standard relationship predicates ST_Covers, ST_CoveredBy, and ST_ContainsProperly.

Spatial predicates are usually used as conditions in SQL WHERE or JOIN clauses. The named spatial predicates automatically use a spatial index if one is available, so there is no need to use the bounding box operator && as well. For example:

SELECT city.name, state.name, city.geom
FROM city JOIN state ON ST_Intersects(city.geom, state.geom);

For more details and illustrations, see the PostGIS Workshop.

In some cases the named spatial relationships are insufficient to provide a desired spatial filter condition.

For example, consider a linear dataset representing a road network. It may be required to identify all road segments that cross each other, not at a point, but in a line (perhaps to validate some business rule). In this case ST_Crosses does not provide the necessary spatial filter, since for linear features it returns true only where they cross at a point. A two-step solution would be to first compute the actual intersection (ST_Intersection) of pairs of road lines that spatially intersect (ST_Intersects), and then check if the intersection's ST_GeometryType is 'LINESTRING' (properly dealing with cases that return GEOMETRYCOLLECTIONs of [MULTI]POINTs, [MULTI]LINESTRINGs, etc.). Clearly, a simpler and faster solution is desirable.

A second example is locating wharves that intersect a lake's boundary on a line and where one end of the wharf is up on shore. In other words, where a wharf is within but not completely contained by a lake, intersects the boundary of a lake on a line, and where exactly one of the wharf's endpoints is within or on the boundary of the lake. It is possible to use a combination of spatial predicates to find the required features: ST_Contains(lake, wharf) = TRUE ST_ContainsProperly(lake, wharf) = FALSE ST_GeometryType(ST_Intersection(wharf, lake)) = 'LINESTRING' ST_NumGeometries(ST_Multi(ST_Intersection(ST_Boundary(wharf), ST_Boundary(lake)))) = 1 ... but needless to say, this is quite complicated.

These requirements can be met by computing the full DE-9IM intersection matrix. PostGIS provides the ST_Relate function to do this:

SELECT ST_Relate( 'LINESTRING (1 1, 5 5)',
                  'POLYGON ((3 3, 3 7, 7 7, 7 3, 3 3))' );
st_relate
-----------
1010F0212

To test a particular spatial relationship, an intersection matrix pattern is used. This is the matrix representation augmented with the additional symbols {T,*}:

Using intersection matrix patterns, specific spatial relationships can be evaluated in a more succinct way. The ST_Relate and the ST_RelateMatch functions can be used to test intersection matrix patterns. For the first example above, the intersection matrix pattern specifying two lines intersecting in a line is '1*1***1**':

-- Find road segments that intersect in a line
SELECT a.id
FROM roads a, roads b
WHERE a.id != b.id
      AND a.geom && b.geom
      AND ST_Relate(a.geom, b.geom, '1*1***1**');

For the second example, the intersection matrix pattern specifying a line partly inside and partly outside a polygon is '102101FF2':

-- Find wharves partly on a lake's shoreline
SELECT a.lake_id, b.wharf_id
FROM lakes a, wharfs b
WHERE a.geom && b.geom
      AND ST_Relate(a.geom, b.geom, '102101FF2');