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
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.
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
On Thu, Mar 1, 2012 at 5:29 AM, Anders Wallin
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.
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 _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
This sounds interesting to me too. I've used openmesh in the past and it worked fairly well for me, but I'd like to see something in boost. Brian
participants (3)
-
Anders Wallin -
Andreas Fabri -
Brian Budge