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

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