CGAL 5.6.1 - Surface Mesh Topology
CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh > Class Template Reference

#include <CGAL/Curves_on_surface_topology.h>

Definition

The class Curves_on_surface_topology provides methods to compute shortest non contractible cycles and to test homotopy on paths.

Each object of this class is constructed from an external mesh, either a 2D combinatorial map or a model of a FaceGraph. It maintains a correspondence between this mesh and an internal representation, computed the first time an homotopy test is called. The user must not modify the input surface as long as homotopy tests are performed with this Curves_on_surface_topology.

Template Parameters
Mesha model of CombinatorialMap or of FaceGraph
Examples:
Surface_mesh_topology/edgewidth_surface_mesh.cpp, Surface_mesh_topology/facewidth.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 descriptor to Dart for combinatorial/generalized maps, or a halfedge descriptor for models of the FaceGraph concept.
 

Public Member Functions

 Curves_on_surface_topology (const Mesh &amesh)
 creates a Curves_on_surface_topology object using amesh as input.
 
bool are_freely_homotopic (const Path_on_surface< Mesh > &p1, const Path_on_surface< Mesh > &p2) const
 returns true if the closed paths p1 and p2 are freely homotopic. More...
 
bool are_homotopic_with_fixed_endpoints (const Path_on_surface< Mesh > &p1, const Path_on_surface< Mesh > &p2) const
 returns true if the paths p1 and p2 are homotopic with fixed endpoints. More...
 
bool is_contractible (const Path_on_surface< Mesh > &p) const
 returns true if the closed path p is contractible. More...
 
bool is_homotopic_to_simple_cycle (const Path_on_surface< Mesh > &p) const
 returns true if the closed path p is homotopic to some simple cycle. More...
 
Path_on_surface< Mesh > compute_edge_width () const
 returns a non-contractible cycle of type Path_on_surface with minimal number of edges. More...
 
template<class WeightFunctor = Unit_weight_functor>
Path_on_surface< Mesh > compute_shortest_non_contractible_cycle (const WeightFunctor &wf=WeightFunctor()) const
 returns a non-contractible cycle of type Path_on_surface with minimal length, where the length of a cycle is the sum of the weights of its edges computed thanks to the WeightFunctor wf. More...
 
template<class WeightFunctor = Unit_weight_functor>
Path_on_surface< Mesh > compute_shortest_non_contractible_cycle_with_base_point (halfedge_descriptor d, const WeightFunctor &wf=WeightFunctor()) const
 returns a non-contractible cycle of type Path_on_surface with minimal length going through the source vertex of d, where the length of a cycle is the sum of the weights of its edges computed thanks to the WeightFunctor wf. More...
 
std::vector< halfedge_descriptorcompute_face_width () const
 returns a vector of darts representing a non-contractible curve with a minimal number of intersection with the graph of the mesh. More...
 
void set_verbose (bool is_verbose)
 set whether the function should output error message to std::cerr when the prerequisite of the argument(s) is not met. More...
 

Member Function Documentation

◆ are_freely_homotopic()

template<typename Mesh>
bool CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::are_freely_homotopic ( const Path_on_surface< Mesh > &  p1,
const Path_on_surface< Mesh > &  p2 
) const

returns true if the closed paths p1 and p2 are freely homotopic.

Precondition
p1 and p2 must be two paths on amesh.

◆ are_homotopic_with_fixed_endpoints()

template<typename Mesh>
bool CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::are_homotopic_with_fixed_endpoints ( const Path_on_surface< Mesh > &  p1,
const Path_on_surface< Mesh > &  p2 
) const

returns true if the paths p1 and p2 are homotopic with fixed endpoints.

The paths p1 and p2 must have the same endpoints but must not be closed. Equivalent to is_contractible(q) where q is the concatenation of p1 and the reverse of p2.

Precondition
p1 and p2 must be two paths on amesh.

◆ compute_edge_width()

template<typename Mesh>
Path_on_surface<Mesh> CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::compute_edge_width ( ) const

returns a non-contractible cycle of type Path_on_surface with minimal number of edges.

This number of edges is the edge width of the mesh.

◆ compute_face_width()

template<typename Mesh>
std::vector<halfedge_descriptor> CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::compute_face_width ( ) const

returns a vector of darts representing a non-contractible curve with a minimal number of intersection with the graph of the mesh.

This curve can be described by the alternating sequence of faces and vertices it goes through, so that each dart in the returned vector belongs to both a face and the next vertex in the alternating sequence. (Here, faces and vertices are viewed as subsets of darts.) The size of the returned vector is the face width of the mesh.

◆ compute_shortest_non_contractible_cycle()

template<typename Mesh>
template<class WeightFunctor = Unit_weight_functor>
Path_on_surface<Mesh> CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::compute_shortest_non_contractible_cycle ( const WeightFunctor wf = WeightFunctor()) const

returns a non-contractible cycle of type Path_on_surface with minimal length, where the length of a cycle is the sum of the weights of its edges computed thanks to the WeightFunctor wf.

By default, all the edge weights are set to 1 (thanks to the Unit_weight_functor functor).

◆ compute_shortest_non_contractible_cycle_with_base_point()

template<typename Mesh>
template<class WeightFunctor = Unit_weight_functor>
Path_on_surface<Mesh> CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::compute_shortest_non_contractible_cycle_with_base_point ( halfedge_descriptor  d,
const WeightFunctor wf = WeightFunctor() 
) const

returns a non-contractible cycle of type Path_on_surface with minimal length going through the source vertex of d, where the length of a cycle is the sum of the weights of its edges computed thanks to the WeightFunctor wf.

By default, all the edge weights are set to 1 (thanks to the Unit_weight_functor functor).

◆ is_contractible()

template<typename Mesh>
bool CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::is_contractible ( const Path_on_surface< Mesh > &  p) const

returns true if the closed path p is contractible.

Precondition
p must be a closed path on amesh.

◆ is_homotopic_to_simple_cycle()

template<typename Mesh>
bool CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::is_homotopic_to_simple_cycle ( const Path_on_surface< Mesh > &  p) const

returns true if the closed path p is homotopic to some simple cycle.

Precondition
p must be a closed path on amesh.

◆ set_verbose()

template<typename Mesh>
void CGAL::Surface_mesh_topology::Curves_on_surface_topology< Mesh >::set_verbose ( bool  is_verbose)

set whether the function should output error message to std::cerr when the prerequisite of the argument(s) is not met.

Affects are_freely_homotopic(p1, p2), are_homotopic_with_fixed_endpoints(p1, p2), is_contractible(p), and is_homotopic_to_simple_cycle(p)