CGAL 5.6 - 2D Triangulations on the Sphere
CGAL::Triangulation_on_sphere_2< Traits, TDS > Class Template Reference

#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
Traitsis the geometric traits; it must be a model of the concept TriangulationOnSphereTraits_2.
TDSis 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_typeVertex_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_iteratorAll_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_iteratorAll_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_iteratorSolid_edges
 Range type for iterating over all solid edges.
 
typedef unspecified_type Solid_faces_iterator
 Iterator over all solid faces.
 
typedef Iterator_range< unspecified_typeSolid_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_iteratorPoints
 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_2operator= (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_traitsgeom_traits () const
 returns a const reference to the triangulation traits object.
 
const Triangulation_data_structuretds () 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 Pointpoint (const Vertex_handle v)
 returns the geometric position of the vertex v.
 
const Pointpoint (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.