#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

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

Definition

Public Types

Public Member Functions

Member Function Documentation

◆ are_freely_homotopic()

◆ are_homotopic_with_fixed_endpoints()

◆ compute_edge_width()

◆ compute_face_width()

◆ compute_shortest_non_contractible_cycle()

◆ compute_shortest_non_contractible_cycle_with_base_point()

◆ is_contractible()

◆ is_homotopic_to_simple_cycle()

◆ set_verbose()