[geos-devel] [GEOS] #997: ST_Union performance degradation from GEOS 3.6.x -> 3.7.x

[GEOS]

#997: ST_Union performance degradation from GEOS 3.6.x -> 3.7.x
-------------------------+---------------------------
 Reporter:  greenlaw     |       Owner:  geos-devel@…
     Type:  defect       |      Status:  new
 Priority:  major        |   Milestone:
Component:  Default      |     Version:  3.7.0
 Severity:  Significant  |  Resolution:
 Keywords:  union        |
-------------------------+---------------------------

Comment (by mdavis):

 I think the problem here is caused by a union operation encountering a
 noding robustness error (TopologyException), on some pair of input
 geometries.  GEOS attempts to handle the error by invoking the heuristic
 line snapping code.  This is very slow for geoms with large numbers of
 points.

 The line snapping code has not changed for several versions.  But there
 have been some changes to low-level code for computing intersections.
 This is likely producing a slightly different result, perhaps in the
 buffer operation (ironically, the buffers may actually be more accurate
 now, but because of that the linework of two geoms is more nearly
 coincident - which is the classic cause of noding errors).

 More thought is required to come up with an internal GEOS solution for
 this.  Some options are:

 * Instead of the snapping heuristic use the buffer(0) hack (which in this
 case also invokes some rounding to handle the noding issue, so does round
 all output vertices somewhat)
 * It might be possible to a priori decide if snapping will take "too long"
 and only then use buffer(0)
 * The new overlay code in the works does not use snapping (however, it
 also requires some rounding)

 Given that buffers are only an approximation, another workaround might be
 to limit the precision of the computed buffers.  This can be done now in
 PostGIS by inserting a ST_SnapToGrid call after the buffer (although there
 is a risk of introducing invalidity here - it would be better if ST_Buffer
 allowed specifying a precision parameter, since internally it can
 guarantee valid output).

 JTS has the same problem (actually more obvious, since the slow snapping
 occurs when unioning the two lower-right geometries from the set that Paul
 posted)

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