Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at