|
CGAL 4.14 - dD Triangulations
|
|
CGAL 4.14 - dD Triangulations
|
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_>.
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.
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 (optional). More... | |
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 |
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.
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.
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.
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.
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.
| TriangulationTraits::TriangulationTraits | ( | ) |
The default constructor (optional).
This is not required when an instance of the traits is provided to the constructor of CGAL::Triangulation.
1.8.13