Polygon clipping and validation over integer coordinates

[Algunenano]

Comes from ​https://trac.osgeo.org/geos/ticket/959

To generate MVT geometries, Postgis transforms the input geometries into the MVT coordinate system (coordinates aren't absolute, but relative to the tile, the y axis is reverted with 0,0 being the top left, and only integer values can be used), clips them to the tile if required and transforms them to have a valid output.

Doing this using GEOS has proven to be extremely hard for several reasons:

• GEOSClipByRect is fast, but only guarantees a valid output on valid input. GEOSIntersection is order of magnitude slower and also requires valid input. Since making a polygon valid is an even slower operation, there are several hacks trying to detect the issue and work around the limits of GEOSClipByRect.

• Both GEOSClipByRect and GEOSMakeValid (which Postgis currently doesn't use, but the issue is the same) can add new points that require double precision (not integers), which then require a new operation and rechecking validation. You can guess that the performance in those cases is terrible. You can even get a polygon that is valid, becomes invalid when using int precision, becomes valid when calling MakeValid but using doubles, then invalid with ints and you can keep going ad eternum.

Currently, I've introduced an extra library in Postgis, Wagyu, to deal with this since it provides fast clipping and, more importantly, fast polygon validation with int coordinates; but ideally this could be provided by GEOS to reduce the dependencies.

I've talked a couple of times with @mdavis about this, but I wanted to fill the ticket and have it documented somewhere.

[dbaston]

Thanks, Raul. Do you need to properly handle polygons that are invalid before the coordinate transformation, or only those that are made invalid by the transformation?

[Algunenano]

I need to handle also the ones that are invalid beforehand; this is both because invalid input is (currently) accepted and because we call lwgeom_simplify_in_place (to reduce the number of points) and lwgeom_affine (to transform to int), and both functions can return invalid polygons.

[mdavis]

Time for an update on this?

Last I think I heard was that OverlayNG works, but is still slower than wagyu. If that is the case, it's unlikely there will be a significant improvement any time soon. In which case perhaps waygu is still required.