Geometry clipping - summary issue

[systemed]

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

History:

• 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 (#574)

• 575 uses kleunen's custom correct code (make_valid) to eliminate these borders

• 581 updates to the latest version of this code

Current status:

• Some tiles are still broken (#580)
• Some make_valid operations are taking too long to finish (#592, #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 https://github.com/kleunen/boost_geometry_correct/commit/008154ab8116f8399b29e322e012ee8ddb0b13c4.

[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.