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.