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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-04-13 14:25:16

From: boost-bounces_at_[hidden] [mailto:boost-bounces_at_[hidden]] On Behalf Of Phil Endecott

>I've started to look at your code.  The good news it that it does seem to work!  Some observations:
>   template <typename PC, typename VD>
>   static inline void construct_voronoi(const PC &points, VD *output,  .....
>   {
>     default_voronoi_builder builder;
>     builder.insert(points.begin(), points.end());
>     ......
>It would be more conventional to pass begin and end iterators in your public interface, rather than a reference to the container.  This allows the caller to e.g. pass part of a container, or >pass raw pointers, or pass complex iterators like filtering iterators etc.  I.e.
>   template <typename POINT_ITER, typename VD>
>   static inline void construct_voronoi(POINT_ITER begin, POINT_ITER end, VD *output,  .....
>   {
>     default_voronoi_builder builder;
>     builder.insert(begin, end);
>     ......
>This is more verbose for the caller, but we are normally prepared to pay that cost (or to use a Range).

Eventually we would like to have a directed_line_segment_set_concept and point_set_concept for which any standard container that supplies forward iterator semantics would be a model.  These would just call the iterator pair form of the function by using the begin()/end() traits of the concept instead of member function.  We would also supply a concept cast so that you could call:

construct_voronoi(view_as<point_set_concept>(my_polygon_set));

to override the semantic of polygon set to use its edges as line segments and instead use just the vertices as a point set.

>You said before that the code has no dependency on the rest of 
>Boost.Polygon, but I now see that you are including e.g. isotrophy.hpp 
>and point_concept.hpp.  These include other things like mpl.  My guess 
>is that I'm looking at code that is changing under my feet!  Is there a 
>"stable" version that I can use?  I'd like to look at something that is 
>at least consistent with the documentation.

Yes, the code is changing under your feet, prompted actually by your initial feedback.  You can always use time stamped checkout of sandbox svn from the date Andrii posted his review request to work with a stable version that matches the documentation.

I see that your voronoi_cell and voronoi_edge classes have:

>class voronoi_cell/edge {
>public:
>   void *data() const { return data_; }
>   void data(void *d) const { data_ = d; }
>
>private:
>   mutable void *data_;
>};
>This probably isn't the best way to include user-data, because it is 
>not type-safe and it has overhead when no data is needed.  Can't you 
>either pass the type of the user data as a template parameter, or allow 
>the user to supply their own cell and edge (sub-)classes?  (Perhaps 
>someone else can suggest a good example of how to do this.)

>Although you have this user-data in the voronoi_cell/edge classes, I 
>don't see any way to have additional attributes in my input data copied 
>to, or referenced from, the output.  I.e. if my input points have a 
>"name", I'd like that to be accessible in the corresponding 
>voronoi_cell.  I am imagining a design where the voronoi_cell contains 
>a copy of the input point-sequence iterator, or a reference to the 
>input point.

I have a similar problem for exposing the generalize line segment intersection algorithm.  Internally my algorithm represents association to input line segments by an index.  I don't expose that in any documented interface, however.  It is tricky to associate intersected line segments with original line segments because of rounding.  The output segments will not be collinear with the input segments.  As long as there is a way to make the association then it can be the user's problem to propagate properties to the output.

In the case of voronoi diagram, the output sites are identical to the input sites, so the association from input to output site can be made easily by hash or log n lookup.  Once could always copy the output voronoi diagram to their own data structure that is augmented with whatever data that they want based on association with the input sites.  I think that just eliminating this void* data feature and providing an example of copying the diagram into a different graph data structure and looking up input sites in a map to populate some field would be the best way to handle this.  I don't know that we currently have code that uses this feature of the cell/edge, do we Andrii? 

>I am trying to get the edges of the Delaunay triangulation by iterating 
>over the edges of the Voronoi diagram.  But I can only see how to get 
>one of the neighbouring cells for each edge, and I need both in order 
>to create a Delaunay edge.  Is there some way to do this?

I think building the Delaunay triangulation of a set of points from the voronoi diagram data structure should be provided as example code in the documentation in addition to being a documented API that populates a collection of polygon_concept with triangles.  That way people can adapt the example code to populate their own mesh data structure if a container of polygon_concept doesn't map well to what they need.  We can make the example code use concrete types for ease of reading and implement the API as a generic algorithm with concept overloading on polygon_concept that would be confusing if shown in example code.

Regards,
Luke