Opened 8 years ago

Closed 16 months ago

#769 closed defect (fixed)

Robustness failure in GEOSVoronoiDiagram

Reported by: dbaston Owned by: geos-devel@…
Priority: major Milestone: Upstream
Component: Default Version: 3.5.0
Severity: Unassigned Keywords:
Cc:

Description

The following geometry (a 7-point MultiPoint) causes GEOSVoronoiDiagram to fail, even with a very large tolerance value relative to the scale of the input points (such as 0.1).

01040000000700000001010000000f8b33e3d97742c038c453588d0423c00101000
0001171d6d1b45d42c06adc1693e78c22c001010000001c8b33e3d97742c062c453
588d0423c00101000000afa5c71fda7742c04b93c61d8e0423c00101000000b0cdd
cb4b57942c026476887d7b122c00101000000e0678421dc7642c0f7736021e1fb22
c00101000000e32fd565018d42c0c7ea1222167c22c0

Originally reported in PostGIS at https://trac.osgeo.org/postgis/ticket/3447

Reported to JTS at https://github.com/dr-jts/jts/issues/20

Change History (8)

comment:1 by strk, 7 years ago

Milestone: 3.5.13.5.2

Ticket retargeted after milestone closed

comment:2 by robe, 6 years ago

Milestone: 3.5.23.5.3

comment:3 by komzpa, 5 years ago

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

comment:4 by mdavis, 5 years ago

This is due to an issue in the underlying Delaunay triangulation computation, caused by some very close sites. This isn't fixed by the recent Voronoi bug fix, which was a fix for the circumcentre calculation in the Voronoi code.

The upstream JTS issue is: https://github.com/locationtech/jts/issues/20

comment:5 by komzpa, 5 years ago

Confirmed on 3.7.1+postgis:

12:16:10 [gis] > select postgis_full_version();     
POSTGIS="3.0.0alpha3 r17573" [EXTENSION] PGSQL="120" GEOS="3.7.1-CAPI-1.11.1 27a5e771" SFCGAL="1.3.6" PROJ="Rel. 5.2.0, September 15th, 2018" GDAL="GDAL 2.4.0, released 2018/12/14" LIBXML="2.9.4" LIBJSON="0.12.1" LIBPROTOBUF="1.3.1" WAGYU="0.4.3 (Internal)" RASTER
(1 row)

Time: 1,639 ms
12:16:11 [gis] > select ST_VoronoiPolygons('01040000000700000001010000000f8b33e3d97742c038c453588d0423c001010000001171d6d1b45d42c06adc1693e78c22c001010000001c8b33e3d97742c062c453588d0423c00101000000afa5c71fda7742c04b93c61d8e0423c00101000000b0cddcb4b57942c026476887d7b122c00101000000e0678421dc7642c0f7736021e1fb22c00101000000e32fd565018d42c0c7ea1222167c22c0');
ERROR:  XX000: GEOSVoronoiDiagram: IllegalArgumentException: Points of LinearRing do not form a closed linestring
CONTEXT:  SQL function "st_voronoipolygons" statement 1
LOCATION:  pg_error, lwgeom_pg.c:243
Time: 1,081 ms

comment:6 by pramsey, 5 years ago

Milestone: 3.5.33.9.0

This is unlikely to be fixed in 3.5, but there are a number of voronoi tickets against master and this could be better kept there.

comment:7 by pramsey, 3 years ago

Milestone: 3.9.0Upstream

comment:8 by dbaston, 16 months ago

Resolution: fixed
Status: newclosed

Not sure when this was fixed, but I added a test confirming the fix at 6a5588c912d0f897db4dcd1de7f5b163ccefa3dd/git.

Note: See TracTickets for help on using tickets.