Boost logo

Boost :

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:

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 {
   void *data() const { return data_; }
   void data(void *d) const { data_ = d; }

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

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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at