CGAL 6.1 - dD Triangulations

Loading...
Searching...
No Matches
List of all members
TriangulationTraits Concept Reference
Reference Manual » Concepts

## 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>`
  `CGAL::Epeck_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`).
typedef unspecified_type | Point_d
| A type representing a point in Euclidean space.
typedef unspecified_type | Orientation_d
| A predicate object that must provide the templated operator `template<typename ForwardIterator> Orientation operator()(ForwardIterator start, ForwardIterator end)`.
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)`.
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)`.
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)`.
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)`.

## Creation
| TriangulationTraits ()
| The default constructor (optional).

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

## ◆ Compare_lexicographically_d

typedef unspecified_type TriangulationTraits::Compare_lexicographically_d

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.

## ◆ Construct_flat_orientation_d

typedef unspecified_type TriangulationTraits::Construct_flat_orientation_d

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

## ◆ Contained_in_affine_hull_d

typedef unspecified_type TriangulationTraits::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)`.

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

## ◆ Dimension

typedef unspecified_type TriangulationTraits::Dimension

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

## ◆ In_flat_orientation_d

typedef unspecified_type TriangulationTraits::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)`.

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

## ◆ Orientation_d

typedef unspecified_type TriangulationTraits::Orientation_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`.

## ◆ Point_d

typedef unspecified_type TriangulationTraits::Point_d

A type representing a point in Euclidean space.

It must be `DefaultConstructible`, `CopyConstructible` and `Assignable`.

## Constructor & Destructor Documentation

## ◆ TriangulationTraits()

TriangulationTraits::TriangulationTraits | ( |  | ) |

The default constructor (optional).

This is not required when an instance of the traits is provided to the constructor of `CGAL::Triangulation`.