CGAL 6.1 - 2D Triangulations on the Sphere

Loading...
Searching...
No Matches
List of all members
TriangulationOnSphereTraits_2 Concept Reference
Reference Manual » Concepts

## 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.
typedef unspecified_type | Compare_on_sphere_2
| Predicate object type.
typedef unspecified_type | Equal_on_sphere_2
| Predicate object type.
typedef unspecified_type | Orientation_on_sphere_2
| Predicate object type.
typedef unspecified_type | Side_of_oriented_circle_on_sphere_2
| Predicate object type.

## Constructions
typedef unspecified_type | Construct_arc_on_sphere_2
| Construction object.
typedef unspecified_type | Construct_point_on_sphere_2
| Construction object.
typedef unspecified_type | Construct_point_3
| Construction object.
typedef unspecified_type | Construct_segment_3
| Construction object.
typedef unspecified_type | Construct_triangle_3
| Construction object.

## 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.
Point_3 | center () const
| returns the center of the sphere.
void | set_radius (FT radius)
| sets the radius of the sphere.
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.
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).

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

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