CGAL 6.1 - 2D Triangulations on the Sphere

Loading...
Searching...
No Matches
List of all members
CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS > Class Template Reference
Reference Manual » Triangulation Classes

`#include <CGAL/Delaunay_triangulation_on_sphere_2.h>`

## Inherits from

CGAL::Triangulation_on_sphere_2< Traits, TDS >.

## Definition

template<typename Traits, typename TDS>
class CGAL::Delaunay_triangulation_on_sphere_2< Traits, TDS >

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.
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[`.
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[`.
| Delaunay_triangulation_on_sphere_2 (const Delaunay_triangulation_on_sphere_2< Traits, TDS > &tr)
| Copy constructor.

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

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

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

## 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.
Face_handle | locate (const Point &query, Locate_type &lt, int &li, Face_handle h=Face_handle()) const
| Same as above.
| Triangulation_on_sphere_2 (const Traits &gt=Traits())
| constructs an empty triangulation.
| 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.
Triangulation_on_sphere_2 & | operator= (Triangulation_on_sphere_2< Traits, TDS > tr)
| Assignment operator.
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.
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.
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:
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.
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`.
Segment_3 | segment (const Face_handle f, int i) const
| returns the 3D line segment formed by the vertices of the edge `(f, i)`.
Arc_on_sphere_2 | segment_on_sphere (const Edge &e) const
| returns the great circle arc formed by the vertices of the edge `e`.
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)`.
Triangle_3 | triangle (const Face_handle f) const
| returns the 3D triangle formed by the three vertices of the face `f`.
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.
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.
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.
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`.
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`.
Face_circulator | incident_faces (Vertex_handle v) const
| Starts at an arbitrary face incident to the vertex `v`.
Face_circulator | incident_faces (Vertex_handle v, Face_handle f) const
| Starts at face `f`.
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.
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.
bool | is_valid (bool verbose=false, int level=0) const
| tests the validity of the triangulation as a `Triangulation_on_sphere_2`.
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 responsibility 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 >

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.

## ◆ 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 >

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.

## ◆ 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 counterclockwise 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 responsibility 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.