CGAL 5.5 - 2D Triangulations on the Sphere
CGAL::Delaunay_triangulation_on_sphere_traits_2< LK, SK > Class Template Reference

#include <CGAL/Delaunay_triangulation_on_sphere_traits_2.h>

## Definition

### template<typename LK, typename SK = CGAL::Spherical_kernel_3< LK, CGAL::Algebraic_kernel_for_spheres_2_3<typename LK::FT> >> class CGAL::Delaunay_triangulation_on_sphere_traits_2< LK, SK >

The class Delaunay_triangulation_on_sphere_traits_2 is a model of the concept DelaunayTriangulationOnSphereTraits_2.

The Point_on_sphere_2 type is implemented as a kernel Point_3 type.

If the kernel template parameter LK does not enable exact representation of points on sphere (i.e., at least a mean to represent algebraic coordinates), then it cannot be guaranteed that all points on the sphere are in a convex position and thus some points might be hidden upon insertion. It is possible to ensure that no point can be hidden by enforcing a tiny gap between points [1]. In Lemma 4.1 of this publication, it is in particular proven that if points lie within a distance $$\delta$$ of the sphere, no point is hidden as long as points are separated by at least $$2 \sqrt{R\delta}$$ with $$R$$ the radius of the sphere.

Thus, if LK offers exact representation, then $$\delta$$ is set to $$0$$. Otherwise, $$\delta$$ is set to the maximal distance between two consecutive LK::FT for the coordinates of a point that is (theoretically) on the sphere. This bound $$\delta$$ is then used in the functions is_on_sphere() and are_points_too_close() using the relation above to ensure that a point being inserted is either marked as "too close" (see CGAL::Triangulation_on_sphere_2<Traits,TDS>::Locate_type ) and thus not inserted, or guaranteed to not be hidden upon insertion.

Template Parameters
 LK a linear kernel type; it must be a model of Kernel. SK a spherical kernel type; it must be a model of SphericalKernel refining LK.
Is Model Of:
DelaunayTriangulationOnSphereTraits_2
CGAL::Projection_on_sphere_traits_3
Examples:
Triangulation_on_sphere_2/triang_on_sphere.cpp.

## Public Types

typedef LK::FT FT
The field number type.

typedef LK::Point_3 Point_on_sphere_2

typedef SK::Circular_arc_3 Arc_on_sphere_2
An arc of a great circle, used to represent a curved segment on the sphere (Voronoi or Delaunay edge).

typedef LK::Point_3 Point_3

typedef LK::Segment_3 Segment_3

typedef LK::Triangle_3 Triangle_3

## Predicates

typedef unspecified_type Collinear_are_strictly_ordered_on_great_circle_2
Internally uses LK::Coplanar_orientation_3

typedef LK::Compare_xyz_3 Compare_on_sphere_2

typedef unspecified_type Equal_on_sphere_2
If the kernel cannot represent algebraic coordinates exactly, there is a tolerance around the sphere, and thus different points of $$\mathbb{R}^3$$ can actually correspond to the same point on the sphere. More...

typedef LK::Orientation_3 Side_of_oriented_circle_on_sphere_2

typedef unspecified_type Orientation_on_sphere_2
Internally uses LK::Orientation_3

## Constructions

typedef unspecified_type Construct_arc_on_sphere_2
Internally uses SK::Construct_circular_arc_3

typedef LK::Construct_circumcenter_3 Construct_circumcenter_3

typedef LK::Construct_point_3 Construct_point_3

typedef LK::Construct_segment_3 Construct_segment_3

typedef LK::Construct_triangle_3 Construct_triangle_3

## Precision predicates

bool is_on_sphere (const Point_on_sphere_2 &p) const
returns whether p is exactly on the sphere if LK can represent algebraic coordinates, or whether p is within an automatically computed small distance otherwise. More...

bool are_points_too_close (const Point_on_sphere_2 &p, const Point_on_sphere_2 &q) const
returns false if LK can represent algebraic coordinates, or whether the distance between p and q is lower than $$2 \sqrt{R\delta}$$ otherwise. More...

## ◆ Equal_on_sphere_2

template<typename LK , typename SK = CGAL::Spherical_kernel_3< LK, CGAL::Algebraic_kernel_for_spheres_2_3<typename LK::FT> >>
 typedef unspecified_type CGAL::Delaunay_triangulation_on_sphere_traits_2< LK, SK >::Equal_on_sphere_2

If the kernel cannot represent algebraic coordinates exactly, there is a tolerance around the sphere, and thus different points of $$\mathbb{R}^3$$ can actually correspond to the same point on the sphere.

This functor checks if two points project onto the same point on the sphere.

## ◆ are_points_too_close()

template<typename LK , typename SK = CGAL::Spherical_kernel_3< LK, CGAL::Algebraic_kernel_for_spheres_2_3<typename LK::FT> >>
 bool CGAL::Delaunay_triangulation_on_sphere_traits_2< LK, SK >::are_points_too_close ( const Point_on_sphere_2 & p, const Point_on_sphere_2 & q ) const

returns false if LK can represent algebraic coordinates, or whether the distance between p and q is lower than $$2 \sqrt{R\delta}$$ otherwise.

## ◆ is_on_sphere()

template<typename LK , typename SK = CGAL::Spherical_kernel_3< LK, CGAL::Algebraic_kernel_for_spheres_2_3<typename LK::FT> >>
 bool CGAL::Delaunay_triangulation_on_sphere_traits_2< LK, SK >::is_on_sphere ( const Point_on_sphere_2 & p ) const

returns whether p is exactly on the sphere if LK can represent algebraic coordinates, or whether p is within an automatically computed small distance otherwise.