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-05-23 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 in-place, 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 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))**;
>

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