TriangulationOnSphereTraits_2 Concept Reference

Definition

Refines

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.

Has Models:

CGAL::Delaunay_triangulation_on_sphere_traits_2

CGAL::Projection_on_sphere_traits_3

See also

DelaunayTriangulationOnSphereTraits_2

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

Operations
The following functions provide access to the predicate and constructor objects.
Compare_on_sphere_2	compare_on_sphere_2_object ()
Equal_on_sphere_2	equal_on_sphere_2_object ()
Orientation_on_sphere_2	orientation_on_sphere_2_object ()
Side_of_oriented_circle_on_sphere_2	side_of_oriented_circle_on_sphere_2_object ()
Collinear_are_strictly_ordered_on_great_circle_2	collinear_are_strictly_ordered_on_great_circle_2_object ()
Construct_arc_on_sphere_2	construct_arc_on_sphere_2_object ()
Construct_point_on_sphere_2	construct_point_on_sphere_2_object ()
Construct_point_3	construct_point_3_object ()
Construct_segment_3	construct_segment_3_object ()
Construct_triangle_3	construct_triangle_3_object ()

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 model-defined \( \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. See also CGAL::Delaunay_triangulation_on_sphere_traits_2
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...

Member Typedef Documentation

Collinear_are_strictly_ordered_on_great_circle_2

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.

Compare_on_sphere_2

typedef unspecified_type TriangulationOnSphereTraits_2::Compare_on_sphere_2

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, user-defined strict total order of points.

Construct_arc_on_sphere_2

typedef unspecified_type TriangulationOnSphereTraits_2::Construct_arc_on_sphere_2

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

Precondition

p and q are not diametrically opposed.

Construct_point_3

typedef unspecified_type TriangulationOnSphereTraits_2::Construct_point_3

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.

Construct_point_on_sphere_2

typedef unspecified_type TriangulationOnSphereTraits_2::Construct_point_on_sphere_2

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 (user-defined) point-on-sphere representation.

Construct_segment_3

typedef unspecified_type TriangulationOnSphereTraits_2::Construct_segment_3

Construction object.

Must provide the operator:

Segment_3 operator()(Point_3 p, Point_3 q),

which constructs a segment from two 3D points.

Construct_triangle_3

typedef unspecified_type TriangulationOnSphereTraits_2::Construct_triangle_3

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.

Equal_on_sphere_2

typedef unspecified_type TriangulationOnSphereTraits_2::Equal_on_sphere_2

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.

Orientation_on_sphere_2

typedef unspecified_type TriangulationOnSphereTraits_2::Orientation_on_sphere_2

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.

Side_of_oriented_circle_on_sphere_2

typedef unspecified_type TriangulationOnSphereTraits_2::Side_of_oriented_circle_on_sphere_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, 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.

Member Function Documentation

are_points_too_close()

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

is_on_sphere()

bool TriangulationOnSphereTraits_2::is_on_sphere

(

Point_on_sphere_2

p

)

returns whether the point p is on the sphere or not.

Note

A point that is not on the sphere will not be inserted in the triangulation.

set_center()

void TriangulationOnSphereTraits_2::set_center

(

Point_3

center

)

sets the center of the sphere.

Note

This function is meant to be used only by the triangulation class as modifying the domain requires clearing the triangulation. Users can change the domain using CGAL::Triangulation_on_sphere_2::set_center_and_radius().

set_radius()

void TriangulationOnSphereTraits_2::set_radius

(

FT

radius

)

sets the radius of the sphere.

Note

This function is meant to be used only by the triangulation class as modifying the domain requires clearing the triangulation. Users can change the domain using CGAL::Triangulation_on_sphere_2::set_center_and_radius().