CGAL 5.5.2 - 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
LKa linear kernel type; it must be a model of Kernel.
SKa spherical kernel type; it must be a model of SphericalKernel refining LK.
Is Model Of:
DelaunayTriangulationOnSphereTraits_2
See also
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...
 

Member Typedef Documentation

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

Member Function Documentation

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