[geos-devel] [GEOS] #1035: VoronoiLines hangs indefinitely on multipoint

[GEOS]

#1035: VoronoiLines hangs indefinitely on multipoint
------------------------+--------------------------
 Reporter:  robe        |      Owner:  geos-devel@…
     Type:  defect      |     Status:  new
 Priority:  blocker     |  Milestone:  3.9.0
Component:  Default     |    Version:  master
 Severity:  Unassigned  |   Keywords:
------------------------+--------------------------
 I tested on 3.8.0 (still have to test on 3.8.1) but definitely an issue on
 GEOS head.


 {{{
 SELECT ST_VoronoiLines('MULTIPOINT(-10 40,5 40,20 40,35 40,50 40,-10 55,5
 55,20 55,35 55,50 55,-10 70,5 70,20 70,35 70,50 70)'::geometry, 20.1,
 'POINT(-11.1111111 40)'::geometry)
 }}}


 See related PostGIS ticket

 https://trac.osgeo.org/postgis/ticket/4726

 Raul's trace


 {{{
 #0  0x00007fc3eacf126c in geos::triangulate::quadedge::Vertex::isCCW
 (this=<optimized out>, b=..., c=...) at
 ../../../include/geos/triangulate/quadedge/Vertex.h:226
 #1  geos::triangulate::quadedge::Vertex::rightOf (this=0x55bba48b9720,
 e=...) at Vertex.cpp:83
 #2  0x00007fc3eace807c in
 geos::triangulate::IncrementalDelaunayTriangulator::insertSite
 (this=<optimized out>, v=...) at IncrementalDelaunayTriangulator.cpp:90
 #3  0x00007fc3eace7e4b in
 geos::triangulate::IncrementalDelaunayTriangulator::insertSites
 (this=0x7ffe3cf96408, vertices=...) at
 IncrementalDelaunayTriangulator.cpp:40
 #4  0x00007fc3eace9f5d in geos::triangulate::VoronoiDiagramBuilder::create
 (this=0x7ffe3cf964b8) at VoronoiDiagramBuilder.cpp:93
 #5  0x00007fc3eacea45b in
 geos::triangulate::VoronoiDiagramBuilder::getDiagramEdges
 (this=0x7ffe3cf964b8, geomFact=...) at VoronoiDiagramBuilder.cpp:122
 #6  0x00007fc3eba9c83e in GEOSVoronoiDiagram_r::$_188::operator()
 (this=<optimized out>) at geos_ts_c.cpp:3261
 #7  execute<GEOSVoronoiDiagram_r::$_188,
 (decltype(nullptr))0>(GEOSContextHandle_HS*,
 GEOSVoronoiDiagram_r::$_188&&) (extHandle=0x55bba48b88b0, f=...) at
 geos_ts_c.cpp:379
 #8  GEOSVoronoiDiagram_r (extHandle=0x55bba48b88b0, g1=0x55bba48b6840,
 env=0x55bba48e6f40, tolerance=20.100000000000001, onlyEdges=1) at
 geos_ts_c.cpp:3253
 #9  0x00007fc3ebc02ecb in lwgeom_voronoi_diagram (g=<optimized out>,
 env=0x7ffe3cf965c0, tolerance=20.100000000000001,
 output_edges=-1534355264) at lwgeom_geos.c:1926
 #10 0x00007fc3ebb3267e in ST_Voronoi (fcinfo=0x55bba48fbb20) at
 lwgeom_geos.c:3465
 #11 0x000055bba3c126e1 in ExecInterpExpr (state=<optimized out>,
 econtext=<optimized out>, isnull=0x7ffe3cf9675f) at execExprInterp.c:625
 #12 0x000055bba3c45874 in ExecEvalExprSwitchContext (state=0x55bba48fba48,
 econtext=0x55bba48fb770, isNull=0x7ffe3cf9675f) at
 ../../../src/include/executor/executor.h:307
 [...]

 (gdb) c
 Continuing.
 ^C
 Program received signal SIGINT, Interrupt.
 geos::triangulate::quadedge::Vertex::isCCW (this=<optimized out>, b=...,
 c=...) at ../../../include/geos/triangulate/quadedge/Vertex.h:227
 227                    > (b.p.y - p.y) * (c.p.x - p.x);
 (gdb) bt
 #0  geos::triangulate::quadedge::Vertex::isCCW (this=<optimized out>,
 b=..., c=...) at ../../../include/geos/triangulate/quadedge/Vertex.h:227
 #1  geos::triangulate::quadedge::Vertex::rightOf (this=0x55bba48b9ee0,
 e=...) at Vertex.cpp:83
 #2  0x00007fc3eace807c in
 geos::triangulate::IncrementalDelaunayTriangulator::insertSite
 (this=<optimized out>, v=...) at IncrementalDelaunayTriangulator.cpp:90
 #3  0x00007fc3eace7e4b in
 geos::triangulate::IncrementalDelaunayTriangulator::insertSites
 (this=0x7ffe3cf96408, vertices=...) at
 IncrementalDelaunayTriangulator.cpp:40
 #4  0x00007fc3eace9f5d in geos::triangulate::VoronoiDiagramBuilder::create
 (this=0x7ffe3cf964b8) at VoronoiDiagramBuilder.cpp:93
 #5  0x00007fc3eacea45b in
 geos::triangulate::VoronoiDiagramBuilder::getDiagramEdges
 (this=0x7ffe3cf964b8, geomFact=...) at VoronoiDiagramBuilder.cpp:122
 #6  0x00007fc3eba9c83e in GEOSVoronoiDiagram_r::$_188::operator()
 (this=<optimized out>) at geos_ts_c.cpp:3261
 #7  execute<GEOSVoronoiDiagram_r::$_188,
 (decltype(nullptr))0>(GEOSContextHandle_HS*,
 GEOSVoronoiDiagram_r::$_188&&) (extHandle=0x55bba48b88b0, f=...) at
 geos_ts_c.cpp:379
 #8  GEOSVoronoiDiagram_r (extHandle=0x55bba48b88b0, g1=0x55bba48b6840,
 env=0x55bba48e6f40, tolerance=20.100000000000001, onlyEdges=1) at
 geos_ts_c.cpp:3253
 #9  0x00007fc3ebc02ecb in lwgeom_voronoi_diagram (g=<optimized out>,
 env=0x7ffe3cf965c0, tolerance=20.100000000000001,
 output_edges=-1534355264) at lwgeom_geos.c:1926
 #10 0x00007fc3ebb3267e in ST_Voronoi (fcinfo=0x55bba48fbb20) at
 lwgeom_geos.c:3465
 [...]
 }}}

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