CGAL 4.12.1 - CGAL and the Boost Graph Library

Generic convenience functions for testing if an edge is a border edge, if a mesh is triangular, for conversion between models of different FaceGraph concepts, etc.

Most functions are in the header file <CGAL/boost/graph/helpers.h>

## Functions

template<typename FaceGraph >
bool CGAL::is_border (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true if the halfedge hd is on a border.

template<typename FaceGraph >
bool CGAL::is_border_edge (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true if the halfedge hd or the opposite halfedge is on a border.

template<typename FaceGraph >
bool CGAL::is_border (typename boost::graph_traits< FaceGraph >::edge_descriptor ed, const FaceGraph &g)
returns true if the edge e is on a border.

template<typename FaceGraph >
boost::optional< typename boost::graph_traits< FaceGraph >::halfedge_descriptor > CGAL::is_border (typename boost::graph_traits< FaceGraph >::vertex_descriptor vd, const FaceGraph &g)
returns a halfedge which is on a border and whose target vertex is vd, if such a halfedge exists.

template<typename FaceGraph >
bool CGAL::is_closed (const FaceGraph &g)
returns true if there are no border edges.

template<typename FaceGraph >
bool CGAL::is_bivalent (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true if the target of hd has exactly two incident edges.

template<typename FaceGraph >
bool CGAL::is_bivalent_mesh (const FaceGraph &g)
returns true if all vertices have exactly two incident edges.

template<typename FaceGraph >
bool CGAL::is_trivalent (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true if the target of hd has exactly three incident edges.

template<typename FaceGraph >
bool CGAL::is_trivalent_mesh (const FaceGraph &g)
returns true if all vertices have exactly three incident edges.

template<typename FaceGraph >
bool CGAL::is_isolated_triangle (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true iff the connected component denoted by hd is a triangle. More...

template<typename FaceGraph >
bool CGAL::is_triangle (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true iff the face denoted by hd is a triangle, that is it has three incident halfedges.

template<typename FaceGraph >
bool CGAL::is_triangle_mesh (const FaceGraph &g)
returns true if all faces are triangles.

template<typename FaceGraph >
bool CGAL::is_isolated_quad (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true iff the connected component denoted by hd is a quadrilateral.

template<typename FaceGraph >
bool CGAL::is_quad (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true iff the face denoted by hd is a quad, that is it has four incident halfedges.

template<typename FaceGraph >
returns true if all faces are quadrilaterals.

template<typename FaceGraph >
bool CGAL::is_tetrahedron (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true iff the connected component denoted by hd is a tetrahedron.

template<typename FaceGraph >
bool CGAL::is_hexahedron (typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph &g)
returns true iff the connected component denoted by hd is a hexahedron.

template<typename Graph , typename P >
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_triangle (const P &p0, const P &p1, const P &p2, Graph &g)
Creates an isolated triangle with its vertices initialized to p0, p1 and p2, and adds it to the graph g. More...

template<typename Graph , typename P >
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_quad (const P &p0, const P &p1, const P &p2, const P &p3, Graph &g)
Creates an isolated quad with its vertices initialized to p0, p1, p2, and p3, and adds it to the graph g. More...

template<typename Graph , typename P >
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_hexahedron (const P &p0, const P &p1, const P &p2, const P &p3, const P &p4, const P &p5, const P &p6, const P &p7, Graph &g)
Creates an isolated hexahedron with its vertices initialized to p0, p1, ... , and p7, and adds it to the graph g. More...

template<typename Graph , typename P >
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_tetrahedron (const P &p0, const P &p1, const P &p2, const P &p3, Graph &g)
Creates an isolated tetrahedron with its vertices initialized to p0, p1, p2, and p3, and adds it to the graph g. More...

template<class Graph , class P >
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_regular_prism (typename boost::graph_traits< Graph >::vertices_size_type nb_vertices, Graph &g, const P &base_center=P(0, 0, 0), typename CGAL::Kernel_traits< P >::Kernel::FT height=1.0, typename CGAL::Kernel_traits< P >::Kernel::FT radius=1.0, bool is_closed=true)
Creates a triangulated regular prism, outward oriented, having nb_vertices vertices in each of its bases and adds it to the graph g. More...

template<class Graph , class P >
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_pyramid (typename boost::graph_traits< Graph >::vertices_size_type nb_vertices, Graph &g, const P &base_center=P(0, 0, 0), typename CGAL::Kernel_traits< P >::Kernel::FT height=1.0, typename CGAL::Kernel_traits< P >::Kernel::FT radius=1.0, bool is_closed=true)
Creates a pyramid, outward oriented, having nb_vertices vertices in its base and adds it to the graph g. More...

template<class Graph , class P >
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_icosahedron (Graph &g, const P &center=P(0, 0, 0), typename CGAL::Kernel_traits< P >::Kernel::FT radius=1.0)
Creates an icosahedron, outward oriented, centered in center and adds it to the graph g. More...

template<class Graph , class CoordinateFunctor = CGAL::Creator_uniform_3< typename boost::graph_traits<Graph>::vertices_size_type, typename boost::property_traits<typename boost::property_map<Graph, vertex_point_t>::type>::value_type>>
boost::graph_traits< Graph >::halfedge_descriptor CGAL::make_grid (typename boost::graph_traits< Graph >::vertices_size_type i, typename boost::graph_traits< Graph >::vertices_size_type j, Graph &g, const CoordinateFunctor &calculator, bool triangulated=false)
Creates a row major ordered grid with i cells along the width and j cells along the height and adds it to the graph g. More...

template<typename FaceGraph >
void CGAL::clear (FaceGraph &g)
removes all vertices, faces and halfedges from a graph. More...

template<typename FaceGraph >
bool CGAL::is_empty (const FaceGraph &g)
checks whether the graph is empty, by checking that it does not contain any vertex. More...

template<typename SourceMesh , typename TargetMesh , typename V2V = Emptyset_iterator, typename H2H = Emptyset_iterator, typename F2F = Emptyset_iterator, typename Src_vpm = typename boost::property_map<SourceMesh, vertex_point_t>::const_type, typename Tgt_vpm = typename boost::property_map<TargetMesh, vertex_point_t>::type>
void CGAL::copy_face_graph (const SourceMesh &sm, TargetMesh &tm, V2V v2v=V2V(), H2H h2h=H2H(), F2F f2f=F2F(), Src_vpm sm_vpm=get(vertex_point, sm), Tgt_vpm tm_vpm=get(vertex_point, tm))
copies a source model of FaceListGraph into a target model of a FaceListGraph. More...

## ◆ clear()

template<typename FaceGraph >
 void CGAL::clear ( FaceGraph & g )

#include <CGAL/boost/graph/helpers.h>

removes all vertices, faces and halfedges from a graph.

Calls remove_edge(), remove_vertex(), and remove_face() for each edge, vertex or face.

If the graph has a member function clear(), it will be called instead.

Template Parameters
 FaceGraph model of MutableHalfedgeGraph and MutableFaceGraph
Parameters
 g the graph to clear

## ◆ copy_face_graph()

template<typename SourceMesh , typename TargetMesh , typename V2V = Emptyset_iterator, typename H2H = Emptyset_iterator, typename F2F = Emptyset_iterator, typename Src_vpm = typename boost::property_map<SourceMesh, vertex_point_t>::const_type, typename Tgt_vpm = typename boost::property_map<TargetMesh, vertex_point_t>::type>
 void CGAL::copy_face_graph ( const SourceMesh & sm, TargetMesh & tm, V2V v2v = V2V(), H2H h2h = H2H(), F2F f2f = F2F(), Src_vpm sm_vpm = get(vertex_point, sm), Tgt_vpm tm_vpm = get(vertex_point, tm) )

#include <CGAL/boost/graph/copy_face_graph.h>

copies a source model of FaceListGraph into a target model of a FaceListGraph.

OutputIterators can be provided to produce a mapping between source and target elements. The target graph is not cleared.

Template Parameters
 SourceMesh a model of FaceListGraph. The descriptor types boost::graph_traits::vertex_descriptor and boost::graph_traits::face_descriptor must be models of Hashable. TargetMesh a model of FaceListGraph V2V a model of OutputIterator accepting std::pair H2H a model of OutputIterator accepting std::pair F2F a model of OutputIterator accepting std::pair Src_vpm a model of ReadablePropertyMap with sm_vertex_descriptor as key Tgt_vpm a model of WritablePropertyMap with tm_vertex_descriptor as key where the prefix sm_ and tm_ mean belonging to the source and target mesh respectively.

The types sm_vertex_descriptor and sm_face_descriptor must be models of the concept Hashable.

Parameters
 sm the source mesh tm the target mesh v2v pairs of vertex_descriptors from sm and corresponding vertex_descriptors in tm are added to v2v h2h pairs of halfedge_descriptors from sm and corresponding halfedge_descriptors in tm are added to h2h f2f pairs of face_descriptors from sm and corresponding face_descriptors in tm are added to f2f sm_vpm vertex point map for sm tm_vpm vertex point map for tm

The points from sm to tm are converted using CGAL::Cartesian_converter<SourceKernel, TargetKernel>. SourceKernel and TargetKernel are deduced using CGAL::Kernel_traits from the value types of Src_vpm and Tgt_vpm.

Other properties are not copied.

Examples:
BGL_polyhedron_3/copy_polyhedron.cpp, BGL_surface_mesh/surface_mesh_partition.cpp, and Surface_mesh_segmentation/extract_segmentation_into_mesh_example.cpp.

## ◆ is_empty()

template<typename FaceGraph >
 bool CGAL::is_empty ( const FaceGraph & g )

#include <CGAL/boost/graph/helpers.h>

checks whether the graph is empty, by checking that it does not contain any vertex.

Template Parameters
 FaceGraph model of FaceGraph
Parameters
 g the graph to test

## ◆ is_isolated_triangle()

template<typename FaceGraph >
 bool CGAL::is_isolated_triangle ( typename boost::graph_traits< FaceGraph >::halfedge_descriptor hd, const FaceGraph & g )

#include <CGAL/boost/graph/helpers.h>

returns true iff the connected component denoted by hd is a triangle.

Precondition
g must be valid.

## ◆ make_grid()

template<class Graph , class CoordinateFunctor = CGAL::Creator_uniform_3< typename boost::graph_traits<Graph>::vertices_size_type, typename boost::property_traits<typename boost::property_map<Graph, vertex_point_t>::type>::value_type>>
 boost::graph_traits::halfedge_descriptor CGAL::make_grid ( typename boost::graph_traits< Graph >::vertices_size_type i, typename boost::graph_traits< Graph >::vertices_size_type j, Graph & g, const CoordinateFunctor & calculator, bool triangulated = false )

#include <CGAL/boost/graph/helpers.h>

Creates a row major ordered grid with i cells along the width and j cells along the height and adds it to the graph g.

Parameters
 i the number of cells along the width. j the number of cells along the height. g the graph in which the grid will be created. calculator the functor that will assign coordinates to the grid vertices. triangulated decides if a cell is composed of one quad or two triangles. If triangulated is true, the diagonal of each cell is oriented from (0,0) to (1,1) in the cell coordinates.
Template Parameters
 CoordinateFunctor that takes two boost::graph_traits::vertices_size_type and outputs a boost::property_traits::type>::value_type.

Default: a point with positive integer coordinates (w, h, 0), with w in [0..i] and h in [0..j]

Returns
the non-border non-diagonal halfedge that has the target vertex associated with the first point of the grid (default is (0,0,0) ).

## ◆ make_hexahedron()

template<typename Graph , typename P >
 boost::graph_traits::halfedge_descriptor CGAL::make_hexahedron ( const P & p0, const P & p1, const P & p2, const P & p3, const P & p4, const P & p5, const P & p6, const P & p7, Graph & g )

#include <CGAL/boost/graph/helpers.h>

Creates an isolated hexahedron with its vertices initialized to p0, p1, ... , and p7, and adds it to the graph g.

Returns
the halfedge that has the target vertex associated with p0, in the face with the vertices with the points p0, p1, p2, and p3.
Examples:
BGL_surface_mesh/gwdwg.cpp.

## ◆ make_icosahedron()

template<class Graph , class P >
 boost::graph_traits::halfedge_descriptor CGAL::make_icosahedron ( Graph & g, const P & center = P(0,0,0), typename CGAL::Kernel_traits< P >::Kernel::FT radius = 1.0 )

#include <CGAL/boost/graph/helpers.h>

Creates an icosahedron, outward oriented, centered in center and adds it to the graph g.

Parameters
 g the graph in which the icosahedron will be created. center the center of the sphere in which the icosahedron is inscribed. radius the radius of the sphere in which the icosahedron is inscribed.
Returns
the halfedge that has the target vertex associated with the first point in the first face.

## ◆ make_pyramid()

template<class Graph , class P >
 boost::graph_traits::halfedge_descriptor CGAL::make_pyramid ( typename boost::graph_traits< Graph >::vertices_size_type nb_vertices, Graph & g, const P & base_center = P(0,0,0), typename CGAL::Kernel_traits< P >::Kernel::FT height = 1.0, typename CGAL::Kernel_traits< P >::Kernel::FT radius = 1.0, bool is_closed = true )

#include <CGAL/boost/graph/helpers.h>

Creates a pyramid, outward oriented, having nb_vertices vertices in its base and adds it to the graph g.

If center is (0, 0, 0), then the first point of the base is (radius, 0, 0)

Parameters
 nb_vertices the number of vertices in the base. It must be greater than or equal to 3. g the graph in which the pyramid will be created base_center the center of the circle in which the base is inscribed. height the distance between the base and the apex. radius the radius of the circle in which the base is inscribed. is_closed determines if the base must be created or not. If is_closed is true, center is a vertex.
Returns
the halfedge that has the target vertex associated with the apex point in the first face.

template<typename Graph , typename P >
 boost::graph_traits::halfedge_descriptor CGAL::make_quad ( const P & p0, const P & p1, const P & p2, const P & p3, Graph & g )

#include <CGAL/boost/graph/helpers.h>

Creates an isolated quad with its vertices initialized to p0, p1, p2, and p3, and adds it to the graph g.

Returns
the non-border halfedge that has the target vertex associated with p0.
Examples:
BGL_surface_mesh/write_inp.cpp.

## ◆ make_regular_prism()

template<class Graph , class P >
 boost::graph_traits::halfedge_descriptor CGAL::make_regular_prism ( typename boost::graph_traits< Graph >::vertices_size_type nb_vertices, Graph & g, const P & base_center = P(0,0,0), typename CGAL::Kernel_traits< P >::Kernel::FT height = 1.0, typename CGAL::Kernel_traits< P >::Kernel::FT radius = 1.0, bool is_closed = true )

#include <CGAL/boost/graph/helpers.h>

Creates a triangulated regular prism, outward oriented, having nb_vertices vertices in each of its bases and adds it to the graph g.

If center is (0, 0, 0), then the first point of the prism is (radius, height, 0)

Parameters
 nb_vertices the number of vertices per base. It must be greater than or equal to 3. g the graph in which the regular prism will be created. base_center the center of the circle in which the lower base is inscribed. height the distance between the two bases. radius the radius of the circles in which the bases are inscribed. is_closed determines if the bases must be created or not. If is_closed is true, center is a vertex.
Returns
the halfedge that has the target vertex associated with the first point in the first face.

## ◆ make_tetrahedron()

template<typename Graph , typename P >
 boost::graph_traits::halfedge_descriptor CGAL::make_tetrahedron ( const P & p0, const P & p1, const P & p2, const P & p3, Graph & g )

#include <CGAL/boost/graph/helpers.h>

Creates an isolated tetrahedron with its vertices initialized to p0, p1, p2, and p3, and adds it to the graph g.

Returns
the halfedge that has the target vertex associated with p0, in the face with the vertices with the points p0, p1, and p2.

## ◆ make_triangle()

template<typename Graph , typename P >
 boost::graph_traits::halfedge_descriptor CGAL::make_triangle ( const P & p0, const P & p1, const P & p2, Graph & g )

#include <CGAL/boost/graph/helpers.h>

Creates an isolated triangle with its vertices initialized to p0, p1 and p2, and adds it to the graph g.

Returns
the non-border halfedge that has the target vertex associated with p0`.
Examples:
Property_map/dynamic_properties.cpp.