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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-04-10 17:42:06

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

As noticed Luke, there shouldn't be any overhead, especially in case when
the input set consists of points. The nice feature of the sweepline
algorithm is that coordinates of the Voronoi vertices are computed as part
of the geometric predicates used for output topology generation. You may
have a look at the benchmark page of the documentation
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_benchmark.htm.
Voronoi diagram of 100 000 points could be constructed in 0.27 seconds on
Linux-64 system with Intel i5-7600 processor (2.8 GHz).

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

Voronoi diagram implementation would be capable to deal with the first 3
items. Before going further I need to have a look on the interfaces
Boost.Graph requires.

Thanks,
Andrii