Geometry clipping - summary issue

[systemed]

This is an umbrella issue to summarise current clipping issues with tilemaker.

History:

• Use faster bbox-specialised clipping algorithm #482 introduced the Sutherland-Hodgman algorithm for clipping polygons. This is many times faster than boost::geometry's intersection, but can leave line artefacts (0-width borders) around the clipping rectangle.
• These 0-width borders upset Maplibre GL Native (Vector tile generation faulty in edge cases ? #574)
• Use custom correct (make_valid) for clipping #575 uses kleunen's custom correct code (make_valid) to eliminate these borders
• Update to latest version of kleunen/boost_geometry_correct #581 updates to the latest version of this code

Current status:

• Some tiles are still broken (PR575 seems to break shapefile #580)
• Some make_valid operations are taking too long to finish (Tilemaker Reading Error #592, PR575 seems to break shapefile #580)

The most obvious solution is to move to a clipping algorithm which is still fast but doesn't produce degenerate geometries. Some options:

• Maillot's algorithm claims to be faster and can be extended (section 5) to produce fewer degenerate edges
  • JavaScript implementation: https://github.com/forallx-algorithms/maillot-polygon-clipping-algorithm
  • C++ implementation: https://github.com/edwinwijaya94/uts-grafika/blob/master/maillot.cpp
  • Walkthrough and pseudocode: http://what-when-how.com/computer-graphics-and-geometric-modeling/clipping-basic-computer-graphics-part-4/
• Foster-Hormann-Popa is an extension of Greiner-Hormann to avoid degenerate polygons, and looks very promising
  • C++ implementation: https://github.com/Fribur/FosterHormannPopaClipping
• The Vatti algorithm is famously robust but may be slow
  • Angus Johnson's well-known Clipper library
  • TriClipper is a header-only implementation

Other possible fixes/improvements:

• Changing boost::geometry #define feature flags in geom.h may improve results in some (but not all) cases
  • remove BOOST_GEOMETRY_INCLUDE_SELF_TURNS
  • add BOOST_GEOMETRY_NO_ROBUSTNESS
• Identify when to drop down to boost::geometry::intersection (slower but doesn't create artefacts)
• There's a paper on "Removal of Artifacts from Polygons Clipped Using the Sutherland-Hodgman Polygon Clipping Algorithm" (J. Michael McGrew) but I haven't been able to find the full paper, only the abstract
• Identify test case for correct that's causing it to be so slow
• Allow user to send a signal to interrupt correct, without aborting tile writing
• Cancel correct after a certain length of time

Known problem locations:

• lon 24.9829-25.0049, lat 37.7533-37.7707 (near Athens) fails at several zoom levels

[systemed]

I have reverted #581 for now. This solves the hangs we were seeing (e.g. #592) though at the cost of some geometry breakage. The commit in correct that causes the hangs is kleunen/boost_geometry_correct@008154a.

[systemed]

Clipping seems to be in a good state at the moment thanks to falling back to boost::geometry::intersection and proactively filtering out small rings. I'll therefore close this but it may be a useful collection of links for the future.