\( \newcommand{\E}{\mathrm{E}} \) \( \newcommand{\A}{\mathrm{A}} \) \( \newcommand{\R}{\mathrm{R}} \) \( \newcommand{\N}{\mathrm{N}} \) \( \newcommand{\Q}{\mathrm{Q}} \) \( \newcommand{\Z}{\mathrm{Z}} \) \( \def\ccSum #1#2#3{ \sum_{#1}^{#2}{#3} } \def\ccProd #1#2#3{ \sum_{#1}^{#2}{#3} }\)
CGAL 4.8.1 - dD Triangulations
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
TriangulationTraits Concept Reference

Definition

This concept describes the geometric types and predicates required to build a triangulation. It corresponds to the first template parameter of the class CGAL::Triangulation<TriangulationTraits, TriangulationDataStructure>.

Refines:
SpatialSortingTraits_d

If a range of points is inserted, the traits must refine SpatialSortingTraits_d. The insertion is then optimized using spatial sorting. This is not required if the points are inserted one by one.

Has Models:
CGAL::Epick_d<Dim>
See Also
DelaunayTriangulationTraits

Types

typedef unspecified_type Dimension
 A type representing the dimension of the predicates (but not necessarily the one of Point_d). More...
 
typedef unspecified_type Point_d
 A type representing a point in Euclidean space. More...
 
typedef unspecified_type Orientation_d
 A predicate object that must provide the templated operator template<typename ForwardIterator> Orientation operator()(ForwardIterator start, ForwardIterator end). More...
 
typedef unspecified_type Contained_in_affine_hull_d
 A predicate object that must provide the templated operator template<typename ForwardIterator> bool operator()(ForwardIterator start, ForwardIterator end, const Point_d & p). More...
 

In the \( D\)-dimensional oriented space, a \( k-1\) dimensional subspace (flat) defined by \( k\) points can be oriented in two different ways.

Choosing the orientation of any simplex defined by \( k\) points in a flat fixes the orientation of the flat and therefore the orientation of all other simplices in this flat. To be able to orient lower dimensional flats, we use the following classes:

typedef unspecified_type Flat_orientation_d
 A type representing an orientation of an affine subspace of dimension \( k\) strictly smaller than the dimension of the traits.
 
typedef unspecified_type Construct_flat_orientation_d
 A construction object that must provide the templated operator template<typename ForwardIterator> Flat_orientation_d operator()(ForwardIterator start, ForwardIterator end). More...
 
typedef unspecified_type In_flat_orientation_d
 A predicate object that must provide the templated operator template<typename ForwardIterator> Orientation operator()(Flat_orientation_d orient,ForwardIterator start, ForwardIterator end). More...
 
typedef unspecified_type Compare_lexicographically_d
 A predicate object that must provide the operator Comparison_result operator()(const Point_d & p, const Point_d & q). More...
 

Creation

 TriangulationTraits ()
 The default constructor.
 

Operations

The following methods permit access to the traits class's predicates:

Orientation_d orientation_d_object () const
 
Contained_in_affine_hull_d contained_in_affine_hull_d_object () const
 
Construct_flat_orientation_d construct_flat_orientation_d_object () const
 
In_flat_orientation_d in_flat_orientation_d_object () const
 
Compare_lexicographically_d compare_lexicographically_d_object () const
 

Member Typedef Documentation

A predicate object that must provide the operator Comparison_result operator()(const Point_d & p, const Point_d & q).

The operator returns SMALLER if p is lexicographically smaller than point q, EQUAL if both points are the same and LARGER otherwise.

A construction object that must provide the templated operator template<typename ForwardIterator> Flat_orientation_d operator()(ForwardIterator start, ForwardIterator end).

The flat spanned by the points in the range R=[start, end) can be oriented in two different ways, the operator returns an object that allow to orient that flat so that R=[start, end) defines a positive simplex.

Precondition
If Dimension=CGAL::Dimension_tag<D>, then std::distance(start,end)=D+1. The points in range [start,end) must be affinely independent. \( 2\leq k\leq D\).

A predicate object that must provide the templated operator template<typename ForwardIterator> bool operator()(ForwardIterator start, ForwardIterator end, const Point_d & p).

The operator returns true if and only if point p is contained in the affine space spanned by the points in the range [start, end). That affine space is also called the affine hull of the points in the range.

Precondition
If Dimension=CGAL::Dimension_tag<D>, then std::distance(start,end)=D+1. The points in the range must be affinely independent. Note that in the CGAL kernels, this predicate works also with affinely dependent points. \( 2\leq k\leq D\).

A type representing the dimension of the predicates (but not necessarily the one of Point_d).

If \( n \) is the number of points required by the Orientation_d predicate, then Dimension \( = n - 1\). It can be static (Dimension=CGAL::Dimension_tag<int dim>) or dynamic (Dimension=CGAL::Dynamic_dimension_tag).

A predicate object that must provide the templated operator template<typename ForwardIterator> Orientation operator()(Flat_orientation_d orient,ForwardIterator start, ForwardIterator end).

The operator returns CGAL::POSITIVE, CGAL::NEGATIVE or CGAL::COPLANAR depending on the orientation of the simplex defined by the points in the range [start, end). The points are supposed to belong to the lower dimensional flat whose orientation is given by orient.

Precondition
std::distance(start,end)=k where \( k\) is the number of points used to construct orient. \( 2\leq k\leq D\).

A predicate object that must provide the templated operator template<typename ForwardIterator> Orientation operator()(ForwardIterator start, ForwardIterator end).

The operator returns the orientation of the simplex defined by the points in the range [start, end); the value can be CGAL::POSITIVE, CGAL::NEGATIVE or CGAL::COPLANAR.

Precondition
If Dimension=CGAL::Dimension_tag<D>, then std::distance(start,end)=D+1.

A type representing a point in Euclidean space.

It must be DefaultConstructible, CopyConstructible and Assignable.