CGAL 5.6.3 - 2D Triangulations on the Sphere

Loading...
Searching...
No Matches
List of all members | Public Types
CGAL::Delaunay_triangulation_on_sphere_traits_2< LK, SK > Class Template Reference
2D Triangulation on the Sphere Reference » Triangulation Classes

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

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

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