Re: [Boost-users] embedding

Subject: Re: [Boost-users] embedding
From: Anders Wallin (anders.e.e.wallin_at_[hidden])
Date: 2012-03-01 08:29:20

> As these graphs are  always embedded, that is as there
> is a circular order of edges we introduced a HalfedgeGraph
> concept
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/BGL_ref/Concept_HalfedgeGraph.html#Cross_link_anchor_1952
> where one has global functions in order to walk along
> the border of a face, and go from an outgoing
> edge via the opposite incoming edge to a neighbor
> face.

FWIW I would certainly use a light-weight, header-only, generic
half-edge data structure which would provide vertices, edges, faces,
as well as the appropriate iterators etc.
I've hacked together something myself over here:
https://github.com/aewallin/openvoronoi/blob/master/src/common/halfedgediagram.hpp
however that code is not in the style of boost-libraries, and makes
some assumptions on the template parameters TEdgeProperties and
TFaceProperties (these could/should be concept-checked I guess).

I'm always adding Faces to the graph and never deleting Faces, so I
haven't provided a function for deleting Faces. The face-container is
hard-coded to std::vector (and thus face_descriptor is unsigned int).

In addition to CGAL there's also GTS (http://gts.sourceforge.net/) and
OpenMesh (http://www.openmesh.org/) which provide similar
functionality. All of these seem to be under slightly different not
necessarily compatible licenses!

Anders