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-04-13 12:44:31

Hi Andrii,

Andrii Sydorchuk wrote:
> It has been two years since I started development of the Voronoi library as
> part of the Google Summer of Code 2010.
> Finally I feel that the library is ready to become public and would like to
> request a review for the inclusion into the Boost.Polygon library.

> The code is already merged with the Boost.Polygon sandbox branch. All the
> Voronoi related files are prefixed with "voronoi".
>
> - Code location: http://svn.boost.org/svn/boost/sandbox/gtl

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).

Or, maybe you intend that we should use voronoi_builder directly if we 
want to do this.

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.

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.

In voronoi_builder::construct, I don't see why output is a pointer and 
not a reference.

In a few places you have code like:

     if (!beach_line_.empty())
       beach_line_.clear();

The test is clearly redundant; have you done this as the result of benchmarking?

The documentation for voronoi_diagram doesn't say what the template 
parameter T is.  I guessed that it was the same as for the 
voronoi_builder, but I realised (after lots of cryptic errors) that it 
is the coordinate type for the output, which needs to be double.

Typedefs like voronoi_diagram<T>::edge_type are not documented.

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?

Regards,  Phil.