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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-04-10 17:18:05

Andrii Sydorchuk wrote:
>> Although your email mentions Delaunay triangulation, the impression that I
>> get from the documentation (& code) is that you have not implemented this.
>
> 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).

Right.  I am aware of the dual nature, but was unsure if there was some 
overhead involved in using one to derive the other.  For example, I 
would guess that computing the coordinates of the vertices of the 
Voronoi diagram would be an overhead that is not needed for the 
Delaunay triangulation.  Or maybe not.

> In case you provide more details
> on the task you are trying to solve I could help with the code examples.

Well in case it is useful as a motivating example, my current 
requirement is to:

- Read in a large number of (x,y,attribute) from a file.
- Compute the Delaunay triangulation of the (x,y), keeping the edge graph.
- Discard some edges based on attributes of the vertices, i.e. equality 
or inequality.
- Partition the modified graph into connected subgraphs (Boost.Graph's connected_components).
- For each of those subgraphs, find a Hamiltonian or longest cycle or 
path (using BFS).
- Write the coordinates of the points on those cycles or paths to the 
output file.

Regards,  Phil.