[geos-devel] [GEOS] #962: GEOSNode is much slower that GEOSUnaryUnion

GEOS geos-trac at osgeo.org
Mon Aug 26 17:33:00 PDT 2019

#962: GEOSNode is much slower that GEOSUnaryUnion
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |

Comment (by mdavis):

 The data in #982 is absolutely a worst-case scenario for CascadedUnion,
 since it has very little spatial coherence, and the number of nodes is on
 the order of O(n^2).  So it's not surprising it's very slow.

 Invoking CascadedUnion only on union exception would be a quick fix for
 this case.  But I have my doubts about using Cascaded Union at all for
 sets of lines.  I think it should be possible to determine how the
 Cascaded Union code is improving robustness (likely due to snapping) and
 simply invoke that directly.  Although, the snapping heuristic is possibly
 low-performance itself, and so it might not produce much advantage.

 Ultimately, better noding is going to be the solution.  Either snap-
 rounding, or perhaps with further research an approach that preserves more
 precision where possible.

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

More information about the geos-devel mailing list