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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-05-22 15:24:02

Andrii Sydorchuk wrote:
> On Mon, May 21, 2012 at 9:03 PM, Phil Endecott wrote:
>> I can now refer to edges and vertices using Boost.Graph's
>> vertex_descriptor and edge_descriptor, and lookup the CGVertex and CGEdge
>> objects using operator[]:
>>
>> ContourGraph g;
>> ContourGraph::vertex_descriptor v = g.add_vertex_near_vertex(....);
>> g[v].alt = 42;
>>
>
> I would look closer at this approach to investigate memory/performance
> overheads of such a design.
> Anyway providing Boost.Graph interface for Voronoi diagram data structure
> is something that could be added within the future releases.

It would be an interesting test of the Boost.Graph concepts to see if 
they fit a half-edge or dart or similar planar graph representation.  
Maybe some Boost.Graph experts could comment on this.

>> Anyway, back to the subject of what Andrii's code should ideally look
>> like: I think there is at least one other issue, namely the
>> voronoi_diagram_builder class (not to be confused with voronoi_diagram or
>> voronoi_builder!), which seems superfluous to me.  I would have the
>> voronoi_builder call methods of the voronoi_diagram directly.  Having to
>> mimic this in my Delaunay class just added extra typing.
>
> If everybody else agrees that this is superfluous than I am going to remove
> it. However my arguments on such a design are following:
> 1) it splits construction and functionality of an object;
> 2) it hides construction methods from the user;
> 3) it represents implementation of the classical builder pattern (
> http://en.wikipedia.org/wiki/Builder_pattern):
> voronoi_builder (director), voronoi_diagram_builder (concrete builder),
> voronoi_diagram (product).

It seems to me that what you've got here is an input data structure, an 
output data structure, and an algorithm.  In your current code the 
algorithm is spread around in methods of the input and output data 
structures.  I would prefer it to be a separate thing outside either of them.

If I were you, I'd have:

- An input data structure based on your current voronoi_builder with 
just its insert*() methods.
- An output data structure, which could maybe be Boost.Graph-based but 
for now could be a simplified version of your voronoi_diagram class.
- Then put all of the beach line algorithmic stuff in an algorithm that 
reads the input and creates the output.

I.e. rather than:

voronoi_builder vb;
vb.insert(......);
voronoi_diagram vd;
vb.construct(&vd);

instead:

voronoi_input i;
i.insert(.......);
voronoi_output o;
make_voronoi_diagram(i,o);

This really does hide implementation details from the user much more completely.

(One advantage of your current arrangement is that it has a split at 
the right place to get both the Voronoi diagram and the Delaunay 
triangulation by changing the back-end.  This needs to be preserved, 
but it doesn't justify the current structure.)

Let me say again that your code is great in many important ways 
including performance and correctness.  The restructuring that I'm 
suggesting shouldn't affect the essence of the hard parts of the code 
at all; it's just a matter of moving things around.

I encourage others to try out this code.  I don't like being the only 
person to comment on it!

Regards,  Phil.