CGAL 4.7 - 2D Triangulation: CGAL::Constrained_triangulation_plus_2< Tr > Class Template Reference

\( \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.7 - 2D Triangulation

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
List of all members | Classes
CGAL::Constrained_triangulation_plus_2< Tr > Class Template Reference
Triangulation Classes

`#include <CGAL/Constrained_triangulation_plus_2.h>`

## Inherits from

Tr.

## Definition

The class `Constrained_triangulation_plus_2<Tr>` provides a constrained triangulation with an additional data structure that keeps track of the input constraints and of their refinement in the triangulation.

The class `Constrained_triangulation_plus_2<Tr>` inherits from its template parameter Tr, which has to be instantiated by a constrained or constrained Delaunay triangulation. The intersection tag of the base class determines whether intersecting input constraints are supported or not. When intersections of input constraints are supported, the base class constructs a triangulation of the arrangement of the constraints, introducing new vertices at each proper intersection point.

The data structure maintains for each input constraint the sequence of vertices on this constraint. These vertices are either vertices of the input constraint or intersection points.

The triangulation also enables the retrieval of the set of subconstraints of the triangulation (not ordered along constraints). It further enables the retrieval of the set of input constraints that induce a subconstraint,. As it is straightforward to obtain a subconstraint from a constrained edge `e`, one can obtain the input constraints which induce `e`.

Template Parameters

  Tr | must be either a CGAL::Constrained_triangulation_2 or a CGAL::Constrained_Delaunay_triangulation_2

See Also
  `CGAL::Constrained_triangulation_2<Traits,Tds>`
  `CGAL::Constrained_Delaunay_triangulation_2<Traits,Tds>`
  `ConstrainedTriangulationTraits_2`
  `ConstrainedDelaunayTriangulationTraits_2`

Examples:
  Triangulation_2/constrained_hierarchy_plus.cpp, Triangulation_2/constrained_plus.cpp, and Triangulation_2/polylines_triangulation.cpp.

## Classes

class | Context
| A context enables the access to the vertices of a constraint that pass through a subconstraint. More...

## Types

typedef Tr | Triangulation
| The triangulation base class.
typedef Tr::Intersection_tag | Intersection_tag
| The intersection tag as defined in `Tr`.
typedef unspecified_type | Constraint_id
| The identifier of a polyline constraint. More...
typedef unspecified_type | Constraint_iterator
| An iterator to visit all the input constraints. More...
typedef std::pair < Vertex_handle, Vertex_handle > | Subconstraint
| A subconstraint is a pair of vertices that correspond to an `Edge`. More...
typedef unspecified_type | Subconstraint_iterator
| An iterator to visit all the subconstraints of the triangulation. More...
typedef unspecified_type | Vertices_in_constraint_iterator
| An iterator on the vertices of the chain of subconstraints representing a constraint. More...
typedef unspecified_type | Context_iterator
| An iterator on constraints enclosing a given subconstraint. More...

## Creation

| Constrained_triangulation_plus_2 (const Geom_traits &gt=Geom_traits())
| Introduces an empty triangulation.
| Constrained_triangulation_plus_2 (const Constrained_triangulation_plus_2 &ct)
| Copy constructor.
template<class ConstraintIterator >
| Constrained_triangulation_plus_2 (ConstraintIterator first, ConstraintIterator last, const Geom_traits &gt=Geom_traits())
| Introduces a constrained triangulation from the constraints in the range `[first,last)`. More...

## Assignment

Constrained_triangulation_plus_2 | operator= (const Constrained_triangulation_plus_2 &tr)
| Assignment. More...
void | swap (Constrained_triangulation_plus_2 tr)
| The triangulations `tr` and this triangulation are swapped. More...

## Insertion and Removal

The class `Constrained_triangulation_plus_2` overwrites the following insertion and removal member functions for points and constraints.
Vertex_handle | insert (const Point &p, Face_handle start=Face_handle())
| Inserts point `p` as a vertex of the triangulation.
Vertex_handle | insert (const Point &p, Locate_type lt, Face_handle loc, int li)
| Inserts point `p` in the triangulation at the location given by `(lt,loc,i)`. More...
Vertex_handle | push_back (const Point &p)
| Equivalent to `insert(p)`.
template<class PointIterator >
size_type | insert (PointIterator first, PointIterator last)
| Inserts the points in the range `[first,last)`. More...
Constraint_id | insert_constraint (Point a, Point b)
| Inserts the constraint segment `ab` in the triangulation. More...
void | push_back (const std::pair< Point, Point > &c)
| Inserts the constraint `c`.
Constraint_id | insert_constraint (Vertex_handle va, Vertex_handle vb)
| Inserts a constraint whose endpoints are the vertices pointed by `va` and `vb` in the triangulation. More...
template<class PointIterator >
Constraint_id | insert_constraint (PointIterator first, PointIterator last, bool close=false)
| Inserts a polyline defined by the points in the range `[first,last)` and returns the constraint id. More...
template<class ConstraintIterator >
std::size_t | insert_constraints (ConstraintIterator first, ConstraintIterator last)
| inserts the constraints in the range `[first,last)`. More...
template<class PointIterator , class IndicesIterator >
std::size_t | insert_constraints (PointIterator points_first, PointIterator points_last, IndicesIterator indices_first, IndicesIterator indices_last)
| Same as above except that each constraint is given as a pair of indices of the points in the range [points_first, points_last). More...
void | remove_constraint (Constraint_id cid)
| Removes the constraint `cid`, without removing the points from the triangulation.

## Access

Constraint_iterator | constraints_begin () const
| Returns a `Constraint_iterator` that points at the first constraint of the triangulation.
Constraint_iterator | constraints_end () const
| Returns the past-the-end iterator of the constraints of the triangulation.
Subconstraint_iterator | subconstraints_begin () const
| Returns a `Subconstraint_iterator` pointing at the first subconstraint of the triangulation.
Subconstraint_iterator | subconstraints_end () const
| Returns the past-the-end iterator of the subconstraints of the triangulation.
int | number_of_enclosing_constraints (Vertex_handle va, Vertex_handle vb) const
| Returns the number of constraints enclosing the subconstraint `(va,vb)`. More...
Context | context (Vertex_handle va, Vertex_handle vb) const
| Returns the `Context` relative to one of the constraints enclosing the subconstraint `(va,vb)`. More...
Context_iterator | contexts_begin (Vertex_handle va, Vertex_handle vb) const
| Returns an iterator pointing at the first `Context` of the sequence of contexts corresponding to the constraints enclosing the subconstraint `(va,vb)`. More...
Context_iterator | contexts_end (Vertex_handle va, Vertex_handle vb) const
| Returns an iterator past the end `Context` of the sequence of contexts corresponding to the constraints enclosing the subconstraint `(va,vb)`. More...
Vertices_in_constraint_iterator | vertices_in_constraint_begin (Constraint_id cid) const
| Returns an iterator on the first vertex on the constraint `cid`.
Vertices_in_constraint_iterator | vertices_in_constraint_end (Constraint_id cid) const
| Returns an iterator past the last vertex on the constraint `cid`.
Vertices_in_constraint_iterator | vertices_in_constraint_begin (Vertex_handle va, Vertex_handle vb) const
Vertices_in_constraint_iterator | vertices_in_constraint_end (Vertex_handle va, Vertex_handle vb) const

## Polyline Simplification

Advanced

The polyline simplification algorithm described in Chapter Chapter_2D_Polyline_simplification operates on polyline constraints.

The algorithm removes in each simplification step a vertex of a constraint and at the same time from the triangulation. The class `Constrained_triangulation_plus_2` stores for each constraint not only the sequence of vertices but also the original sequence of points at those vertices. As the `Vertices_in_constraint_iterator` enables the traversal of the current set of vertices, the `Points_in_constraint_iterator` enables the traversal of the points that were in the constraint before the simplification algorithm started.

It enables the simplification algorithm to compute the error introduced by each simplification step: it is the distance of the current sequence (vertices) to the original sequence (points).

Those stored points which do not correspond to a vertex can be removed afterward either for a single constraint or for all constraints.

The simplification algorithm uses the following types and functions.

typedef unspecified_type | Points_in_constraint_iterator
| Advanced An iterator on the points of the of the original constraint before simplification steps are applied. More...
Points_in_constraint_iterator | points_in_constraint_begin (Constraint_id cid) const
| Advanced Returns an iterator to the first point on the constraint before any simplification step. More...
Points_in_constraint_iterator | points_in_constraint_end (Constraint_id cid) const
| Advanced Returns an iterator past the last point on the constraint before any simplification step. More...
void | simplify (Vertices_in_constraint_iterator vicq)
| Advanced Removes the vertex at `vicq` from the constraint and the triangulation. More...
size_type | remove_points_without_corresponding_vertex (Constraint_id cid)
| Advanced Removes the original points that correspond to vertices in the constraint `cid` which have been removed by the `simplify()` function. More...
void | remove_points_without_corresponding_vertex ()
| Advanced Removes all original points that correspond to vertices in the constraints which have been removed by the `simplify()` function. More...

## Member Typedef Documentation

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Constraint_id

The identifier of a polyline constraint.

The class is model of `Assignable`, `CopyConstructible`, `DefaultConstructible`, `LessThanComparable` and `EqualityComparable`.

A default constructed `Constraint_id` is a singular value that can not be the ID of a constraint.

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Constraint_iterator

An iterator to visit all the input constraints.

The order of visit is undefined. The value type of this iterator is `Constraint_id`.

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Context_iterator

An iterator on constraints enclosing a given subconstraint.

The value type of this iterator is `Context`.

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Points_in_constraint_iterator

Advanced
An iterator on the points of the of the original constraint before simplification steps are applied.

The value type of this iterator is `Point`. A `Vertices_in_constraint_iterator` can be converted into a `Points_in_constraint_iterator`, but not the other way around.

template<typename Tr >

typedef std::pair<Vertex_handle, Vertex_handle> CGAL::Constrained_triangulation_plus_2< Tr >::Subconstraint

A subconstraint is a pair of vertices that correspond to an `Edge`.

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Subconstraint_iterator

An iterator to visit all the subconstraints of the triangulation.

The order of visit is undefined. The value type of this iterator is `Subconstraint` corresponding to the vertices of the subconstraint.

template<typename Tr >

typedef unspecified_type CGAL::Constrained_triangulation_plus_2< Tr >::Vertices_in_constraint_iterator

An iterator on the vertices of the chain of subconstraints representing a constraint.

The value type of this iterator is `Vertex_handle`.

## Constructor & Destructor Documentation

template<typename Tr >
template<class ConstraintIterator >

CGAL::Constrained_triangulation_plus_2< Tr >::Constrained_triangulation_plus_2 | ( | ConstraintIterator | first,
|  | ConstraintIterator | last,
|  | const Geom_traits & | gt = `Geom_traits()`
| ) |  |

Introduces a constrained triangulation from the constraints in the range `[first,last)`.

Template Parameters

  ConstraintIterator | must be an `InputIterator` with the value type `std::pair<Point,Point>` or `Segment`.

## Member Function Documentation

template<typename Tr >

Context CGAL::Constrained_triangulation_plus_2< Tr >::context | ( | Vertex_handle | va,
|  | Vertex_handle | vb
| ) |  | const

Returns the `Context` relative to one of the constraints enclosing the subconstraint `(va,vb)`.

Precondition
  `va` and `vb` refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Context_iterator CGAL::Constrained_triangulation_plus_2< Tr >::contexts_begin | ( | Vertex_handle | va,
|  | Vertex_handle | vb
| ) |  | const

Returns an iterator pointing at the first `Context` of the sequence of contexts corresponding to the constraints enclosing the subconstraint `(va,vb)`.

Precondition
  `va` and `vb` refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Context_iterator CGAL::Constrained_triangulation_plus_2< Tr >::contexts_end | ( | Vertex_handle | va,
|  | Vertex_handle | vb
| ) |  | const

Returns an iterator past the end `Context` of the sequence of contexts corresponding to the constraints enclosing the subconstraint `(va,vb)`.

Precondition
  `va` and `vb` refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Vertex_handle CGAL::Constrained_triangulation_plus_2< Tr >::insert | ( | const Point & | p,
|  | Locate_type | lt,
|  | Face_handle | loc,
|  | int | li
| ) |  |

Inserts point `p` in the triangulation at the location given by `(lt,loc,i)`.

See Also
  `Triangulation_2::locate()`

template<typename Tr >
template<class PointIterator >

size_type CGAL::Constrained_triangulation_plus_2< Tr >::insert | ( | PointIterator | first,
|  | PointIterator | last
| ) |  |

Inserts the points in the range `[first,last)`.

Returns the number of inserted points.

Template Parameters

  PointIterator | must be an `InputIterator` with the value type `Point`.

template<typename Tr >

Constraint_id CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraint | ( | Point | a,
|  | Point | b
| ) |  |

Inserts the constraint segment `ab` in the triangulation.

If the two points are equal the point is inserted but no constraint, and the default constructed `Constraint_id` is returned.

Examples:
  Triangulation_2/constrained_hierarchy_plus.cpp, and Triangulation_2/constrained_plus.cpp.

template<typename Tr >

Constraint_id CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraint | ( | Vertex_handle | va,
|  | Vertex_handle | vb
| ) |  |

Inserts a constraint whose endpoints are the vertices pointed by `va` and `vb` in the triangulation.

If the two vertex handles are equal no constraint is inserted, and the default constructed `Constraint_id` is returned.

template<typename Tr >
template<class PointIterator >

Constraint_id CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraint | ( | PointIterator | first,
|  | PointIterator | last,
|  | bool | close = `false`
| ) |  |

Inserts a polyline defined by the points in the range `[first,last)` and returns the constraint id.

The polyline is considered as a closed curve if the first and last point are equal or if `close == true`. This enables for example passing the vertex range of a `Polygon_2`. When traversing the vertices of a closed polyline constraint with a `Vertices_in_constraint_iterator` the first and last vertex are the same. In case the range is empty `Constraint_id()`is returned. In case all points are equal the point is inserted but no constraint, and `Constraint_id()`is returned.

Template Parameters

  PointIterator | must be an `InputIterator` with the value type `Point`.

template<typename Tr >
template<class ConstraintIterator >

std::size_t CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraints | ( | ConstraintIterator | first,
|  | ConstraintIterator | last
| ) |  |

inserts the constraints in the range `[first,last)`.

Note that this function is not guaranteed to insert the constraints following the order of `ConstraintIterator`, as `spatial_sort()` is used to improve efficiency. More precisely, all endpoints are inserted prior to the segments and according to the order provided by the spatial sort. Once endpoints have been inserted, the segments are inserted in the order of the input iterator, using the vertex handles of its endpoints.

Returns
  the number of inserted points.

Template Parameters

  ConstraintIterator | must be an `InputIterator` with the value type `std::pair<Point,Point>` or `Segment`.

template<typename Tr >
template<class PointIterator , class IndicesIterator >

std::size_t CGAL::Constrained_triangulation_plus_2< Tr >::insert_constraints | ( | PointIterator | points_first,
|  | PointIterator | points_last,
|  | IndicesIterator | indices_first,
|  | IndicesIterator | indices_last
| ) |  |

Same as above except that each constraint is given as a pair of indices of the points in the range [points_first, points_last).

The indices must go from 0 to `std::distance(points_first, points_last)`

Template Parameters

  PointIterator | is an `InputIterator` with the value type `Point`.
  IndicesIterator | is an `InputIterator` with `std::pair<Int, Int>` where `Int` is an integral type implicitly convertible to `std::size_t`

template<typename Tr >

int CGAL::Constrained_triangulation_plus_2< Tr >::number_of_enclosing_constraints | ( | Vertex_handle | va,
|  | Vertex_handle | vb
| ) |  | const

Returns the number of constraints enclosing the subconstraint `(va,vb)`.

Precondition
  `va` and `vb` refer to the vertices of a constrained edge of the triangulation.

template<typename Tr >

Constrained_triangulation_plus_2 CGAL::Constrained_triangulation_plus_2< Tr >::operator= | ( | const Constrained_triangulation_plus_2< Tr > & | tr) |  |

Assignment.

All the vertices and faces are duplicated. The bidirectional mapping between constraints and subconstraints is also duplicated.

template<typename Tr >

Points_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::points_in_constraint_begin | ( | Constraint_id | cid) |  | const

Advanced
Returns an iterator to the first point on the constraint before any simplification step.
template<typename Tr >

Points_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::points_in_constraint_end | ( | Constraint_id | cid) |  | const

Advanced
Returns an iterator past the last point on the constraint before any simplification step.
template<typename Tr >

size_type CGAL::Constrained_triangulation_plus_2< Tr >::remove_points_without_corresponding_vertex | ( | Constraint_id | cid) |  |

Advanced
Removes the original points that correspond to vertices in the constraint `cid` which have been removed by the `simplify()` function.
template<typename Tr >

void CGAL::Constrained_triangulation_plus_2< Tr >::remove_points_without_corresponding_vertex | ( | ) |  |

Advanced
Removes all original points that correspond to vertices in the constraints which have been removed by the `simplify()` function.
template<typename Tr >

void CGAL::Constrained_triangulation_plus_2< Tr >::simplify | ( | Vertices_in_constraint_iterator | vicq) |  |

Advanced
Removes the vertex at `vicq` from the constraint and the triangulation.

The point of that vertex remains stored in the sequence of original points of the constraint until `remove_points_without_corresponding_vertex(Constraint_id)` or `remove_points_without_corresponding_vertex()` is called.

The polyline simplification algorithm described in Chapter Chapter_2D_Polyline_simplification operates on polyline constraints and applies `simplify()` to vertices in constraints based on a cost and stop function.

Precondition
  Each vertex of the triangulation must be either a vertex of a constraint or a vertex at the intersection of constraints.
  `vicq` must neither be the first nor the last vertex on a constraint.
  The vertex referred by vicq is not contained in any other constraint.
  Let `vip` and `vir` be defined as `vip = std::prev(vicq)` and `vir = std::next(vicr)`.
  The line segment between `*vicp->point()` and `*vicr->point()` must not intersect any constraint.

template<typename Tr >

void CGAL::Constrained_triangulation_plus_2< Tr >::swap | ( | Constrained_triangulation_plus_2< Tr > | tr) |  |

The triangulations `tr` and this triangulation are swapped.

This operation should be preferred to the assignment or to the copy constructor if `tr` is deleted after that.

template<typename Tr >

Vertices_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::vertices_in_constraint_begin | ( | Vertex_handle | va,
|  | Vertex_handle | vb
| ) |  | const

Deprecated:
  Returns an iterator on the first vertex on the constraint `cid`.

Attention
  This function only works for constraints that were inserted as a pair of points or pair of vertex handles.

template<typename Tr >

Vertices_in_constraint_iterator CGAL::Constrained_triangulation_plus_2< Tr >::vertices_in_constraint_end | ( | Vertex_handle | va,
|  | Vertex_handle | vb
| ) |  | const

Deprecated:
  Returns an iterator past the last vertex on the constraint `cid`.

Attention
  This function only works for constraints that were inserted as a pair of points or pair of vertex handles.