#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

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

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

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

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

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

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.

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

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

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

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.

Inherits from

Definition

Types

Creation

Predicates

Insertion and Removal

Queries

Voronoi Diagram

Miscellaneous

Additional Inherited Members

Constructor & Destructor Documentation

◆ Delaunay_triangulation_on_sphere_2() [1/4]

◆ Delaunay_triangulation_on_sphere_2() [2/4]

◆ Delaunay_triangulation_on_sphere_2() [3/4]

◆ Delaunay_triangulation_on_sphere_2() [4/4]

Member Function Documentation

◆ dual_on_sphere() [1/4]

◆ dual_on_sphere() [2/4]

◆ dual_on_sphere() [3/4]

◆ dual_on_sphere() [4/4]

◆ get_conflicts_and_boundary()

◆ insert() [1/3]

◆ insert() [2/3]

◆ insert() [3/3]

◆ is_valid()