RelateNG

The upcoming 3.13 release of GEOS includes a complete re-write of the “boolean predicates”, called “RelateNG”. The boolean predicates are pairwise tests for geometries that return true/false answers. “Intersects”, “Contains”, “Touches” are all examples of boolean predicates.

The old implementation in JTS and GEOS operated by building a complete topological relationship graph between the two inputs, then reading the result off the graph. However, computing the whole graph every time is computationally expensive, and the results of many predicates can be determined without a full graph – the first time you hit an edge intersection, you know that geometries intersect, and you do not need to do any more calculations.

The new implementation, RelateNG, has a number of advantages:

• Efficient short-circuited evaluation of topological predicates (including matching custom DE-9IM matrix patterns)
• Optimized repeated evaluation of predicates against a single geometry via * cached spatial indexes (AKA “prepared mode”)
• Robust computation (only point-local geometry topology is computed, so invalid topology does not cause failures)
• GeometryCollection inputs containing mixed types and overlapping polygons are supported, using union semantics.
• Zero-length LineStrings are treated as being topologically identical to Points.
• Support for BoundaryNodeRules.

The port to GEOS blends the new functionality with the existing implementation of PreparedGeometry and the C-API.

• All one-shot predicates are now handled by RelateNG, and should in general be faster. These are called in Geometry.cpp.
• The default implementation in of prepared geometry, BasicPreparedGeometry.cpp now uses the RelateNG implementations. The existing implementations in PreparedPolygon.cpp, etc, still over-ride the defaults, because they are currently slightly faster. If/when the RelateNG implementations are optimized, they can be replaced.
• The C-API already had functions for things like GEOSPreparedTouches() even though the “touches” predicate had no prepared implementation, and was just calling the non-optimized predicate. These functions now end up using the RelateNG prepared implementation, so they should automatically be much faster.
• The C-API has been expanded with two new functions, GEOSPreparedRelate() and GEOSPreparedRelatePattern(), exposing a new feature of RelateNG, the ability to do accelerated relate matrix calculations.

The RelateNG work has been run against the entire regression suite and returns exactly the same answers over all our collected 20 years of tests.

• The only exception is the handling of a zero-length LineString, which is now treated as logically equivalent to a point.

The RelateNG code is new and there are no doubt lots of places in the implementation that can still be tightened up. The existing pair-wise predicates can be considered deprecated, as the new implementation is faster and just as correct. The existing prepared geometry implementation is still faster, for the cases it supports, but for all the unsupported cases RelateNG now provides faster default implementations.