|
CGAL 5.6.1 - 2D Triangulations on the Sphere
|
|
CGAL 5.6.1 - 2D Triangulations on the Sphere
|
#include <CGAL/Delaunay_triangulation_on_sphere_traits_2.h>
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.
| 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. |
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... | |
| 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.
| 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.
| 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.
1.8.13