CGAL 5.5.4 - Surface Mesh Topology
CGAL::Surface_mesh_topology::Path_on_surface< Mesh > Class Template Reference

#include <CGAL/Path_on_surface.h>

Definition

The class Path_on_surface represents a walk in a mesh which is either a model of CombinatorialMap, a model of GeneralizedMap or a model of a FaceGraph.

Each object of this class is constructed from an external mesh on which the path should lie. A path is represented as a sequence of darts or halfedges, each one representing an oriented edge in the path. The class Path_on_surface behaves as a container for this sequence of darts/halfedges. Elements are added in the path one at a time to the path thanks to the push_back() method.

Template Parameters
Mesha model of CombinatorialMap, GeneralizedMap or of FaceGraph
Examples:
Surface_mesh_topology/edgewidth_surface_mesh.cpp, Surface_mesh_topology/open_path_homotopy.cpp, Surface_mesh_topology/path_homotopy_double_torus.cpp, Surface_mesh_topology/path_homotopy_with_symbols.cpp, Surface_mesh_topology/path_homotopy_with_symbols_2.cpp, Surface_mesh_topology/path_simplicity_double_torus.cpp, Surface_mesh_topology/path_simplicity_double_torus_2.cpp, and Surface_mesh_topology/shortest_noncontractible_cycle.cpp.

Public Types

typedef unspecified_type halfedge_descriptor
 A handle to Dart for combinatorial/generalized maps, or a halfedge descriptor for models of the FaceGraph concept.
 

Public Member Functions

 Path_on_surface (const Mesh &amesh)
 creates an empty path object which lies on amesh.
 
bool is_empty () const
 returns true iff this path is empty
 
bool is_closed () const
 returns true iff this path is closed.
 
bool is_simple () const
 returns true iff this path does not pass twice through a same edge or a same vertex.
 
std::size_t length () const
 returns the length of the path, i.e. its number of edges.
 
halfedge_descriptor operator[] (std::size_t i) const
 returns the ith dart of the path. More...
 
void clear ()
 clears this path.
 
bool can_be_pushed (halfedge_descriptor hd, bool flip=false) const
 returns true iff hd can be added at the end of this path. If flip is true, the direction of hd is reversed before checking
 
void push_back (halfedge_descriptor hd, bool flip=false)
 adds hd at the end of this path. More...
 
bool can_be_pushed_by_index (std::size_t i) const
 returns true iff the dart/halfedge with index i can be added at the end of this path. More...
 
void push_back_by_index (std::size_t i)
 adds the dart/halfedge with index i at the end of this path. More...
 
void push_back_by_index (std::initializer_list< std::size_t > l)
 adds successively all dart/halfedges in l (a sequence of indices), at the end of the path. More...
 
void extend_positive_turn (std::size_t nb)
 adds the dart/halfedge obtained by turning nb times around the target vertex of the last dart/halfedge in this path, in the positive circular order. More...
 
void extend_negative_turn (std::size_t nb)
 adds the dart/halfedge obtained by turning nb times around the target vertex of the last dart/halfedge in this path, in the negative circular order. More...
 
bool can_be_pushed_by_label (const std::string &l) const
 returns true iff the dart/halfedge with label l can be added at the end of this path. More...
 
void push_back_by_label (const std::string &s)
 adds successively all darts/halfedges in s (a sequence of labels separated by spaces) at the end of this path. More...
 
Self & operator+= (const Self &other)
 concatenates other to this path. More...
 
void reverse ()
 reverses this path (i.e. negates its orientation).
 
void generate_random_path (std::size_t length, Random &random=get_default_random())
 creates a random open path with length darts/halfedges.
 
void generate_random_closed_path (std::size_t length, Random &random=get_default_random())
 creates a random closed path with at least length darts/halfedges.
 

Member Function Documentation

◆ can_be_pushed_by_index()

template<typename Mesh>
bool CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::can_be_pushed_by_index ( std::size_t  i) const

returns true iff the dart/halfedge with index i can be added at the end of this path.

If Mesh is a Polyhedron_3, takes time proportional to the number of darts/halfedges.

◆ can_be_pushed_by_label()

template<typename Mesh>
bool CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::can_be_pushed_by_label ( const std::string &  l) const

returns true iff the dart/halfedge with label l can be added at the end of this path.

Precondition
Mesh must be a model of PolygonalSchema concept.

◆ extend_negative_turn()

template<typename Mesh>
void CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::extend_negative_turn ( std::size_t  nb)

adds the dart/halfedge obtained by turning nb times around the target vertex of the last dart/halfedge in this path, in the negative circular order.

To extend with a negative 1 turn thus amounts to extend with the composite pointer: opposite(prev(opposite())).

Precondition
!is_empty()

◆ extend_positive_turn()

template<typename Mesh>
void CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::extend_positive_turn ( std::size_t  nb)

adds the dart/halfedge obtained by turning nb times around the target vertex of the last dart/halfedge in this path, in the positive circular order.

To extend with a positive 1 turn thus amounts to extend with the next() pointer. (A zero turn corresponds to the opposite() pointer.)

Precondition
!is_empty()

◆ operator+=()

template<typename Mesh>
Self& CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::operator+= ( const Self &  other)

concatenates other to this path.

Precondition
the last vertex of this path should coincide with the first vertex of other.

◆ operator[]()

template<typename Mesh>
halfedge_descriptor CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::operator[] ( std::size_t  i) const

returns the ith dart of the path.

Precondition
i<length().

◆ push_back()

template<typename Mesh>
void CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::push_back ( halfedge_descriptor  hd,
bool  flip = false 
)

adds hd at the end of this path.

If flip is true, the opposite of hd is considered.

Precondition
can_be_pushed(hd)

◆ push_back_by_index() [1/2]

template<typename Mesh>
void CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::push_back_by_index ( std::size_t  i)

adds the dart/halfedge with index i at the end of this path.

If Mesh is a Polyhedron_3, takes time proportional to the number of halfedges.

Precondition
can_be_pushed_by_index(i)

◆ push_back_by_index() [2/2]

template<typename Mesh>
void CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::push_back_by_index ( std::initializer_list< std::size_t >  l)

adds successively all dart/halfedges in l (a sequence of indices), at the end of the path.

If Mesh is a Polyhedron_3, takes time proportional to the number of halfedges. For each index i, can_be_pushed_by_index(i) should be true.

◆ push_back_by_label()

template<typename Mesh>
void CGAL::Surface_mesh_topology::Path_on_surface< Mesh >::push_back_by_label ( const std::string &  s)

adds successively all darts/halfedges in s (a sequence of labels separated by spaces) at the end of this path.

For each label, l, can_be_pushed_by_label(l) should be true.

Precondition
Mesh must be a model of PolygonalSchema concept.