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

Mesh	a 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.