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 17:34:19
From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]] On Behalf Of Phil Endecott
>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.
Looks like it would make a smashing good tutorial and help us figure out the glue needed to get VD data structure to work with Boost.Graph.
The overhead for computing the voronoi vertices should be minimal, particularly for voronoi of points, which is numerically easier than that of line segments. This should be a straightforward application of the library.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk