JTS OverlayNG - Tolerant Topology Transformation

This is another in a series of posts about the new OverlayNG algorithm being developed for the JTS Topology Suite. (Previous ones are here and here).  Overlay is a core spatial function which allows computing the set-theoretic boolean operations of intersection, union, difference, and symmetric difference over all geometry types. OverlayNG introduces significant improvements in performance, robustness and code design.

JTS has always provided the ability to specify a fixed-precision model for computing geometry constructions (including overlay).  This ensures that output coordinates have a defined, limited precision.  This can reduce the size of data transfers and storage, and generally leads to cleaner, simpler geometric output.  The original overlay implementation had some issues with robustness, which were exacerbated by using fixed-precision.  One of the biggest improvements in OverlayNG is that fixed-precision overlay is now guaranteed to be fully robust.  This is achieved by using an implementation of the well-known snap-rounding noding paradigm. 

Geometric algorithms which operate in a fixed-precision model can encounter situations called topology collapse.  This happens when line segments and points become coincident due to vertices or intersection points being rounded.  The OverlayNG algorithm detects occurrences of topology collapse and transforms them into valid topology in the overlay result.

Topology collapse during overlay with a fixed precision model

As a bonus, handling topology collapse during the overlay process also allows it to be tolerated when present in the original input geometries.  This means that some kinds of "mildly" invalid geometry (according to the OGC model) are acceptable as input.  Invalid geometry is transformed to valid geometry during the overlay process.

Specifically,  input geometry may contain the following situations, which are invalid in the OGC geometry model:

• A ring which self-touches at discrete points (the so-called "inverted polygon" or "exverted hole")
• A ring which self-touches in one or more line segments
• Rings which touch other ones along one or more line segments 

Note that this does not extend to handling polygons that overlap, rather than simply touch.  These are "strongly invalid", and will trigger a TopologyException during overlay.

An interesting use for this capability is to process individual geometries.  By simply computing the union of a single geometry the geometry is transformed into an OGC-valid geometry.  In this way OverlayNG functions as a (partial) "MakeValid" operation.  

A polygon which self-touches in a line transforms to a valid polygon with a hole

A polygon which self-touches in a point transforms to a valid polygon with a hole

A collection of polygons which touch in lines transforms to a valid polygon with a hole

Moreover, some spatial systems use geometry models which do not conform to the OGC semantics.  Some systems (such as ArcGIS) actually specify the use of inverted polygons and exverted holes in their topology model.  And in days of yore there were systems which were unable to model holes explicitly, and so used a "connected hole" topology hack (AKA "lollipop holes".) This represented  holes as an inversion connected by a zero-width corridor to the polygon shell. Both of these models are accepted by OverlayNG. Thus it provides a convenient way to convert from these non-standard models into OGC-valid topology. 

This is one more reason why overlay is the real workhorse of spatial data processing!