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

[GEOS]

#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):

 Here's what I think is going on.  `GEOSNode` uses the GEOS
 [https://github.com/libgeos/geos/blob/master/src/noding/GeometryNoder.cpp
 GeometryNoder], which in turn uses
 [https://github.com/libgeos/geos/blob/master/src/noding/IteratedNoder.cpp
 IteratedNoder].  `IteratedNoder` uses `MCIndexNoder`, which is actually
 O(NlogN)-ish.  But the function of `IteratedNoder` is to attempt to fully
 node lines by repeatedly re-noding until no new nodes are created.  There
 are situations involving almost-parallel lines where repeated noding keeps
 adding nodes, but also perturbing the resultant line segments so that they
 still cross.  So this will obviously be very slow.

 OTOH the GEOS `UnaryUnion` uses the overlay snapping heuristic if it
 detects noding failure.  That's probably succeeding here, and so the
 computation is faster.

 However, in the case DB mentions the UnaryUnion is perhaps hitting the
 recent correctness heuristic that was introduced to prevent some other
 failures.  It seems to be quite slow in some cases.  Probably the dataset
 does not cause too much (perhaps none) repeated noding in GEOSNode, so
 that is faster.

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