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-05-23 09:11:54

Simonson, Lucanus J wrote:
> Carrying properties of the input through to the output is 
> something we have thought about, but we haven't come up with 
> a generic solution.  It is a separate concern from the void* 
> member of the output data structure.

Yes, I have confused myself a bit because I've been thinking primarily 
about the Delaunay triangulation.  In the Voronoi diagram, the output 
vertices are new entities.  In the case of the Delaunay triangulation, 
the input vertices ARE the output vertices and only the edges are new.  
So the triangulation algorithm can in principle operate in-place, 
adding edges to an existing graph.

To make that a bit more concrete, the Delaunay algorithm could be:

template <typename IN_VERTEX_ITER_T, typename OUT_EDGE_ITER_T>
// IN_VERTEX_ITER_T is a random access iterator to a sequence of points that
// model the Boost.Polygon point concept.
// OUT_EDGE_ITER_T is an output iterator to a sequence of edges, which 
could be
// pairs of IN_VERTEX_ITER_Ts.
void make_inplace_delaunay_triangulation(IN_VERTEX_ITER_T begin, 
IN_VERTEX_ITER_T end,
                                          OUT_EDGE_ITER_T out)
{
   std::sort(begin,end,pred);  // The input is re-ordered in place.
                   // Alternatively, use more memory and sort a sequence 
of pointers.
   ......  // Run the sweep-line algorithm, and append edges to out.
}

// Usage:
std::vector< std::pair<int,int> > vertices_t;
vertices_t vertices = .....;
typedef std::pair<vertices_t::const_iterator> edge_t;
std::vector<edge_t> edges;
make_delaunay_triangulation(vertices.begin(),vertices.end(),back_insert_iterator(edges));

Regards,  Phil.