Navigation: Up, Table of Contents, Bibliography, Index, Title Page

## DelaunayTriangulationTraits_3

### Definition

The concept DelaunayTriangulationTraits_3 is the first template parameter of the class 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

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

### Types

DelaunayTriangulationTraits_3::Line_3
| The line type.
DelaunayTriangulationTraits_3::Object_3
| The object type.
DelaunayTriangulationTraits_3::Plane_3
| The plane type.
DelaunayTriangulationTraits_3::Ray_3
| The ray 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.
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.

The following additional predicate is required only when the Triangulation_hierarchy_3 is used on top of Delaunay_triangulation_3:

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.

In addition, only when the dual operations are used, the traits class must provide the following constructor objects:

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 contructs 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 contructs the circumcenter of three points. Precondition: p, q and r must be non collinear.
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.
DelaunayTriangulationTraits_3::Construct_perpendicular_line_3
| A constructor object that must provide the function operator Line_3 operator()(Plane_3 pl, Point_3 p), which constructs the line perpendicular to pl passing through p.
DelaunayTriangulationTraits_3::Construct_plane_3
| A constructor object that must provide the function operator Plane_3 operator()(Point_3 p, Point_3 q, Point_3 r), which constructs the plane passing through p, q and r. Precondition: p, q and r are non collinear.
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.

### Operations

The following functions give access to the predicate and construction objects:

Coplanar_side_of_bounded_circle_3
| traits.coplanar_side_of_bounded_circle_3_object ()
Side_of_oriented_sphere_3
| traits.side_of_oriented_sphere_3_object ()

When using the triangulation hierarchy, the traits must provide:

Compare_distance_3 | traits.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
| traits.construct_circumcenter_3_object ()
Construct_object_3 | traits.construct_object_3_object ()
Construct_perpendicular_line_3
| traits.construct_perpendicular_line_object ()
Construct_plane_3 | traits.construct_plane_3_object ()
Construct_ray_3 | traits.construct_ray_3_object ()

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

Next: RegularTriangulationTraits_3

Navigation: Table of Contents, Bibliography, Index, Title Page

The CGAL Project . Tue, December 21, 2004 .