I'm happy to say that OverlayNG has landed on the JTS master branch! This is the culmination of over a year of work, and even more years of planning and design. It will appear in the upcoming JTS 1.18 release this fall.
As described in previous posts OverlayNG brings substantial improvements to overlay computation in JTS:
- A completely new codebase provides greater clarity, maintainability, and extensibility
- Pluggable noding supports various kinds of noding strategies including Fast Full-Precision Noding, Snapping and Snap-Rounding.
- Optimizations are built-in, including new ones such as Ring Clipping and Line Limiting.
- Additional functionality including Precision Reduction and Fast Coverage Union
All of these improvements are encapsulated in the new OverlayNGRobust class. It provides fully robust execution with excellent performance, via automated fallback through a series of increasingly robust noding strategies. This should solve a host of overlay issues reported over the years in various downstream projects such as GEOS, PostGIS, Shapely, R-sf and QGIS. (Many of these cases have been captured as XML tests for overlay robustness, to ensure that they are handled by the new code).
Initially the idea was to use OverlayNG as an opportunity to simplify and improve the semantics of overlay output, including:
- Sewing linear output node-to-node (to provide a full union)
- Ensuring output geometry is homogeneous (to allow easy chaining of overlay operations)
- Omitting lines created by topology collapse in polygonal inputs
In the end we decided that this change would have too much impact on existing tests and downstream code, so the default semantics are the same as the previous overlay implementation. However, the simplified semantics are available as a "strict" mode for overlay operations.
At the moment OverlayNG is not wired in to the JTS Geometry overlay operations, but is provided as a separate API. The plan is to provide a runtime switch to allow choosing which overlay code is used. This will allow testing in-place while avoiding potential impact on production systems. GeometryPrecisionReducer has been changed to use OverlayNG with Snap-Rounding, to provide more effective precision reduction.
GEOS has been tracking the OverlayNG codebase closely for a while now, which has been valuable to finalize the overlay semantics, and for finding and fixing issues. Having the code in JTS master gives the green light for downstream projects to do their own testing as well. There have been a few issues reported:
- A minor copy-and-paste variable name issue in HotPixel (which did not actually cause any failures, since it was masked by other logic)
- A clarification about the new behaviour of GeometryPrecisionReducer, revealed by an NTS test
- Most notably, a serious performance issue with Snap-Rounding of large geometries was identified and fixed by a member of the NTS project. This is quite interesting, so I'll discuss it in detail in another post.
After years of designing and developing improvements to overlay, it's great to see OverlayNG make its debut. Hopefully this will be the end of issues involving the dreaded TopologyException. And the new design will make it easier to build other kinds of overlay operations, including things like fast line clipping, split by line, coverage overlay... so stay tuned!
