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

[GEOS]

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

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