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-21 15:03:32

Simonson, Lucanus J wrote:
>>Andrii Sydorchuk wrote:
>>> Apart from topology information it's usually useful to be able to 
>>> associate some information with the primitive (vertex/edge/cell).
>>> At the moment this is implemented via mutable void pointer
>
> Phil Endecott wrote:
>>This void* "user data" thing is something that I commented on before.  
>>It struck me as a rather old-school "C" way of doing things.  
>>If this contribution had been subject to a full review as a new library 
>>I believe it would not have been accepted in this form.  
>>I see it as a weakness of the Boost process that this has "slipped 
>>through", i.e. we have different rules for additions to existing
>>libraries even when they are by different authors and have little or no dependency on the existing work.
>
> Nothing has slipped through.  It isn't on the release branch yet.  The reason 
> we are talking about it on the list is to get feedback for changes the community 
> would like to see made before it is released.

OK, good.  My comment was based on a previous post by Andrii where he 
said that you (Luke) had approved the contribution.

> Upon reflection it seems ridiculous to recompile a complex algorithm for no 
> good reason to make it composable with an unrelated pointer type.

The library is already header-only, so there is plenty of "ridiculous 
unnecessary recompilation" going on, as with very many other 
libraries.  The extra bit of recompilation occurs when there is more 
than one variant in the same compilation unit.  I suspect this will not 
be a common use case.  Anyway, despite the complexity of the algorithm 
I found it to compile quickly in practice; it is not a "compiler stress 
test" like some Boost things...

> I typically use an index instead of a void* pointer, but I don't really see 
> one as being much better than the other.

Boost.Graph's vertex (and edge?) descriptors seem to be essentially 
indexes that can be used to look up properties stored in e.g. vectors 
in O(1) time.

Indexes look more type-safe than casting a void*, but I think there is 
an equivalent risk of indexing into the wrong vector.  I think the main 
benefit of indexes is that they might not need to be stored at all, 
i.e. they are implicit; if your vertices are stored in a vector you can 
get the index from a pointer to the vertex by subtracting &vertices[0].

>>Having briefly experimented with Andrii's code, I have since them 
>> implemented an incremental constrained Delaunnay triangulation using 
>> Boost.Graph.  
>>This has some problems of its own, but it neatly solves the issue of 
>> per-vertex or per-edge user data via template parameters.
>
> I'd be interested in learning more about this.  Are you willing to 
> share the code or at least expand a little on your description?

I naively made Boost.Graph's vertices and edges correspond to vertices 
and edges of the Delaunay triangulation.  As a result, my code spends 
most of its time studying the relative directions of edges, e.g. given 
a vertex v and and edge e that is incident to v, find the two edges d 
and f that are incident to v and adjacent respectively clockwise and 
anticlockwise of e.  This could be improved by storing the edge 
incidence list ordered by direction.  Better, though, would be to use a 
half-edge data structure or similar where each node has explicit links 
to nodes representing adjacent edges in each direction from the same 
source node (as Andrii seems to have done).  Boost.Graph may not be the 
best starting point for either of these alternatives, though I see that 
some things related to planar graphs are on the Boost.Graph to-do list.

To build a Delaunay triangulation incrementally, it's important to be 
able to find the existing triangle (or edge) that contains the new 
point efficiently.  In my case the input data was sequences of points 
with good spacial locality, so I simply used the previously-added point 
as a hint for the new point and located the containing triangle in 
worst-case O(N).  In general, some sort of spacial index of the 
triangles is needed and adds considerably to the complexity.  Because 
of this, I think sweep-line or similar is better than incremental 
construction, unless there is some particular need for incremental.

At the top level, my code looks something like this:

// Default vertex type; user code could use a subclass of this to add
// per-vertex attributes.
struct Vertex {
   typedef int coord_t;
   typedef std::pair<coord_t,coord_t> point_t;
   point_t pos;
};

// Default edge type:
struct Edge {
   bool constrained;

   Edge(): constrained(false) {}
   Edge(bool constrained_): constrained(constrained_) {}
};

// A DelaunayTriangulation is-a Boost.Graph Mutable Graph; it's 
templated on
// vertex and edge types (see above), and adds methods for triangulation.
template <typename VERTEX_T = Vertex, typename EDGE_T = Edge>
class DelaunayTriangulation:
   public boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
                                VERTEX_T, EDGE_T>
{
public:
   vertex_descriptor add_vertex_near_vertex(vertex_t v,
                                            vertex_descriptor hint,
                                            edge_t e = edge_t());

   edge_descriptor add_constrained_edge(vertex_descriptor src,
                                        vertex_descriptor tgt,
                                        edge_t e = edge_t());

   // etc.
};

Then my "application" code then subclasses from that:

struct CGVertex:
   public Vertex
{
   typedef int alt_t;
   alt_t alt;
};

struct CGEdge:
   public Edge
{
   char type;
};

class ContourGraph:
   public DelaunayTriangulation<CGVertex,CGEdge>
{
   // etc.
};

(Note to Andrii: in another post, you object to inheritance because of 
the storage of a virtual function table pointer and the speed for 
virtual function indirection; note that here I'm using inheritance, but 
nothing is virtual; if there are no virtual functions, there is no 
virtual function table pointer or other overhead.)

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;

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.  Any comments?

Regards,  Phil.