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

#include <CGAL/Delaunay_triangulation_on_sphere_2.h>

## Definition

The class Delaunay_triangulation_on_sphere_2 is designed to represent the Delaunay triangulation of a set of points on the 2-sphere.

A Delaunay triangulation of a set of points is a triangulation of the set of points that fulfills the following empty circle property (also called Delaunay property): the circumscribing sphere of any simplex of the triangulation contains no point of the set in its interior. For a point set with no case of co-circularity of more than three points, the Delaunay triangulation is unique, and defined as the dual of the Voronoi diagram of the points.

The setting of 3D points on the 2-sphere is particular in that the empty circle property can be reduced to a single 3D orientation test [1].

Template Parameters
 Traits is the geometric traits; it must be a model of DelaunayTriangulationOnSphereTraits_2. TDS is the triangulation data structure, which must be a model of TriangulationDataStructure_2 whose vertex base must be a model of TriangulationOnSphereVertexBase_2 and whose face base must be a model of TriangulationOnSphereFaceBase_2. CGAL provides a default instantiation for this parameter, which is the class CGAL::Triangulation_data_structure_2 < CGAL::Triangulation_on_sphere_vertex_base_2, CGAL::Triangulation_on_sphere_face_base_2 >.
CGAL::Triangulation_on_sphere_2<Traits, TDS>
Examples:
Triangulation_on_sphere_2/triang_on_sphere.cpp, Triangulation_on_sphere_2/triang_on_sphere_exact.cpp, Triangulation_on_sphere_2/triang_on_sphere_proj.cpp, and Triangulation_on_sphere_2/triang_on_sphere_range.cpp.

## Types

typedef Traits Geom_traits
The traits class.

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

## Creation

Delaunay_triangulation_on_sphere_2 (const Point_3 &c, const FT r)
introduces an empty triangulation and sets the center and radius of the sphere to c and r respectively.

Delaunay_triangulation_on_sphere_2 (const Geom_traits &gt=Geom_traits())
introduces an empty triangulation. More...

template<typename PointOnSphereIterator >
Delaunay_triangulation_on_sphere_2 (PointOnSphereIterator first, PointOnSphereIterator beyond, const Point_3 &center, const FT radius)
introduces an empty triangulation, sets the center and radius of the sphere to c and r respectively, and inserts the point range [first; beyond[. More...

template<typename PointOnSphereIterator >
Delaunay_triangulation_on_sphere_2 (PointOnSphereIterator first, PointOnSphereIterator beyond, const Geom_traits &gt=Geom_traits())
introduces an empty triangulation whose center and radius are set according to values within the traits and inserts the point range [first;beyond[. More...

Delaunay_triangulation_on_sphere_2 (const Delaunay_triangulation_on_sphere_2< Traits, TDS > &tr)
Copy constructor. More...

## Predicates

Oriented_side side_of_oriented_circle (Face_handle f, const Point &p) const
returns the side of p with respect to the circle circumscribing the triangle associated with f.

## Insertion and Removal

Methods for the insertion and removal of points on the sphere.

In the degenerate setting of co-circular points, the Delaunay triangulation is known not to be uniquely defined. In this case, CGAL chooses a particular Delaunay triangulation using a symbolic perturbation scheme [2].

Vertex_handle insert (const Point &p, Face_handle f=Face_handle())
inserts the point p. More...

Vertex_handle insert (const Point &p, Locate_type &lt, Face_handle loc, int li)
inserts the point p at the location given by (lt, loc, li). More...

Vertex_handle push_back (const Point &p)
Equivalent to insert(p).

template<class PointOnSphereIterator >
size_type insert (PointOnSphereIterator first, PointOnSphereIterator beyond)
inserts the points in the range [first, beyond) and returns the number of inserted points. More...

void remove (Vertex_handle v)
removes the vertex v from the triangulation.

## Queries

template<typename OutputItFaces , typename OutputItBoundaryEdges >
std::pair< OutputItFaces, OutputItBoundaryEdges > get_conflicts_and_boundary (const Point &p, OutputItFaces fit, OutputItBoundaryEdges eit, Face_handle start) const
outputs the faces and boundary edges of the conflict zone of point p into output iterators. More...

## Voronoi Diagram

The following member functions provide the elements of the dual Voronoi diagram.

Two different embeddings are possible: a "straight" embedding, using line segments living in Euclidean 3D sphere, and a "curved" embedding, using arc segments on the sphere.

Note that the following operations are constructions, which should be kept in mind in the choice of the underlying kernel.

Point_3 dual (const Face_handle f) const
returns the center of the circle circumscribed to face f

Segment_3 dual (const Edge &e) const
returns the line segment with endpoints the circumcenters of the faces incident to the edge e.

Segment_3 dual (const Edge_circulator ec) const
returns the line segment with endpoints the circumcenters of the faces incident to the edge *ec.

Segment_3 dual (const All_edges_iterator ei) const
returns the line segment with endpoints the circumcenters of the faces incident to the edge *ei.

Point dual_on_sphere (const Face_handle f) const
returns the intersection of the dual of the face f and the sphere. More...

Arc_on_sphere_2 dual_on_sphere (const Edge &e) const
returns the arc of great circle with endpoints the circumcenters of the faces incident to the edge e. More...

Arc_on_sphere_2 dual_on_sphere (const Edge_circulator ec) const
returns the arc of great circle with endpoints the circumcenters of the faces incident to the edge *ec. More...

Arc_on_sphere_2 dual_on_sphere (const All_edges_iterator ei) const
returns the arc of great circle with endpoints the circumcenters of the faces incident to the edge *ei. More...

## Miscellaneous

bool is_valid (bool verbose=false, int level=0) const
tests the validity of the triangulation as a Triangulation_on_sphere_2 and additionally tests the Delaunay property. More...

Public Types inherited from CGAL::Triangulation_on_sphere_2< Traits, TDS >
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...

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.

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.

Public Member Functions inherited from CGAL::Triangulation_on_sphere_2< Traits, TDS >
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...

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.

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

void set_center (const Point_3 &c)

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.

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

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.

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

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

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

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

## ◆ Delaunay_triangulation_on_sphere_2() [1/4]

template<typename Traits , typename TDS >
 CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::Delaunay_triangulation_on_sphere_2 ( const Geom_traits & gt = Geom_traits() )

introduces an empty triangulation.

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

## ◆ Delaunay_triangulation_on_sphere_2() [2/4]

template<typename Traits , typename TDS >
template<typename PointOnSphereIterator >
 CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::Delaunay_triangulation_on_sphere_2 ( PointOnSphereIterator first, PointOnSphereIterator beyond, const Point_3 & center, const FT radius )

introduces an empty triangulation, sets the center and radius of the sphere to c and r respectively, and inserts the point range [first; beyond[.

Template Parameters
 PointOnSphereIterator must be a model of InputIterator with value type Point_on_sphere_2 or Point_3.

## ◆ Delaunay_triangulation_on_sphere_2() [3/4]

template<typename Traits , typename TDS >
template<typename PointOnSphereIterator >
 CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::Delaunay_triangulation_on_sphere_2 ( PointOnSphereIterator first, PointOnSphereIterator beyond, const Geom_traits & gt = Geom_traits() )

introduces an empty triangulation whose center and radius are set according to values within the traits and inserts the point range [first;beyond[.

Warning
It is the user's responsability to ensure that the center and radius are set as intended in gt.
Template Parameters
 PointOnSphereIterator must be a model of InputIterator with value type Point_on_sphere_2 or Point_3.

## ◆ Delaunay_triangulation_on_sphere_2() [4/4]

template<typename Traits , typename TDS >
 CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::Delaunay_triangulation_on_sphere_2 ( const Delaunay_triangulation_on_sphere_2< Traits, TDS > & tr )

Copy constructor.

All the vertices and faces are duplicated.

## ◆ dual_on_sphere() [1/4]

template<typename Traits , typename TDS >
 Point CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::dual_on_sphere ( const Face_handle f ) const

returns the intersection of the dual of the face f and the sphere.

Precondition
dimension() == 2 and f is a solid face.

## ◆ dual_on_sphere() [2/4]

template<typename Traits , typename TDS >
 Arc_on_sphere_2 CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::dual_on_sphere ( const Edge & e ) const

returns the arc of great circle with endpoints the circumcenters of the faces incident to the edge e.

Precondition
dimension() == 2 and e is not a ghost edge.

## ◆ dual_on_sphere() [3/4]

template<typename Traits , typename TDS >
 Arc_on_sphere_2 CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::dual_on_sphere ( const Edge_circulator ec ) const

returns the arc of great circle with endpoints the circumcenters of the faces incident to the edge *ec.

Precondition
dimension() == 2 and *ec is not a ghost edge.

## ◆ dual_on_sphere() [4/4]

template<typename Traits , typename TDS >
 Arc_on_sphere_2 CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::dual_on_sphere ( const All_edges_iterator ei ) const

returns the arc of great circle with endpoints the circumcenters of the faces incident to the edge *ei.

Precondition
dimension() == 2 and *ei is not a ghost edge.

## ◆ get_conflicts_and_boundary()

template<typename Traits , typename TDS >
template<typename OutputItFaces , typename OutputItBoundaryEdges >
 std::pair CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::get_conflicts_and_boundary ( const Point & p, OutputItFaces fit, OutputItBoundaryEdges eit, Face_handle start ) const

outputs the faces and boundary edges of the conflict zone of point p into output iterators.

This function outputs in the container pointed to by fit the faces which are in conflict with point p, i. e., the faces whose circumcircle contains p. It outputs in the container pointed to by eit the boundary of the zone in conflict with p. The boundary edges of the conflict zone are output in counter-clockwise order and each edge is described through its incident face which is not in conflict with p. The function returns in a std::pair the resulting output iterators.

Template Parameters
 OutItFaces is an output iterator with Face_handle as value type. OutItBoundaryEdges is an output iterator with Edge as value type.
Warning
This function makes uses of the member tds_data (see the concept TriangulationDSFaceBase_2) of the face to mark faces in conflict. It is the responsability of the user to make sure the flags are cleared.
Precondition
dimension() == 2.

## ◆ insert() [1/3]

template<typename Traits , typename TDS >
 Vertex_handle CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::insert ( const Point & p, Face_handle f = Face_handle() )

inserts the point p.

If the point p coincides with an already existing vertex, this vertex is returned and the triangulation remains unchanged. The optional parameter f is used to give a hint about the location of p.

## ◆ insert() [2/3]

template<typename Traits , typename TDS >
 Vertex_handle CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::insert ( const Point & p, Locate_type & lt, Face_handle loc, int li )

inserts the point p at the location given by (lt, loc, li).

Triangulation_on_sphere_2::locate()

## ◆ insert() [3/3]

template<typename Traits , typename TDS >
template<class PointOnSphereIterator >
 size_type CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >::insert ( PointOnSphereIterator first, PointOnSphereIterator beyond )

inserts the points in the range [first, beyond) and returns the number of inserted points.

Template Parameters
 PointOnSphereIterator must be a model of InputIterator with value type Point.

## ◆ is_valid()

template<typename Traits , typename TDS >
 bool CGAL::Delaunay_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 and additionally tests the Delaunay property.

This method is mainly useful for debugging Delaunay triangulation algorithms.