Hello I am wondering if there is ongoing work around the notion of embeddings of the Boost Graph Library. In the CGAL project which deals with geometric data structures we have written specializations of the graph_traits for the polyhedral surface, the halfedge datastructure, 2D triangulations, and arrangements. This allows to run BGL algorithms directly on CGAL data structures. http://www.cgal.org/Pkg/BGL. 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_Halfe... 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. Would any of these ideas be interesting for the maintainers of the BGL. best regards, andreas -- Andreas Fabri, PhD Chief Officer, GeometryFactory Editor, The CGAL Project phone: +33.492.954.912 skype: andreas.fabri
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/halfedgediagr... 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
participants (3)
-
Anders Wallin -
Andreas Fabri -
Brian Budge