Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-04-10 14:15:30

Phil wrote:
>> Although your email mentions Delaunay triangulation, the impression that I
>> get from the documentation (& code) is that you have not implemented this.

Andrii wrote:
> Voronoi diagram data structure is dual to the Delaunay graph. That means you can retrieve all 
> the Delaunay graph information from the Voronoi graph, even do traversal. As this would be weird 
> for many users we are also planning to implement dedicated Delaunay triangulation data structure
> (this is the first item in the priority list). In case you provide more details on the task you are trying to
> solve I could help with the code examples.

While this is true for Delaunay triangulation of points, it isn't so simple for Delaunay triangulation of polygons.  The constrained Delaunay triangulation of polygons is something I'm not sure how to solve using the voronoi diagram of points or segments, though it may be trivial, I just haven't thought it through or looked it up.  The Delaunay triangulation of polygons where you are allowed to insert vertices on the polygon boundaries can be solved through iterative voronoi diagram of the polygon vertices and introducing a vertex on any polygon edges that intersect a delauney edge until you converge on a triangulation with no such intersections.  This formulation can be easily solved by combining voronoi diagram with generalized line segment intersection, both of which are provided by Polygon, though the interface for line segment intersection is only exposed in the trunk version of Polygon because I haven't gotten around to releasing it yet.  Line segment concepts was the GSOC2011 project, which I implemented myself after the student failed to do so.  I was hoping to release it at the same time as voronoi diagram because they need to be used together to satisfy the precondition of the voronoi diagram algorithm.

Thanks,
Luke