
Boost : 
Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 20120523 13:51:49
On Wed, May 23, 2012 at 3:11 PM, Phil Endecott <
spam_from_boost_dev_at_[hidden]> wrote:
> 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 inplace, adding edges to
> an existing graph.
>
For the Voronoi diagram output Voronoi cells (not Voronoi vertices) contain
information about input vertices/segments.
> 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 reordered in place.
> // Alternatively, use more memory and sort a sequence of
> pointers.
> ...... // Run the sweepline 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))**;
>
One important detail that you forgot here is duplicates elimination. Apart
from that I don't see how this is going to be generalized for segment
inputs.
I am going back to mention my previous idea to expose indices of input
sites within the voronoi_builder interface.
This will allow the user to implement the following data structure:
template<UserPointType>
struct inplace_delaunay_triangulation {
// Should be the same container that was used during construction.
inplace_delaunay_triangulation(const INPUT_RANDOM_ACCESS_CONTAINER
&input) : input_containers_(input);
template <typename SEvent>
std::pair<void*, void*> insert_new_edge (const SEvent &site1, const SEvent
&site2) {
int ind1 = site1.index();
int ind2 = site2.index();
// operate with data within input data set.
}
private:
const INPUT_RANDOM_ACCESS_CONTAINER& input_container_;
}
This approach doesn't require any hashmaps or smth. like this. The library
could provide version of inplace containers for inputs that consist only of
points.
Regards, Andrii
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk