Opened 4 years ago

Last modified 20 months ago

#859 new defect

Voronoi issue

Reported by: jjgreen Owned by: geos-devel@…
Priority: major Milestone: 3.6.6
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 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 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 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

Attachments (2)

fedje.csv (73.6 KB ) - added by jjgreen 4 years ago.
data points (514 bytes ) - added by jjgreen 4 years ago.
script which reproduces the issue

Download all attachments as: .zip

Change History (14)

by jjgreen, 4 years ago

Attachment: fedje.csv added

data points

by jjgreen, 4 years ago

Attachment: added

script which reproduces the issue

comment:1 by robe, 4 years ago


Still an issue even with 3.7.0beta1.

comment:2 by robe, 4 years ago


comment:3 by komzpa, 3 years ago

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

comment:4 by mdavis, 3 years ago

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

comment:5 by pramsey, 3 years ago

Not fixed, just tested on latest trunk.

comment:6 by Paul Ramsey <pramsey@…>, 3 years ago

In 2036448/git:

Add trimmed down test case on Voronoi.
Curiously, this case blows an exception on PostGIS, but not in the unit test.
References #859

in reply to:  6 comment:7 by mdavis, 22 months ago

Replying to 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.

comment:8 by mdavis, 22 months ago

Using DD precision for circumcentre actually fixes this issue. But the isocelese triangle heuristic for performance doesn't work. This is why the unit test fails when it is fixed to use an appropriate tolerance.

comment:9 by mdavis, 22 months ago

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:


comment:10 by strk, 21 months ago

Time to re-test this against master or 3.8 branches (see

comment:11 by mdavis, 21 months ago

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).

comment:12 by strk, 20 months ago


Ticket retargeted after milestone closed

Note: See TracTickets for help on using tickets.