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.