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