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