[GEOS] #859: Voronoi issue

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

[GEOS] #859: Voronoi issue

geos-2
#859: Voronoi issue
------------------------+--------------------------
 Reporter:  jjgreen     |      Owner:  geos-devel@…
     Type:  defect      |     Status:  new
 Priority:  major       |  Milestone:  3.5.2
Component:  Default     |    Version:  3.5.1
 Severity:  Unassigned  |   Keywords:
------------------------+--------------------------
 OSGEO Voronoi issue

 Further to a posting on the PostGIS mailing list
 in February 2018, this directory contains scripts
 to generate data for the bug report for OSGEO.
 The scripts generating the data can only be used
 against a copy of the seadb DB which is not open
 source, but the `reproduce.sh` script can be used
 (with minimal modifications) to reproduce the issue
 with the CSV file output from the DB.

 For my setup, which is Ubuntu Xenial with PostGIS
 from apt-postgresql.org and

 - POSTGIS="2.3.3 r15473"
 - GEOS="3.5.0-CAPI-1.9.0 r4084"
 - PROJ="Rel. 4.9.2, 08 September 2015"
 - GDAL="GDAL 1.11.3, released 2015/09/16"
 - LIBXML="2.9.3"
 - LIBJSON="0.11.99" RASTER

 the `reproduce.sh` script reports

     CREATE TABLE
     COPY 1322
     CREATE INDEX
     ERROR:  GEOSVoronoiDiagram: TopologyException: Input
         geom 1 is invalid: Self-intersection at or near point
         444332.38647522771 8548816.0569835864 at
         444332.38647522771 8548816.0569835864

 As discussed in the PostGIS forum thread mentioned above, we
 find that `ST_SnapToGrid` with dyadic grid step fixes the
 issue.

 The original data for these points was the EuroROSE project,
 an EU-funded experiment on the feasibility of the use of
 HF-radar for measuring ocean waves, currents and so on. The
 experiment took place at Fedje, Norway in early 2000. More
 details can be found at

     http://wera.cen.uni-hamburg.de/EuroROSE/EuroROSE_Intro.shtml

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859>
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] #859: Voronoi issue

geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.5.2
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by jjgreen):

 * Attachment "fedje.csv" added.

 data points

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859>
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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.5.2
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by jjgreen):

 * Attachment "reproduce.sh" added.

 script which reproduces the issue

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859>
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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.7.0
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by robe):

 * milestone:  3.5.2 => 3.7.0


Comment:

 Still an issue even with 3.7.0beta1.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------
Changes (by robe):

 * milestone:  3.7.0 => 3.6.4


--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by komzpa):

 Hi, there was a gridded voronoi robustness fix in #976. Maybe this one is
 fixed on master too?

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 This problem does appear to be caused by input points which lie on a grid,
 so this is probably fixed by #976

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by pramsey):

 Not fixed, just tested on latest trunk.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by Paul Ramsey <pramsey@…>):

 In [changeset:"2036448ae9ef15ef026ff5b5bb6acbff119c75c3/git" 2036448/git]:
 {{{
 #!CommitTicketReference repository="git"
 revision="2036448ae9ef15ef026ff5b5bb6acbff119c75c3"
 Add trimmed down test case on Voronoi.
 Curiously, this case blows an exception on PostGIS, but not in the unit
 test.
 References #859
 }}}

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Replying to [comment:6 Paul Ramsey <pramsey@…>]:

 > Curiously, this case blows an exception on PostGIS, but not in the unit
 test.

 The reason the unit test passes is that the triangulation tolerance value
 (100) is larger than the extent of the input geometry.  This causes the
 data to collapse to a point, which produces an empty Voronoi diagram.  If
 a smaller tolerance (say 0.1) is used then the test fails with a Topo
 exception.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Using DD precision for circumcentre actually fixes this issue.  But the
 [https://github.com/libgeos/geos/blob/master/src/triangulate/quadedge/QuadEdgeSubdivision.cpp#L398
 isocelese triangle heuristic] for performance doesn't work. This is why
 the unit test fails when it is fixed to use an appropriate tolerance.

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 Verified that the original data on this issue is fixed by using
 circumcentreDD (with no heuristic).

 Note that #976 is testing a subset of this data, which also fails:
 {{{
 0104000080170000000101000080EC51B81E11A20741EC51B81E85A51C415C8FC2F528DC354001010000801F85EB5114A207415C8FC2F585A51C417B14AE47E1BA3540010100008085EB51B818A20741A8C64B3786A51C413E0AD7A3709D35400101000080000000001BA20741FED478E984A51C413E0AD7A3709D3540010100008085EB51B818A20741FED478E984A51C413E0AD7A3709D354001010000800AD7A37016A20741FED478E984A51C413E0AD7A3709D35400101000080000000001BA2074154E3A59B83A51C413E0AD7A3709D3540010100008085EB51B818A2074154E3A59B83A51C413E0AD7A3709D354001010000800AD7A37016A2074154E3A59B83A51C413E0AD7A3709D35400101000080000000001BA20741AAF1D24D82A51C413E0AD7A3709D3540010100008085EB51B818A20741AAF1D24D82A51C413E0AD7A3709D35400101000080F6285C8F12A20741EC51B81E88A51C414160E5D022DB354001010000802222222210A2074152B81EC586A51C414160E5D022DB354001010000804F1BE8B40DA2074152B81EC586A51C414160E5D022DB354001010000807B14AE470BA2074152B81EC586A51C414160E5D022DB354001010000802222222210A20741B81E856B85A51C414160E5D022DB354001010000804F1BE8B40DA20741B81E856B85A51C414160E5D022DB354001010000807B14AE470BA20741B81E856B85A51C414160E5D022DB35400101000080A70D74DA08A20741B81E856B85A51C414160E5D022DB35400101000080D4063A6D06A20741B81E856B85A51C414160E5D022DB354001010000807B14AE470BA207411F85EB1184A51C414160E5D022DB35400101000080A70D74DA08A207411F85EB1184A51C414160E5D022DB35400101000080D4063A6D06A207411F85EB1184A51C414160E5D022DB3540
 }}}

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by strk):

 Time to re-test this against master or 3.8 branches (see
 https://trac.osgeo.org/geos/ticket/976#comment:25)

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#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
Reply | Threaded
Open this post in threaded view
|

Re: [GEOS] #859: Voronoi issue

geos-2
In reply to this post by geos-2
#859: Voronoi issue
------------------------+---------------------------
 Reporter:  jjgreen     |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:  3.6.4
Component:  Default     |     Version:  3.5.1
 Severity:  Unassigned  |  Resolution:
 Keywords:              |
------------------------+---------------------------

Comment (by mdavis):

 I did run this against master as a C++ unit test (but didn't commit it
 because data is so large).  I can commit it if that seems like a good idea
 (there is a unit test which is a subset of this data though).

 Or, have been thinking about adding ability to run Delaunay and Voronoi as
 XML tests (should be fairly easy).

--
Ticket URL: <https://trac.osgeo.org/geos/ticket/859#comment:11>
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