FYI, I just posted this as a new item in libgeos.org <http://libgeos.org/>
> > 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](https://lin-ear-th-inking.blogspot.com/2024/05/jts-topological-relationships-next.html), > 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](https://lin-ear-th-inking.blogspot.com/2024/05/relateng-performance.html) > 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 implentations.
