[GEOS] #1035: VoronoiLines hangs indefinitely on multipoint

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

[GEOS] #1035: VoronoiLines hangs indefinitely on multipoint

geos-2
#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).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines hangs indefinitely on multipoint

geos-2
#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  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Description changed by robe:

Old description:

> 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
> [...]
> }}}
New description:

 I tested on 3.8.0 and works fine there (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#comment:1>
GEOS <http://trac.osgeo.org/geos>
GEOS (Geometry Engine - Open Source) is a C++ port of the Java Topology Suite (JTS).

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint (was: VoronoiLines hangs indefinitely on multipoint)

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Description changed by robe:

Old description:

> I tested on 3.8.0 and works fine there (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
> [...]
> }}}
New description:

 I tested on 3.8.0 and works fine there (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
 [...]
 }}}

 Same with VoronoiPolygons


 {{{
 SELECT ST_VoronoiPolygons('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)
 }}}

--

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 See also #976 and #859.

 This case works fine in JTS.
 It seems that the fix that worked in JTS (computing triangle
 circumcentres) does not work in GEOS?

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 That's a pretty massive tolerance value compared to the scale of the
 input.  It's possible that has something to do with the infinite loop.  If
 so, still need to figure out a way to disallow it, at least.

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 This case also creates an infinite loop when evaluating a Delaunay
 Triangulation.

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 A slightly smaller reproducer is:
 {{{
 MULTIPOINT ((-10 40), (5 40), (20 40), (-10 55), (5 55), (20 55), (-10
 70), (5 70), (20 70))
 }}}

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 After bisecting it appears (not surprisingly) that the cause of this bug
 is the commit:

 https://github.com/libgeos/geos/commit/8b433f0887633e320053e169e5bf71c5bbaecb1f

 Not sure why, however.  I suspect that there's an issue in the
 `QuadEdgeSubdivision::remove` method, since that is only called when there
 is a non-zero tolerance being used.

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Found the fix for this.  See https://github.com/libgeos/geos/pull/342

 The problem is caused by two bugs in the `QuadEdgeSubdivision::remove`
 method:

 * Since the method argument can be an edge in either base or sym
 orientation, the code to remove the corresponding `QuadEdgeQuartet` needs
 to check if the quartet base matches the arg edge OR its sym
 * The lambda capture clause must specify the edge parameter as `e`, not
 `&e`, since it is already a reference

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons 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  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Fixed by [changeset:"1198e06ef656ffdce71d1a3bc6e65cd146056677/git"
 1198e06/git]

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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint

geos-2
In reply to this post by geos-2
#1035: VoronoiLines and VoronoiPolygons hangs indefinitely on multipoint
------------------------+-----------------------
 Reporter:  robe        |       Owner:  mdavis
     Type:  defect      |      Status:  assigned
 Priority:  blocker     |   Milestone:  3.9.0
Component:  Default     |     Version:  master
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+-----------------------
Changes (by mdavis):

 * status:  new => assigned
 * owner:  geos-devel@… => mdavis


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

_______________________________________________
geos-devel mailing list
[hidden email]
https://lists.osgeo.org/mailman/listinfo/geos-devel