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.