Fix invalid polygon geometries (intersecting & colinear segments)

[mourner]

Clipping and simplification of polygon geometries often makes the polygons non-simple (with intersecting & touching segments). This is hard to handle when trying to tesselate such polygons for rendering (both on native & JS). Native uses Clipper (specifically SimplifyPolygon with StrictlySimple) to fix the geometries. It has a port for JS, but applying it there would take a lot of precious CPU time, so it would be great to fix those problems on the VT side, using Clipper there.

Intersecting edges after simplification:

Degenerate edges after clipping:

cc @springmeyer @yhahn

[springmeyer]

Thanks, yes, this needs revisited. We are using only AGG-based clipping still which - by design - leads to the edges you see. Not a blocker if the tile is slightly buffered and they can be discarded out of sight but yes, certainly not ideal for the reasons you detail. The intended plan early on was to use Clipper or Boost.Geometry but we ran into blocking hangs and crashing bugs, respectively. However both toolkits have had a number of releases since so hopefully we can move to Clipper or Boost.Geometry in upcoming releases.

[mourner]

Awesome, looking forward to it!

[mourner]

@springmeyer btw, any idea of when you might try to approach this? Just wondering if it's worth spending a lot of effort trying to get around the degeneracies on the JS side, or would it be much easier to fix that on the VT side.

[springmeyer]

@mourner - Definitely seems ideal to fix on the generation side. That said ideally i'd take a closer look at this not till end of sept/early oct - given other things in the pipeline.

[mpickell]

@springmeyer I was directed to this issue from the mapbox/vector-tile-js#14 issue. Is there any update?

[springmeyer]

@mpickell high on the list of priorities so this will get attention soon, but I don't have an ETA yet.

[springmeyer]

Update here:

degenerate edges

We have a plan to fix degenerate edges which is to move away from the agg clipper to a better clipping library (The AGG clipper leaves degenerate edges by design). Since we need to support complex/potentially non-simple and self-intersecting polygons we cannot use boost::geometry::intersection. The clipping algorithm we choose also needs needs to maintain ring order (per #59 (comment) and mapnik/mapnik#2756). Therefore my sense of the best plan is to use the clipper library along with its custom clipper.PolyTree structure

To mitigate the performance hit of this new clipper, the plan is to simplify before clipping. To simplify before clipping the plan is to use boost::geometry::simplify which is working in #94 but needs more of a robust framework to stand on which is being tracked at mapnik/mapnik#2753

invalid polygons

Polygons with degenerate/colinear eges or self-intersections before they arrive to Mapnik are going to be much harder to fix. My understand from talking with @mourner is that the latest earcut library (that we are targeting) is able to handle a variety of self-intersections. But we can consider using clipper SimplifyPolygon with StrictlySimple. Once mapnik/mapnik#2753 is in place I'll be in a better place to test plugging in this type of geometry fixing to assess if it is viable (or too slow, not robust enough).

In the meantime anyone that has small testcases of invalid polygons you think should still be supported, please share them in the form of GeoJSON files.