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

#include <CGAL/Delaunay_triangulation_on_sphere_2.h>

Inherits from

CGAL::Triangulation_on_sphere_2< Traits, TDS >.

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
Traitsis the geometric traits; it must be a model of DelaunayTriangulationOnSphereTraits_2.
TDSis 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<Traits>, CGAL::Triangulation_on_sphere_face_base_2<Traits> >.
See also
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...
 

Additional Inherited Members

- 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)
 
void set_radius (const FT radius)
 
void set_center_and_radius (const Point_3 &c, const FT radius)
 
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.
 
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...
 
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
 

Constructor & Destructor Documentation

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

Member Function Documentation

◆ 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<OutputItFaces, OutputItBoundaryEdges> 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
OutItFacesis an output iterator with Face_handle as value type.
OutItBoundaryEdgesis 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).

See also
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
PointOnSphereIteratormust 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.