#include <CGAL/Triangulation_on_sphere_2.h>

Inherits from

CGAL::Triangulation_cw_ccw_2.

Inherited by CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >.

Definition

The class Triangulation_on_sphere_2 is the basic class designed to represent a triangulation of a point set on a sphere: its vertices coincide with the points of the set.

Warning: This triangulation supports neither the insertion nor the removal of vertices, see CGAL::Delaunay_triangulation_on_sphere_2 for such purposes.

This triangulation class is very similar to CGAL::Triangulation_2 as both classes represent triangulations of a 2-manifold domain without boundary. A significant difference is that in the case of Euclidean 2D triangulation, it is necessary to introduce so-called infinite faces to complete the convex hull into an actual 2-manifold without boundary that the triangulation data structure can represent. This is not necessary for triangulations on the sphere, which are already perfectly adapted to the triangulation data structure.

There is an exception to the previous statement: in the degenerate configuration where all points lie on the same hemisphere, the triangulation has a border. Internally, the triangulation data structure must however remain a 2-manifold at all time, and to ensure this property, fictitious faces called ghost faces are added. We call faces that are not ghost faces solid faces, and edges of such faces solid edges.

Template Parameters

Traits is the geometric traits; it must be a model of the concept TriangulationOnSphereTraits_2.

TDS is the triangulation data structure; it must be a model of the concept TriangulationDataStructure_2, whose vertex base must be a model of TriangulationOnSphereVertexBase_2 and whose face base must be a model of TriangulationOnSphereFaceBase_2. By default, the triangulation data structure is instantiated by Triangulation_data_structure_2<Triangulation_on_sphere_vertex_base_2<Gt>, Triangulation_on_sphere_face_base_2<Gt> >.

See also: CGAL::Delaunay_triangulation_on_sphere_2<Traits, TDS>

Types
typedef Traits	Geom_traits
	The traits class.

typedef TDS	Triangulation_data_structure
	The triangulation data structure type.

typedef Triangulation_data_structure::size_type	size_type
	Size type (an unsigned integral type).

typedef Traits::FT	FT
	The number type.

typedef Traits::Point_on_sphere_2	Point
	The point type representing a point on the sphere.

typedef Traits::Point_3	Point_3
	The 3D point type.

typedef Traits::Segment_3	Segment_3
	The 3D segment type.

typedef Traits::Triangle_3	Triangle_3
	The 3D triangle type.

typedef Traits::Arc_on_sphere_2	Arc_on_sphere_2
	An arc of a great circle, used to represent a curved segment (Voronoi or Delaunay edge).

typedef TDS::Vertex	Vertex
	The vertex type.

typedef TDS::Edge	Edge
	The edge type.

typedef TDS::Face	Face
	The face type.

Handles, Iterators, and Circulators
The vertices and faces of the triangulation are accessed through handles, iterators and circulators. The handles are models of the concept `Handle` which basically offers the two dereference operators `*` and `->`. The handles are also model of the concepts `LessThanComparable` and `Hashable`, that is they can be used as keys in containers such as `std::map` and `std::unordered_map`. The iterators and circulators are all bidirectional and non-mutable. The circulators and iterators are convertible to handles with the same value type, so that whenever a handle appear in the parameter list of a function, an appropriate iterator or circulator can be passed as well. The edges of the triangulation can also be visited through iterators and circulators, the edge circulators and iterators are also bidirectional and non mutable.
typedef TDS::Vertex_handle	Vertex_handle
	Handle to a vertex.

typedef TDS::Face_handle	Face_handle
	Handle to a face.

typedef TDS::Vertex_iterator	Vertices_iterator
	Iterator over all vertices.

typedef Iterator_range< unspecified_type >	Vertex_handles
	Range type for iterating over all vertices, with a nested type `iterator` that has as value type `Vertex_handle`.

typedef TDS::Edge_iterator	All_edges_iterator
	Iterator over all edges.

typedef Iterator_range< All_edges_iterator >	All_edges
	Range type for iterating over all edges (including non-solid ones).

typedef TDS::Face_iterator	All_faces_iterator
	Iterator over all faces.

typedef Iterator_range< All_faces_iterator >	All_face_handles
	Range type for iterating over all faces (including ghost faces), with a nested type `iterator` that has as value type `Face_handle`.

typedef unspecified_type	Solid_edges_iterator
	Iterator over all solid edges.

typedef Iterator_range< Solid_edges_iterator >	Solid_edges
	Range type for iterating over all solid edges.

typedef unspecified_type	Solid_faces_iterator
	Iterator over all solid faces.

typedef Iterator_range< unspecified_type >	Solid_face_handles
	Range type for iterating over solid faces, with a nested type `iterator` that has as value type `Face_handle`.

typedef unspecified_type	Vertex_circulator
	Circulator over all vertices incident to a given vertex.

typedef unspecified_type	Edge_circulator
	Circulator over all edges incident to a given vertex.

typedef unspecified_type	Face_circulator
	Circulator over all faces incident to a given vertex.

typedef unspecified_type	Point_iterator
	Iterator over the points corresponding the vertices of the triangulation.

typedef Iterator_range< Point_iterator >	Points
	Range type for iterating over the points of the finite vertices.

Creation
	Triangulation_on_sphere_2 (const Traits &gt=Traits())
	constructs an empty triangulation. More...

	Triangulation_on_sphere_2 (const Point_3 &c, const FT r)
	constructs an empty triangulation and sets the center and radius to `c` and `r` respectively.

	Triangulation_on_sphere_2 (const Triangulation_on_sphere_2 &tr)
	Copy constructor. More...

Triangulation_on_sphere_2 &	operator= (Triangulation_on_sphere_2< Traits, TDS > tr)
	Assignment operator. More...

void	swap (Triangulation_on_sphere_2 &tr)
	The triangulations `tr` and `*this` are swapped.

void	clear ()
	deletes all faces and vertices, resulting in an empty triangulation.

Ghost Predicates
bool	is_ghost (const Face_handle f) const
	returns `true` if `f` is a ghost face, and `false` otherwise. More...

bool	is_ghost (const Edge &e) const
	returns `true` if `e` is a ghost edge, that is if both its incident faces are ghost faces, and `false` otherwise. More...

Modifying the domain
The following functions can be used to modify the geometry of the spherical domain. Warning The triangulation is cleared in the process.
void	set_center (const Point_3 &c)

void	set_radius (const FT radius)

void	set_center_and_radius (const Point_3 &c, const FT radius)

Access Functions
int	dimension () const
	returns: More...

const Geom_traits &	geom_traits () const
	returns a const reference to the triangulation traits object.

const Triangulation_data_structure &	tds () const
	returns a const reference to the triangulation data structure.

size_type	number_of_vertices () const
	returns the number of vertices.

size_type	number_of_faces () const
	returns the number of faces. More...

size_type	number_of_ghost_faces () const
	returns the number of ghost faces.

size_type	number_of_solid_faces () const
	returns the number of solid faces.

Geometric Access Functions
const Point &	point (const Vertex_handle v)
	returns the geometric position of the vertex `v`.

const Point &	point (const Face_handle f, const int i)
	returns the geometric position of the `i`-th vertex of the face `f`.

Segment_3	segment (const Edge &e) const
	returns the 3D line segment formed by the vertices of the edge `e`. More...

Segment_3	segment (const Face_handle f, int i) const
	returns the 3D line segment formed by the vertices of the edge `(f, i)`. More...

Arc_on_sphere_2	segment_on_sphere (const Edge &e) const
	returns the great circle arc formed by the vertices of the edge `e`. More...

Arc_on_sphere_2	segment_on_sphere (const Face_handle f, int i) const
	returns the great circle arc formed by the vertices of the edge `(f, i)`. More...

Triangle_3	triangle (const Face_handle f) const
	returns the 3D triangle formed by the three vertices of the face `f`. More...

All Face, Edge and Vertex Iterators
The following iterators allow respectively to visit all faces, edges and vertices of the triangulation. These iterators are non mutable, bidirectional and their value types are respectively `Face`, `Edge` and `Vertex`. They are all invalidated by any change in the triangulation.
Vertices_iterator	vertices_begin () const
	Starts at an arbitrary vertex.

Vertices_iterator	vertices_end () const
	Past-the-end iterator.

Vertex_handles	vertex_handles () const
	returns a range of iterators over all vertices. More...

All_edges_iterator	all_edges_begin () const
	Starts at an arbitrary edge.

All_edges_iterator	all_edges_end () const
	Past-the-end iterator.

All_edges	all_edges () const
	returns a range of iterators over all edges.

All_faces_iterator	all_faces_begin () const
	Starts at an arbitrary face.

All_faces_iterator	all_faces_end () const
	Past-the-end iterator.

All_face_handles	all_face_handles () const
	returns a range of iterators over all faces. More...

Solid_faces_iterator	solid_faces_begin () const
	Starts at an arbitrary face.

Solid_faces_iterator	solid_faces_end () const
	Past-the-end iterator.

Solid_face_handles	solid_face_handles () const
	returns a range of iterators over all solid faces. More...

Solid_edges_iterator	solid_edges_begin () const
	Starts at an arbitrary face.

Solid_edges_iterator	solid_edges_end () const
	Past-the-end iterator.

Solid_edges	solid_edges () const
	returns a range of iterators over all solid edges.

Points	points () const
	returns a range of iterators over all the points of the triangulations.

Face, Edge and Vertex Circulators
The triangulation also provides circulators that allows to visit respectively all faces or edges incident to a given vertex or all vertices adjacent to a given vertex. These circulators are non-mutable and bidirectional. The `operator++` moves the circulator counterclockwise around the vertex while the `operator-` moves clockwise. A face circulator is invalidated by any modification of the face pointed to. An edge or a vertex circulator are invalidated by any modification of one of the two faces incident to the edge pointed to.
Vertex_circulator	adjacent_vertices (Vertex_handle v) const
	Starts at an arbitrary vertex adjacent to the vertex `v`.

Vertex_circulator	adjacent_vertices (Vertex_handle v, Face_handle f)
	Starts at the first vertex of `f` adjacent to `v` in counterclockwise order around `v`. More...

Edge_circulator	incident_edges (Vertex_handle v) const
	Starts at an arbitrary edge incident to the vertex `v`.

Edge_circulator	incident_edges (Vertex_handle v, Face_handle f) const
	Starts at the first edge of `f` incident to `v`, in counterclockwise order around `v`. More...

Face_circulator	incident_faces (Vertex_handle v) const
	Starts at an arbitrary face incident to the vertex `v`. More...

Face_circulator	incident_faces (Vertex_handle v, Face_handle f) const
	Starts at face `f`. More...

Combinatorial Predicates
The class `Triangulation_on_sphere_2` provides methods to test the presence of a particular feature (edge or face) in the triangulation.
bool	is_edge (Vertex_handle va, Vertex_handle vb)
	returns `true` if there exists an edge (ghost or solid) having `va` and `vb` as vertices.

bool	is_edge (Vertex_handle va, Vertex_handle vb, Face_handle &fr, int &i)
	returns `true` if there exists an edge (ghost or solid) having `va` and `vb` as vertices. More...

bool	is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3)
	returns `true` if there exists a face (ghost or solid) having `v1`, `v2` and `v3` as vertices.

bool	is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3, Face_handle &fr)
	returns `true` if there exists a face (ghost or solid) having `v1`, `v2` and `v3` as vertices. More...

Queries
The class `Triangulation_on_sphere_2` provides methods to locate a given point with respect to a triangulation. It also provides methods to locate a point with respect to a given face of the triangulation.
enum	Locate_type { VERTEX =0, EDGE, FACE, OUTSIDE_CONVEX_HULL, OUTSIDE_AFFINE_HULL, NOT_ON_SPHERE, TOO_CLOSE }
	specifies which case occurs when locating a query point in the triangulation. More...

Face_handle	locate (const Point &query, Face_handle f=Face_handle()) const
	locates the point `query` in the triangulation, and returns information on this location. More...

Face_handle	locate (const Point &query, Locate_type &lt, int &li, Face_handle h=Face_handle()) const
	Same as above. More...

Miscellaneous
bool	is_valid (bool verbose=false, int level=0) const
	tests the validity of the triangulation as a `Triangulation_on_sphere_2`. More...

Additional Inherited Members
Public Member Functions inherited from CGAL::Triangulation_cw_ccw_2
	Triangulation_cw_ccw_2 ()

int	ccw (const int i) const

int	cw (const int i) const

Member Enumeration Documentation

◆ Locate_type

template<typename Traits , typename TDS >

enum CGAL::Triangulation_on_sphere_2::Locate_type

specifies which case occurs when locating a query point in the triangulation.

Enumerator
VERTEX	when the point coincides with a vertex of the triangulation
EDGE	when the point is in the relative interior of an edge
FACE	when the point is in the interior of a face
OUTSIDE_CONVEX_HULL	when the point is on the same 3D plane as the existing vertices, but not on an existing edge
OUTSIDE_AFFINE_HULL	when the insertion of the point would increase the dimension of the triangulation.
NOT_ON_SPHERE	when the point is not on the sphere
TOO_CLOSE	when the point is too close to a vertex of the triangulation (see `TriangulationOnSphereTraits_2` for more details)

Constructor & Destructor Documentation

◆ Triangulation_on_sphere_2() [1/2]

template<typename Traits , typename TDS >

CGAL::Triangulation_on_sphere_2< Traits, TDS >::Triangulation_on_sphere_2 ( const Traits & gt = Traits() )

constructs an empty triangulation.

Note: The values for the center and radius must be either already set in the traits (if gt is passed) or must be set after the construction, using the function set_center_and_radius().

◆ Triangulation_on_sphere_2() [2/2]

template<typename Traits , typename TDS >

CGAL::Triangulation_on_sphere_2< Traits, TDS >::Triangulation_on_sphere_2 ( const Triangulation_on_sphere_2< Traits, TDS > & tr )

Copy constructor.

All the vertices and faces are duplicated. After the copy, *this and tr refer to different triangulations: if tr is modified, *this is not.

Member Function Documentation

◆ adjacent_vertices()

template<typename Traits , typename TDS >

Vertex_circulator CGAL::Triangulation_on_sphere_2< Traits, TDS >::adjacent_vertices	(	Vertex_handle	v,
		Face_handle	f
	)

Starts at the first vertex of f adjacent to v in counterclockwise order around v.

Precondition: The face f is incident to the vertex v.

◆ all_face_handles()

template<typename Traits , typename TDS >

All_face_handles CGAL::Triangulation_on_sphere_2< Traits, TDS >::all_face_handles ( ) const

returns a range of iterators over all faces.

Note: While the value type of All_faces_iterator is Face, the value type of All_face_handles::iterator is Face_handle.

◆ dimension()

template<typename Traits , typename TDS >

int CGAL::Triangulation_on_sphere_2< Traits, TDS >::dimension ( ) const

returns:

-2 if the triangulation is empty
-1 if the triangulation contains a single vertex
0 if the triangulation contains exactly two vertices
1 if the triangulation contains three (or more) coplanar vertices
2 if the triangulation contains at least four non-coplanar vertices

Note that a triangulation of dimension 1 is just a polygon drawn on a circle. The polygon is not triangulated itself. Thus the triangulation of dimension one consists of one polygon and has no faces.

◆ incident_edges()

template<typename Traits , typename TDS >

Edge_circulator CGAL::Triangulation_on_sphere_2< Traits, TDS >::incident_edges	(	Vertex_handle	v,
		Face_handle	f
	)		const

Starts at the first edge of f incident to v, in counterclockwise order around v.

Precondition: The face f is incident to the vertex v.

◆ incident_faces() [1/2]

template<typename Traits , typename TDS >

Face_circulator CGAL::Triangulation_on_sphere_2< Traits, TDS >::incident_faces ( Vertex_handle v ) const

Starts at an arbitrary face incident to the vertex v.

Note that this may contain ghost faces.

◆ incident_faces() [2/2]

template<typename Traits , typename TDS >

Face_circulator CGAL::Triangulation_on_sphere_2< Traits, TDS >::incident_faces	(	Vertex_handle	v,
		Face_handle	f
	)		const

Starts at face f.

Precondition: The face f is incident to the vertex v.

◆ is_edge()

template<typename Traits , typename TDS >

bool CGAL::Triangulation_on_sphere_2< Traits, TDS >::is_edge	(	Vertex_handle	va,
		Vertex_handle	vb,
		Face_handle &	fr,
		int &	i
	)

returns true if there exists an edge (ghost or solid) having va and vb as vertices.

If true is returned, the edge with vertices va and vb is the edge e=(fr,i) where fr is a handle to the face incident to e and on the right side of e oriented from va to vb.

◆ is_face()

template<typename Traits , typename TDS >

bool CGAL::Triangulation_on_sphere_2< Traits, TDS >::is_face	(	Vertex_handle	v1,
		Vertex_handle	v2,
		Vertex_handle	v3,
		Face_handle &	fr
	)

returns true if there exists a face (ghost or solid) having v1, v2 and v3 as vertices.

If true is returned, fr is a handle to the face with v1, v2 and v3 as vertices.

◆ is_ghost() [1/2]

template<typename Traits , typename TDS >

bool CGAL::Triangulation_on_sphere_2< Traits, TDS >::is_ghost ( const Face_handle f ) const

returns true if f is a ghost face, and false otherwise.

Precondition: dimension() == 2

◆ is_ghost() [2/2]

template<typename Traits , typename TDS >

bool CGAL::Triangulation_on_sphere_2< Traits, TDS >::is_ghost ( const Edge & e ) const

returns true if e is a ghost edge, that is if both its incident faces are ghost faces, and false otherwise.

Precondition: dimension() == 2

◆ is_valid()

template<typename Traits , typename TDS >

bool CGAL::Triangulation_on_sphere_2< Traits, TDS >::is_valid	(	bool	verbose = `false`,
		int	level = `0`
	)		const

tests the validity of the triangulation as a Triangulation_on_sphere_2.

This function tests the validity of the underlying data structure (using the function TriangulationDataStructure_2::is_valid()), and the validity of the triangulation itself (consistency between the dimension and the number of simplices, face orientation checks, etc.).

This method is mainly useful for debugging Delaunay triangulation algorithms.

◆ locate() [1/2]

template<typename Traits , typename TDS >

Face_handle CGAL::Triangulation_on_sphere_2< Traits, TDS >::locate	(	const Point &	query,
		Face_handle	f = `Face_handle()`
	)		const

locates the point query in the triangulation, and returns information on this location.

If the point is (according to the traits) not on the sphere or is too close to an existing vertex, or if the dimension of the triangulation is not 2, or if the point is outside the affine hull, then the returned Face_handle is nullptr.

Otherwise, a face intersected by the ray spawned from the center of the sphere and passing through the point is returned.

The optional Face_handle argument, if provided, is used as a hint of where the locate process should start its search.

◆ locate() [2/2]

template<typename Traits , typename TDS >

Face_handle CGAL::Triangulation_on_sphere_2< Traits, TDS >::locate	(	const Point &	query,
		Locate_type &	lt,
		int &	li,
		Face_handle	h = `Face_handle()`
	)		const

Same as above.

Additionally, the parameters lt and li describe where the query point is located. The variable lt is set to the locate type of the query. If lt==VERTEX, the variable li is set to the index of the vertex, and if lt==EDGE li is set to the index of the vertex opposite to the edge. Note that li has no meaning when the query type is FACE, OUTSIDE_CONVEX_HULL, or OUTSIDE_AFFINE_HULL.

◆ number_of_faces()

template<typename Traits , typename TDS >

size_type CGAL::Triangulation_on_sphere_2< Traits, TDS >::number_of_faces ( ) const

returns the number of faces.

Note that this includes ghost faces.

◆ operator=()

template<typename Traits , typename TDS >

Triangulation_on_sphere_2& CGAL::Triangulation_on_sphere_2< Traits, TDS >::operator= ( Triangulation_on_sphere_2< Traits, TDS > tr )

Assignment operator.

This performs a deep copy of the triangulation, duplicating both vertices and faces.

◆ segment() [1/2]

template<typename Traits , typename TDS >

Segment_3 CGAL::Triangulation_on_sphere_2< Traits, TDS >::segment ( const Edge & e ) const

returns the 3D line segment formed by the vertices of the edge e.

Precondition: t.dimension() \( \geq1\).

◆ segment() [2/2]

template<typename Traits , typename TDS >

Segment_3 CGAL::Triangulation_on_sphere_2< Traits, TDS >::segment	(	const Face_handle	f,
		int	i
	)		const

returns the 3D line segment formed by the vertices of the edge (f, i).

Precondition: t.dimension() \( \geq1\).

◆ segment_on_sphere() [1/2]

template<typename Traits , typename TDS >

Arc_on_sphere_2 CGAL::Triangulation_on_sphere_2< Traits, TDS >::segment_on_sphere ( const Edge & e ) const

returns the great circle arc formed by the vertices of the edge e.

Precondition: t.dimension() \( \geq1\).

◆ segment_on_sphere() [2/2]

template<typename Traits , typename TDS >

Arc_on_sphere_2 CGAL::Triangulation_on_sphere_2< Traits, TDS >::segment_on_sphere	(	const Face_handle	f,
		int	i
	)		const

returns the great circle arc formed by the vertices of the edge (f, i).

Precondition: t.dimension() \( \geq1\).

◆ solid_face_handles()

template<typename Traits , typename TDS >

Solid_face_handles CGAL::Triangulation_on_sphere_2< Traits, TDS >::solid_face_handles ( ) const

returns a range of iterators over all solid faces.

Note: While the value type of Solid_faces_iterator is Face, the value type of Solid_face_handles::iterator is Face_handle.

◆ triangle()

template<typename Traits , typename TDS >

Triangle_3 CGAL::Triangulation_on_sphere_2< Traits, TDS >::triangle ( const Face_handle f ) const

returns the 3D triangle formed by the three vertices of the face f.

Precondition: t.dimension() \( \geq2\).

◆ vertex_handles()

template<typename Traits , typename TDS >

Vertex_handles CGAL::Triangulation_on_sphere_2< Traits, TDS >::vertex_handles ( ) const

returns a range of iterators over all vertices.

Note: While the value type of Vertices_iterator is Vertex, the value type of Vertex_handles::iterator is Vertex_handle.

Inherits from

Definition

Types

Handles, Iterators, and Circulators

Creation

Ghost Predicates

Modifying the domain

Access Functions

Geometric Access Functions

All Face, Edge and Vertex Iterators

Face, Edge and Vertex Circulators

Combinatorial Predicates

Queries

Miscellaneous

Additional Inherited Members

Member Enumeration Documentation

◆ Locate_type

Constructor & Destructor Documentation

◆ Triangulation_on_sphere_2() [1/2]

◆ Triangulation_on_sphere_2() [2/2]

Member Function Documentation

◆ adjacent_vertices()

◆ all_face_handles()

◆ dimension()

◆ incident_edges()

◆ incident_faces() [1/2]

◆ incident_faces() [2/2]

◆ is_edge()

◆ is_face()

◆ is_ghost() [1/2]

◆ is_ghost() [2/2]

◆ is_valid()

◆ locate() [1/2]

◆ locate() [2/2]

◆ number_of_faces()

◆ operator=()

◆ segment() [1/2]

◆ segment() [2/2]

◆ segment_on_sphere() [1/2]

◆ segment_on_sphere() [2/2]

◆ solid_face_handles()

◆ triangle()

◆ vertex_handles()