There is an elegant mathematical theory of binary relations. Homogeneous relations are an important subclass of binary relations in which both domains are the same. A homogeneous relation R is a subset of all ordered pairs (x,y) with x and y elements of the domain. This can be thought of as a boolean-valued function R(x,y), which is true if the pair has the relationship and false if not.
The restricted structure of homogeneous relations allows describing them by various properties, including:
Reflexive - R(x, x) is always true
Irreflexive - R(x, x) is never true
Symmetric - if R(x, y), then R(y, x)
Antisymmetric - if R(x, y) and R(y, x), then x = y
Transitive - if R(x, y) and R(y, z), then R(x, z)
The Dimensionally Extended 9-Intersection Model (DE-9IM) represents the topological relationship between two geometries.
Various useful subsets of spatial relationships are specified by named spatial predicates. These are the basis for spatial querying in many spatial systems including the JTS Topology Suite, GEOS and PostGIS.
The spatial predicates are homogeneous binary relations over the Geometry domain They can thus be categorized in terms of the relational properties above. The following table shows the properties of the standard predicates:
Predicate | Reflexive / Irreflexive | Symmetric / Antisymmetric | Transitive |
---|---|---|---|
Equals | R | S | T |
Intersects | R | S | - |
Disjoint | R | S | - |
Contains | R | A | - |
Within | R | A | - |
Covers | R | A | T |
CoveredBy | R | A | T |
Crosses | I | S | - |
Overlaps | I | S | - |
Touches | I | S | - |
Notes
- Contains and Within are not Transitive because of the quirk that "Polygons do not contain their Boundary" (explained in this post). A counterexample is a Polygon that contains a LineString lying in its boundary and interior, with the LineString containing a Point that lies in the Polygon boundary. The Polygon does not contain the Point. So Contains(poly, line) = true and Contains(line, pt) = true, but Contains(poly, pt) = false. The predicates Covers and CoveredBy do not have this idiosyncrasy, and thus are transitive.
This comment has been removed by the author.
ReplyDeleteI'm not seeing how the Irreflexive definition is wrong?
ReplyDelete