DelaunayTriangulationTraits_3 Concept Reference

Definition

The concept DelaunayTriangulationTraits_3 is the first template parameter of the class CGAL::Delaunay_triangulation_3. It defines the geometric objects (points, segments...) forming the triangulation together with a few geometric predicates and constructions on these objects.

Refines

TriangulationTraits_3

Has models

CGAL::Exact_predicates_inexact_constructions_kernel (recommended)

CGAL::Exact_predicates_exact_constructions_kernel (recommended for Voronoi)

CGAL::Filtered_kernel

CGAL::Cartesian

CGAL::Simple_cartesian

CGAL::Homogeneous

CGAL::Simple_homogeneous

In addition to the requirements described for the traits class of CGAL::Triangulation_3, the geometric traits class of a Delaunay triangulation must fulfill the following requirements:

Types
typedef unspecified_type	Line_3
	The line type.
typedef unspecified_type	Object_3
	The object type.
typedef unspecified_type	Ray_3
	The ray type.
typedef unspecified_type	Coplanar_side_of_bounded_circle_3
	A predicate object that must provide the function operator.
typedef unspecified_type	Side_of_oriented_sphere_3
	A predicate object that must provide the function operator.
typedef unspecified_type	Compare_distance_3
	A predicate object that must provide the function operator.
When is_Gabriel functions are used, the traits class must in addition provide the following predicate object:
typedef unspecified_type	Side_of_bounded_sphere_3
	A predicate object that must provide the function operators.
In addition, only when the dual operations are used, the traits class must provide the following constructor objects:
typedef unspecified_type	Construct_circumcenter_3
	A constructor object that must provide the function operator.
typedef unspecified_type	Construct_object_3
	A constructor object that must provide the function operators.
typedef unspecified_type	Construct_equidistant_line_3
	A constructor object that must provide the function operator.
typedef unspecified_type	Construct_ray_3
	A constructor object that must provide the function operator.

Operations
The following functions give access to the predicate and construction objects:
Coplanar_side_of_bounded_circle_3	coplanar_side_of_bounded_circle_3_object ()
Side_of_oriented_sphere_3	side_of_oriented_sphere_3_object ()
When using the Fast_location policy or the CGAL::Delaunay_triangulation_3::nearest_vertex() function, the traits must provide:
Compare_distance_3	compare_distance_3_object ()
The following functions must be provided only if the methods of Delaunay_triangulation_3 returning elements of the Voronoi diagram are instantiated:
Construct_circumcenter_3	construct_circumcenter_3_object ()
Construct_object_3	construct_object_3_object ()
Construct_equidistant_line_3	construct_equidistant_line_object ()
Construct_ray_3	construct_ray_3_object ()

Member Typedef Documentation

Compare_distance_3

typedef unspecified_type DelaunayTriangulationTraits_3::Compare_distance_3

A predicate object that must provide the function operator.

Comparison_result operator()(Point p, Point q, Point r),

which compares the distance between p and q to the distance between p and r.

It is only needed when using the Fast_location policy or the nearest_vertex function.

Construct_circumcenter_3

typedef unspecified_type DelaunayTriangulationTraits_3::Construct_circumcenter_3

A constructor object that must provide the function operator.

Point_3 operator()(Point_3 p, Point_3 q, Point_3 r, Point_3 s),

which constructs the circumcenter of four points.

Precondition

p, q, r and s must be non coplanar.

It must also provide the function operator

Point_3 operator()(Point_3 p, Point_3 q, Point_3 r),

which constructs the circumcenter of three points.

Precondition

p, q and r must be non collinear.

Construct_equidistant_line_3

typedef unspecified_type DelaunayTriangulationTraits_3::Construct_equidistant_line_3

A constructor object that must provide the function operator.

Line_3 operator()(Point_3 p1, Point_3 p2, Point_3 p3),

which constructs the line which is at the same distance from the three points.

Precondition

p1, p2 and p3 must be non collinear.

Construct_object_3

typedef unspecified_type DelaunayTriangulationTraits_3::Construct_object_3

A constructor object that must provide the function operators.

Object_3 operator()(Point_3 p),

Object_3 operator()(Segment_3 s) and

Object_3 operator()(Ray_3 r)

that construct an object respectively from a point, a segment and a ray.

Construct_ray_3

typedef unspecified_type DelaunayTriangulationTraits_3::Construct_ray_3

A constructor object that must provide the function operator.

Ray_3 operator()(Point_3 p, Line_3 l),

which constructs the ray starting at p with direction given by l.

Coplanar_side_of_bounded_circle_3

typedef unspecified_type DelaunayTriangulationTraits_3::Coplanar_side_of_bounded_circle_3

A predicate object that must provide the function operator.

Bounded_side operator()(Point p, Point q, Point r, Point s),

which determines the bounded side of the circle defined by p, q, and r on which s lies.

Precondition

p, q, r, and s are coplanar and p, q, and r are not collinear.

Side_of_bounded_sphere_3

typedef unspecified_type DelaunayTriangulationTraits_3::Side_of_bounded_sphere_3

A predicate object that must provide the function operators.

Bounded_side operator()(Point_3 p, Point_3 q, Point_3 t),

which returns the position of the point t relative to the sphere that has pq as its diameter,

Bounded_side operator()(Point_3 p, Point_3 q, Point_3 r, Point_3 t),

which returns the position of the point t relative to the sphere passing through p, q, and r and whose center is in the plane defined by these three points.

Side_of_oriented_sphere_3

typedef unspecified_type DelaunayTriangulationTraits_3::Side_of_oriented_sphere_3

A predicate object that must provide the function operator.

Oriented_side operator()(Point p, Point q, Point r, Point s, Point t),

which determines on which side of the oriented sphere circumscribing p, q, r, s the point t lies.