[geos-devel] [GEOS] #976: Voronoi polygons robustness issue

GEOS geos-trac at osgeo.org
Mon Jul 15 11:08:53 PDT 2019

#976: Voronoi polygons robustness issue
 Reporter:  komzpa      |       Owner:  geos-devel@…
     Type:  defect      |      Status:  new
 Priority:  major       |   Milestone:
Component:  Default     |     Version:  3.6.2
 Severity:  Unassigned  |  Resolution:
 Keywords:              |

Comment (by mdavis):

 This is due to a couple of the generated Voronoi polygons being
 topologically invalid, and because of that failing during the intersection
 computation (when clipping the raw Voronoi polygons to a surrounding

 The reason the polygons are invalid is that they contain two points which
 are almost identical, one of which happens to lie on another edge of the
 polygon, thus creating a self-intersection.

 The reason the very close points are present is because the input points
 (Voronoi sites) generating them lie on a regular grid pattern.  This
 produces two Delaunay triangles with *almost* identical circumcentres.
 They are not 100% identical because of round-off error. The DT
 circumcentres form the vertices of the Voronoi polygons, and so polygons
 are created with almost-but-not-identical points in them.

 See attached diagrams for images.

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

More information about the geos-devel mailing list