CGAL 5.6.1  2D Triangulations on the Sphere

SpatialSortingTraits_3
The concept TriangulationOnSphereTraits_2
describes the set of requirements to be fulfilled by any class used to instantiate the first template parameter of the class CGAL::Triangulation_on_sphere_2<Traits, Tds>
. This concept provides the types of the geometric primitives used in the triangulation and the function object types for the required predicates on those primitives.
In particular, the traits class is expected to contain information about the sphere (center and radius) on which the points of the triangulation lie, as well as to provide means to change this information.
Types  
typedef unspecified_type  FT 
The number type; must be a model of FieldNumberType .  
typedef unspecified_type  Point_on_sphere_2 
The point type of the triangulation, representing a point on the sphere.  
typedef unspecified_type  Arc_on_sphere_2 
An arc of a great circle, used to represent a curved segment (a Voronoi or a Delaunay edge).  
typedef unspecified_type  Point_3 
The 3D point type.  
typedef unspecified_type  Segment_3 
The 3D segment type.  
typedef unspecified_type  Triangle_3 
The 3D triangle type.  
Predicates  
typedef unspecified_type  Collinear_are_strictly_ordered_on_great_circle_2 
Predicate object type. More...  
typedef unspecified_type  Compare_on_sphere_2 
Predicate object type. More...  
typedef unspecified_type  Equal_on_sphere_2 
Predicate object type. More...  
typedef unspecified_type  Orientation_on_sphere_2 
Predicate object type. More...  
typedef unspecified_type  Side_of_oriented_circle_on_sphere_2 
Predicate object type. More...  
Constructions  
typedef unspecified_type  Construct_arc_on_sphere_2 
Construction object. More...  
typedef unspecified_type  Construct_point_on_sphere_2 
Construction object. More...  
typedef unspecified_type  Construct_point_3 
Construction object. More...  
typedef unspecified_type  Construct_segment_3 
Construction object. More...  
typedef unspecified_type  Construct_triangle_3 
Construction object. More...  
Configuration of the spherical domain  
void  set_center (Point_3 center) 
sets the center of the sphere. More...  
Point_3  center () const 
returns the center of the sphere.  
void  set_radius (FT radius) 
sets the radius of the sphere. More...  
FT  radius () const 
returns the radius of the sphere.  
Precision predicates  
When a kernel does not offer arbitrary precision  or at least an exact representation of algebraic coordinates, which is usually the case for the sake of computational speed, then most points that are theoretically on the sphere are not in practice exactly on the sphere. When this is the case, it cannot be guaranteed that all points are in a convex position, which can then result in points being hidden upon insertion, see [1]. To ensure that no point is hidden, a trick is to enforce a gap between points ([1], Lemma 4.1). This gap is based on a fixed maximal allowed distance \( \delta \) between a point and the theoretical sphere. The gap must then be at least \( 2 \sqrt{R\delta} \), where \( R \) is the radius of the sphere. The following two predicates serve to check if the point is on the sphere, that is if for a modeldefined \( \delta \) the distance to the sphere is smaller than \( \delta \) and if the distance between two points is greater than \( 2 \sqrt{R\delta} \). It is also of course possible to construct traits classes with arbitrary precision or with a representation that ensures that points are exactly on the sphere and in this case, \( \delta = 0 \) can be chosen and the predicates below are trivial.  
bool  is_on_sphere (Point_on_sphere_2 p) 
returns whether the point p is on the sphere or not. More...  
bool  are_points_too_close (Point_on_sphere_2 p, Point_on_sphere_2 q) 
returns whether the points p and q are too close (see Precision predicates). More...  
typedef unspecified_type TriangulationOnSphereTraits_2::Collinear_are_strictly_ordered_on_great_circle_2 
Predicate object type.
Must provide the operator:
bool operator()(Point_on_sphere_2 p, Point_on_sphere_2 q, Point_on_sphere_2 r)
which returns true
if r
strictly lies on the shortest path between p
and q
on the great circle passing through p
and q
.
If p
and q
are diametrically opposed, true
is returned.
Predicate object type.
Must provide the operator:
bool operator()(Point_on_sphere_2 p, Point_on_sphere_2 q)
which returns true
or false
based on a consistent, userdefined strict total order of points.
Construction object.
Must provide the operator:
Arc_on_sphere_2 operator()(Point_on_sphere_2 p, Point_on_sphere_2 q)
which introduces an arc of great circle, with source p
and target q
.
The circular arc constructed from a source, and a target, is defined as the set of points of the great circle that lie between the source p
and the target q
, when traversing the great circle counterclockwise seen from the side of the plane of the great circle pointed by its positive normal vectors.
In this definition, we say that a normal vector \( (a,b,c)\) is positive if \( (a,b,c)>(0,0,0)\) (i.e. \( (a>0)  (a==0) \&\& (b>0)  (a==0)\&\&(b==0)\&\&(c>0)\)).
p
and q
are not diametrically opposed. Construction object.
Must provide the operator:
Point_3 operator()(Point_on_sphere_2 p)
,
which expresses the point p
on the sphere as a point in the embedding 3D space.
Construction object.
Must provide the operator:
Point_on_sphere_2 operator()(Point_3 p)
,
which expresses the point p
, a 3D point living on the sphere, using the (userdefined) pointonsphere representation.
Construction object.
Must provide the operator:
Segment_3 operator()(Point_3 p, Point_3 q)
,
which constructs a segment from two 3D points.
Construction object.
Must provide the operator:
Triangle_3 operator()(Point_3 p, Point_3 q, Point_3 r)
,
which constructs a triangle from three 3D points.
Predicate object type.
Must provide the operator:
bool operator()(Point_on_sphere_2 p, Point_on_sphere_2 q)
which returns true
if, and only if, p
and q
are equal.
Predicate object type.
Must provide the operator:
Orientation operator()(Point_on_sphere_2 p, Point_on_sphere_2 q, Point_on_sphere_2 r)
which returns CGAL::POSITIVE
, if r
lies on the left hemisphere while walking the shortest path between p
and q
on the great circle defined by p
and q
; returns CGAL::NEGATIVE
if r
lies on the right hemisphere; and returns CGAL::COPLANAR
if r
lies on the great circle.
If p
and q
are diametrically opposed, CGAL::COPLANAR
is returned.
Predicate object type.
Must provide the operator:
bool operator()(Point_on_sphere_2 p, Point_on_sphere_2 q, Point_on_sphere_2 r, Point_on_sphere_2 s)
which returns CGAL::POSITIVE
, if s
lies on the positive side of the oriented plane h
defined by p
, q
, and r
; returns CGAL::NEGATIVE
if s
lies on the negative side of h
; and returns CGAL::COPLANAR
if s
lies on h
.
bool TriangulationOnSphereTraits_2::are_points_too_close  (  Point_on_sphere_2  p, 
Point_on_sphere_2  q  
) 
returns whether the points p
and q
are too close (see Precision predicates).
bool TriangulationOnSphereTraits_2::is_on_sphere  (  Point_on_sphere_2  p  ) 
returns whether the point p
is on the sphere or not.
void TriangulationOnSphereTraits_2::set_center  (  Point_3  center  ) 
sets the center of the sphere.
CGAL::Triangulation_on_sphere_2::set_center_and_radius()
. void TriangulationOnSphereTraits_2::set_radius  (  FT  radius  ) 
sets the radius of the sphere.
CGAL::Triangulation_on_sphere_2::set_center_and_radius()
.