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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-04-13 14:51:34

Hi Phil,

I've started to look at your code.  The good news it that it does seem to
> work!

That's definitely a good start :-)!

 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.

I completely agree. However one of the methods accepts both: container of
points and container of segments. Moving to iterators will change the
signature to 5 input arguments. I thought that this will add another layer
of UI complexity. What do you think?

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 am going to update documentation and code according to the recent changes
by the end of the day. Luke convinced me that library will benefit from
using concepts. Yes, that would mean that it won't be so independent as I
stated before. As I finish updates I'll make a separate post on this thread
with what was changes.

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.

BTW, Voronoi vertex also has this member. I agree that this adds some
memory overhead, but I don't think that it is significant.

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

So if you pass it as template parameter probably it would be different for
each of the primitives: edge/vertex/cell. That would require to add three
additional template parameters to the voronoi_diagram declaration, I think
that's too much. Library already supports user provided edge/vertex/cell
classes via voronoi_diagram_traits, thus users may drop data member if they
think it's too much memory overhead.

 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.

You are right. The main problem is that output Voronoi diagram could have
two type of cells: with point or with segment inside. I don't see an easy
way to resolve this while also keeping Voronoi_diagram and Voronoi_builder
data structures decoupled as they are now. One of the solutions I can
propose is storing index of the input object within the output topology.
What do you think about such approach?

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

This is a common technique used at the place I am currently working at: input
arguments are values or const references while output arguments are pointers.
And I actually like it, because it allows to strictly distinguish between
input/output arguments.

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?

I don't remember exactly why I used it this way. Will review it.

 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.

Thanks, I'll update documentation.

I am trying to get the edges of the Delaunay triangulation by iterating
> over the edges of the Voronoi diagram.

I will add this as a separate tutorial to the documentation (within a few
months there will be a dedicated Delaunay triangulation data structure).
One thing that I wanted to clarify: imagine you have four cocircular input
points, by default that would produce a rectangle for the triangulation not
two triangles. In case you require those to be triangles declare your
voronoi_diagram_traits as follows:

struct my_voronoi_diagram_traits {
  typedef double coordinate_type;
  typedef struct {
    template <typename CT>
    double operator()(const CT& that) const { return
static_cast<double>(that); }
  } ctype_converter_type;
  typedef detail::point_2d<coordinate_type> point_type;
  typedef voronoi_cell<coordinate_type> cell_type;
  typedef voronoi_vertex<coordinate_type> vertex_type;
  typedef voronoi_edge<coordinate_type> edge_type;
  typedef struct {
    bool operator()(const point_type &v1, const point_type &v2) const
{ return false; }
  } vertex_equality_predicate_type;
};
typedef voronoi_diagram<double, my_voronoi_diagram_traits>
my_voronoi_diagram;

As you might see this will change vertex equality predicate to always
return false. Thus no Voronoi vertices will be united.

 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?

const voronoi_edge<double> *e;
const voronoi_cell<dobule> *left_cell = e->cell();
const voronoi_cell<double> *right_cell = e->twin()->cell(); // switch to
the twin edge at first; after that you have direct access to the second
cell.

Thanks for your comments!
Andrii