[geos-devel] [GEOS] #973: Polygon clipping and validation over integer coordinates

[GEOS]

#973: Polygon clipping and validation over integer coordinates
-----------------------------+--------------------------
 Reporter:  Algunenano       |      Owner:  geos-devel@…
     Type:  enhancement      |     Status:  new
 Priority:  minor            |  Milestone:  GEOS Fund Me
Component:  Default          |    Version:  master
 Severity:  Feature Request  |   Keywords:
-----------------------------+--------------------------
 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.

-- 
Ticket URL: <https://trac.osgeo.org/geos/ticket/973>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).