CGAL 6.2 - 2D Triangulations

Loading...
Searching...
No Matches
List of all members
CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag > Class Template Reference
Reference Manual » Triangulation Classes

`#include <CGAL/Constrained_Delaunay_triangulation_2.h>`

## Inherits from

CGAL::Constrained_triangulation_2< Traits, Tds, Itag >.

## Definition

template<typename Traits, typename Tds, typename Itag>
class CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >

A constrained Delaunay triangulation is a triangulation with constrained edges which tries to be as much Delaunay as possible.

Constrained edges are not necessarily Delaunay edges, therefore a constrained Delaunay triangulation is not a Delaunay triangulation. A constrained Delaunay is a triangulation whose faces do not necessarily fulfill the empty circle property but fulfill a weaker property called the constrained empty circle. To state this property, it is convenient to think of constrained edges as blocking the view. Then, a triangulation is constrained Delaunay if the circumscribing circle of any of its triangular faces includes in its interior no vertex that is visible from the interior of the triangle.

As in the case of constrained triangulations, three different versions of Delaunay constrained triangulations are offered depending on whether the user wishes to handle intersecting input constraints or not.

Template Parameters

  Traits | is the geometric traits of a constrained Delaunay triangulation. It must be a model of `DelaunayTriangulationTraits_2`, providing the `side_of_oriented_circle` test of a Delaunay triangulation. When intersection of input constraints are supported, the geometric traits class is required to provide additional function object types to compute the intersection of two segments. and has then to be also a model of the concept `ConstrainedTriangulationTraits_2`.
  Tds | must be a model of `TriangulationDataStructure_2` or `Default`.
  Itag | allows to select if intersecting constraints are supported and how they are handled. `No_constraint_intersection_tag` if intersections of input constraints are disallowed, except for the configuration of a single common extremity; `No_constraint_intersection_requiring_constructions_tag` if intersections of input constraints are disallowed, except if no actual construction is needed to represent the intersection. For example, if two constraints intersect in a 'T'-like junction, the intersection point is one of the constraints' extremity and as such, no construction is in fact needed. Other similar configurations include overlapping segments, common extremities, or equal constraints. `Exact_predicates_tag` allows intersections between input constraints and is to be used when the traits class provides exact predicates but approximate constructions of the intersection points; `Exact_intersections_tag` allows intersections between input constraints and is to be used in conjunction with an exact arithmetic type.

A constrained Delaunay triangulation is not a Delaunay triangulation but it is a constrained triangulation. Therefore the class `Constrained_Delaunay_triangulation_2` derives from the class `Constrained_triangulation_2<Traits,Tds>`. Also, information about the status (constrained or not) of the edges of the triangulation is stored in the faces. Thus the nested `Face` type of a constrained triangulation offers additional functionalities to deal with this information. These additional functionalities induce additional requirements on the base face class plugged into the triangulation data structure of a constrained Delaunay triangulation. The base face of a constrained Delaunay triangulation has to be a model of the concept `ConstrainedTriangulationFaceBase_2`.

CGAL provides a default for the template parameters. If `Gt` is the geometric traits parameter, the default for `ConstrainedTriangulationFaceBase_2` is the class `Constrained_triangulation_face_base_2<Gt>` and the default for the triangulation data structure parameter is the class `Triangulation_data_structure_2< CGAL::Triangulation_vertex_base_2<Gt>, Constrained_triangulation_face_base_2<Gt> >`. The default intersection tag is `No_constraint_intersection_requiring_constructions_tag`.

Types

All types used in this class are inherited from the base class `Constrained_triangulation_2<Traits,Tds,Itag>`.

See also
  `CGAL::Constrained_triangulation_2<Traits,Tds,Itag>`
  `TriangulationDataStructure_2`
  `DelaunayTriangulationTraits_2`
  `ConstrainedTriangulationTraits_2`
  `ConstrainedDelaunayTriangulationTraits_2`
  `ConstrainedTriangulationFaceBase_2`

Examples
  Triangulation_2/constrained.cpp, Triangulation_2/constrained_hierarchy_plus.cpp, Triangulation_2/constrained_plus.cpp, Triangulation_2/polygon_triangulation.cpp, Triangulation_2/polylines_triangulation.cpp, Triangulation_2/segment_soup_to_polylines.cpp, and Triangulation_2/triangulation_projection_traits.cpp.

## Creation
| Constrained_Delaunay_triangulation_2 (const Traits &t=Traits())
| introduces an empty constrained Delaunay triangulation `cdt`.
| Constrained_Delaunay_triangulation_2 (const Constrained_Delaunay_triangulation_2 &cdt1)
| Copy constructor: All faces and vertices are duplicated and the constrained status of edges is copied.
template<class ConstraintIterator >
| Constrained_Delaunay_triangulation_2 (ConstraintIterator first, ConstraintIterator last, const Traits &t=Traits())
| builds a constrained triangulation with constraints in the range `[first,last)` by calling `insert_constraints(first, last)`.

## Insertion and Removal
The following member functions overwrite the corresponding members of the base class to include a step restoring the Delaunay constrained property after modification of the triangulation.
Vertex_handle | insert (Point p, Face_handle f=Face_handle())
| inserts point `p` in the triangulation, with face `f` as a hint for the location of `p`.
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)`.
Vertex_handle | push_back (const Point &p)
| Equivalent to `insert(p)`.
template<class PointIterator >
std::ptrdiff_t | insert (PointIterator first, PointIterator last)
| inserts the points in the range `[first,last)`.
template<class PointWithInfoIterator >
std::ptrdiff_t | insert (PointWithInfoIterator first, PointWithInfoIterator last)
| inserts the points in the iterator range `[first,last)`.
void | insert_constraint (Point a, Point b)
| Inserts the line segment `ab` as a constraint in the triangulation.
void | push_back (const std::pair< Point, Point > &c)
| inserts the line segment between the points `c.first` and `c.second` as a constraint in the triangulation.
void | insert_constraint (Vertex_handle va, Vertex_handle vb)
| inserts the line segment whose endpoints are the vertices `va` and `vb` as a constraint in the triangulation.
template<class PointIterator >
void | insert_constraint (PointIterator first, PointIterator last, bool close=false)
| Inserts a polyline defined by the points in the range `[first,last)`.
template<class ConstraintIterator >
std::size_t | insert_constraints (ConstraintIterator first, ConstraintIterator last)
| inserts the constraints in the range `[first,last)`.
template<class ConstraintIterator >
std::size_t | insert_unique_constraints (ConstraintIterator first, ConstraintIterator last)
| Same as `insert_constraints(begin,end)` except that duplicated pairs of points are only considered once.
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).
template<class PointIterator , class IndicesIterator >
std::size_t | insert_unique_constraints (PointIterator points_first, PointIterator points_last, IndicesIterator indices_first, IndicesIterator indices_last)
| Same as `insert_constraint(points_first, points_last, indices_first, indices_last)` except that duplicated pairs of points are only considered once.
void | remove (Vertex_handle &v)
| removes vertex v.
void | remove_incident_constraints (Vertex_handle v)
| makes the edges incident to vertex `v` unconstrained edges.
void | remove_constraint (const Face_handle &f, int i)
| makes the edge `(f,i)` unconstrained.

## Queries
The following template member functions query the set of faces in conflict with a point `p`. The notion of conflict refers here to a constrained Delaunay setting which means the following. Constrained edges are considered as visibility obstacles and a point `p` is considered to be in conflict with a face `f` iff it is visible from the interior of `f` and included in the circumcircle of `f`.
template<class OutputItFaces , class OutputItBoundaryEdges >
std::pair< OutputItFaces, OutputItBoundaryEdges > | get_conflicts_and_boundary (const Point &p, OutputItFaces fit, OutputItBoundaryEdges eit, Face_handle start) const
| outputs the faces and boundary edges of the conflict zone of point `p` into output iterators.
template<class OutputItFaces >
OutputItFaces | get_conflicts (const Point &p, OutputItFaces fit, Face_handle start) const
| outputs the faces of the conflict zone of point `p` into an output iterator.
template<class OutputItBoundaryEdges >
OutputItBoundaryEdges | get_boundary_of_conflicts (const Point &p, OutputItBoundaryEdges eit, Face_handle start) const
| outputs the boundary edges of the conflict zone of point `p` into an output iterator.

## Checking
bool | is_valid () const
| checks if the triangulation is valid and if each constrained edge is consistently marked constrained in its two incident faces.

## Flips
bool | is_flipable (Face_handle f, int i) const
| determines if edge `(f,i)` can be flipped.
void | flip (Face_handle &f, int i)
| This is an advanced function.
void | propagating_flip (List_edges &edges)
| makes the triangulation constrained Delaunay by flipping edges.

## Additional Inherited Members
Public Types inherited from CGAL::Constrained_triangulation_2< Traits, Tds, Itag >
typedef std::pair< Point, Point > | Constraint
typedef unspecified_type | Constrained_edges_iterator
| A bidirectional iterator to visit all the edges `e` of the triangulation which are constrained.
typedef Iterator_range< Constrained_edges_iterator > | Constrained_edges
| A range type to iterate over the constrained edges.
typedef Itag | Intersection_tag
| The intersection tag which decides how intersections between input constraints are dealt with.
Public Types inherited from CGAL::Triangulation_2< Traits, Tds >
enum | Locate_type { VERTEX =0 , EDGE , FACE , OUTSIDE_CONVEX_HULL , OUTSIDE_AFFINE_HULL }
| specifies which case occurs when locating a point in the triangulation. More...
typedef Tds::Vertex_handle | Vertex_handle
| Handle to a vertex.
typedef Tds::Face_handle | Face_handle
| Handle to a face.
typedef Tds::Face_iterator | All_faces_iterator
| Iterator over all faces.
typedef Tds::Edge_iterator | All_edges_iterator
| Iterator over all edges.
typedef Tds::Vertex_iterator | All_vertices_iterator
| Iterator over all vertices.
typedef unspecified_type | Finite_faces_iterator
| Iterator over finite faces.
typedef unspecified_type | Finite_edges_iterator
| Iterator over finite edges.
typedef unspecified_type | Finite_vertices_iterator
| Iterator over finite vertices.
typedef unspecified_type | Point_iterator
| Iterator over the points corresponding to the finite vertices of the triangulation.
typedef Iterator_range< unspecified_type > | All_face_handles
| Range type for iterating over all faces (including infinite faces), with a nested type `iterator` that has as value type `Face_handle`.
typedef Iterator_range< All_edges_iterator > | All_edges
| Range type for iterating over all edges (including infinite ones).
typedef Iterator_range< unspecified_type > | All_vertex_handles
| Range type for iterating over all vertices (including the infinite vertex), with a nested type `iterator` that has as value type `Vertex_handle`.
typedef Iterator_range< unspecified_type > | Finite_face_handles
| Range type for iterating over finite faces, with a nested type `iterator` that has as value type `Face_handle`.
typedef Iterator_range< Finite_edges_iterator > | Finite_edges
| Range type for iterating over finite edges.
typedef Iterator_range< unspecified_type > | Finite_vertex_handles
| Range type for iterating over finite vertices, with a nested type `iterator` that has as value type `Vertex_handle`.
typedef Iterator_range< Point_iterator > | Points
| Range type for iterating over the points of the finite vertices.
typedef unspecified_type | Line_face_circulator
| Circulator over all faces intersected by a line.
typedef unspecified_type | Face_circulator
| Circulator over all faces incident to a given vertex.
typedef unspecified_type | Edge_circulator
| Circulator over all edges incident to a given vertex.
typedef unspecified_type | Vertex_circulator
| Circulator over all vertices incident to a given vertex.
typedef Traits | Geom_traits
| The traits class.
typedef Tds | Triangulation_data_structure
| The triangulation data structure type.
typedef Traits::Point_2 | Point
| The point type.
typedef Traits::Segment_2 | Segment
| The segment type.
typedef Traits::Triangle_2 | Triangle
| The triangle type.
typedef Tds::Vertex | Vertex
| The vertex type.
typedef Tds::Face | Face
| The face type.
typedef Tds::Edge | Edge
| The edge type.
typedef Tds::size_type | size_type
| Size type (an unsigned integral type).
typedef Tds::difference_type | difference_type
| Difference type (a signed integral type).
Public Member Functions inherited from CGAL::Constrained_triangulation_2< Traits, Tds, Itag >
| Constrained_triangulation_2 ()
| Default constructor.
| Constrained_triangulation_2 (const Constrained_triangulation_2 &ct1)
| Copy constructor: All faces and vertices are duplicated and the constrained status of edges is copied.
bool | is_constrained (Edge e) const
| returns `true` if edge `e` is a constrained edge.
bool | are_there_incident_constraints (Vertex_handle v) const
| returns `true` if at least one of the edges incident to vertex `v` is constrained.
template<class OutputItEdges >
OutputItEdges | incident_constraints (Vertex_handle v, OutputItEdges out) const
| outputs the constrained edges incident to `v` into the output iterator `out` and returns the resulting output iterator.
Constrained_edges_iterator | constrained_edges_begin () const
| returns an iterator that enumerates the constrained edges.
Constrained_edges_iterator | constrained_edges_end () const
| returns the past-the-end iterator.
Constrained_edges | constrained_edges () const
| returns a range of constrained edges.
Vertex_handle | insert (Point p, Face_handle f=Face_handle())
| inserts point `p` and restores the status (constrained or not) of all the touched edges.
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)`.
Vertex_handle | push_back (const Point &p)
| Equivalent to `insert(p)`.
void | insert_constraint (Point a, Point b)
| inserts points `a` and `b` in this order, and inserts the line segment `ab` as a constraint.
void | push_back (const std::pair< Point, Point > &c)
| Equivalent to `insert(c.first, c.second)`.
void | insert_constraint (const Vertex_handle &va, const Vertex_handle &vb)
| inserts the line segment `s` whose endpoints are the vertices `va` and `vb` as a constraint.
template<class PointIterator >
void | insert_constraint (PointIterator first, PointIterator last, bool close=false)
| inserts a polyline defined by the points in the range `[first,last)`.
void | remove (Vertex_handle v)
| removes a vertex `v`.
void | remove_incident_constraints (Vertex_handle v)
| makes the edges incident to vertex `v` unconstrained edges.
void | remove_constrained_edge (Face_handle f, int i)
| makes edge `(f,i)` unconstrained.
bool | is_valid (bool verbose=false, int level=0) const
| checks the validity of the triangulation and the consistency of the constrained marks in edges.
Public Member Functions inherited from CGAL::Triangulation_2< Traits, Tds >
| Triangulation_2 (const Traits &gt=Traits())
| introduces an empty triangulation.
| Triangulation_2 (const Triangulation_2 &tr)
| Copy constructor.
template<class InputIterator >
| Triangulation_2 (InputIterator first, InputIterator last, const Traits &gt=Traits())
| Equivalent to constructing an empty triangulation with the optional traits class argument and calling insert(first,last).
Triangulation_2 | operator= (const Triangulation_2< Traits, Tds > &tr)
| Assignment.
void | swap (Triangulation_2 &tr)
| The triangulations `tr` and `*this` are swapped.
void | clear ()
| deletes all faces and finite vertices resulting in an empty triangulation.
int | dimension () const
| returns the dimension of the convex hull.
size_type | number_of_vertices () const
| returns the number of finite vertices.
size_type | number_of_faces () const
| returns the number of finite faces.
Face_handle | infinite_face () const
| returns a face incident to the infinite vertex.
Vertex_handle | infinite_vertex () const
| returns the infinite vertex.
Vertex_handle | finite_vertex () const
| returns a vertex distinct from the infinite vertex.
const Geom_traits & | geom_traits () const
| returns a const reference to the triangulation traits object.
const TriangulationDataStructure_2 & | tds () const
| returns a const reference to the triangulation data structure.
TriangulationDataStructure_2 & | tds ()
| returns a reference to the triangulation data structure.
bool | is_infinite (Vertex_handle v) const
| returns `true` iff `v` is the infinite vertex.
bool | is_infinite (Face_handle f) const
| returns `true` iff face `f` is infinite.
bool | is_infinite (Face_handle f, int i) const
| returns `true` iff edge `(f,i)` is infinite.
bool | is_infinite (Edge e) const
| returns `true` iff edge `e` is infinite.
bool | is_infinite (Edge_circulator ec) const
| returns `true` iff edge `*ec` is infinite.
bool | is_infinite (All_edges_iterator ei) const
| returns `true` iff edge `*ei` is infinite.
bool | is_vertex (Vertex_handle v) const
| returns `true` if `v` is a vertex of the triangulation.
bool | is_edge (Vertex_handle va, Vertex_handle vb)
| returns `true` if there is an edge having `va` and `vb` as vertices.
bool | is_edge (Vertex_handle va, Vertex_handle vb, Face_handle &fr, int &i)
| As above.
bool | includes_edge (Vertex_handle va, Vertex_handle vb, Vertex_handle &vbb, Face_handle &fr, int &i)
| returns `true` if the line segment from `va` to `vb` includes an edge `e` incident to `va`.
bool | is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3)
| returns `true` if there is a face having `v1`, `v2` and `v3` as vertices.
bool | is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3, Face_handle &fr)
| As above.
Face_handle | locate (const Point &query, Face_handle f=Face_handle()) const
| If the point `query` lies inside the convex hull of the points, a face that contains the query in its interior or on its boundary is returned.
Face_handle | inexact_locate (const Point &query, Face_handle start=Face_handle()) const
| Same as `locate()` but uses inexact predicates.
Face_handle | locate (const Point &query, Locate_type &lt, int &li, Face_handle h=Face_handle()) const
| Same as above.
Oriented_side | oriented_side (Face_handle f, const Point &p) const
| returns on which side of the oriented boundary of `f` lies the point `p`.
Oriented_side | side_of_oriented_circle (Face_handle f, const Point &p)
| returns on which side of the circumcircle of face `f` lies the point `p`.
void | flip (Face_handle f, int i)
| exchanges the edge incident to `f` and `f->neighbor(i)` with the other diagonal of the quadrilateral formed by `f` and `f->neighbor(i)`.
Vertex_handle | insert (const Point &p, Face_handle f=Face_handle())
| inserts point `p` in the triangulation and returns the corresponding vertex.
Vertex_handle | insert (const Point &p, Locate_type lt, Face_handle loc, int li)
| Same as above except that the location of the point `p` to be inserted is assumed to be given by `(lt,loc,i)` (see the description of the `locate` method above.)
Vertex_handle | push_back (const Point &p)
| Equivalent to `insert(p)`.
template<class PointInputIterator >
std::ptrdiff_t | insert (PointInputIterator first, PointInputIterator last)
| inserts the points in the range `[first,last)` in the given order, and returns the number of inserted points.
template<class PointWithInfoInputIterator >
std::ptrdiff_t | insert (PointWithInfoInputIterator first, PointWithInfoInputIterator last)
| inserts the points in the iterator range `[first,last)` in the given order, and returns the number of inserted points.
void | remove (Vertex_handle v)
| removes the vertex from the triangulation.
Vertex_handle | move_if_no_collision (Vertex_handle v, const Point &p)
| If there is not already another vertex placed on `p`, the triangulation is modified such that the new position of vertex `v` is `p`, and `v` is returned.
Vertex_handle | move (Vertex_handle v, const Point &p)
| If there is no collision during the move, this function is the same as `move_if_no_collision` .
Vertex_handle | insert_first (const Point &p)
| inserts the first finite vertex .
Vertex_handle | insert_second (const Point &p)
| inserts the second finite vertex .
Vertex_handle | insert_in_face (const Point &p, Face_handle f)
| inserts vertex `v` in face `f`.
Vertex_handle | insert_in_edge (const Point &p, Face_handle f, int i)
| inserts vertex v in edge `i` of `f`.
Vertex_handle | insert_outside_convex_hull (const Point &p, Face_handle f)
| inserts a point which is outside the convex hull but in the affine hull.
Vertex_handle | insert_outside_affine_hull (const Point &p)
| Inserts a point which is outside the affine hull.
void | remove_degree_3 (Vertex_handle v)
| Removes a vertex of degree three.
void | remove_second (Vertex_handle v)
| removes the before last finite vertex.
void | remove_first (Vertex_handle v)
| removes the last finite vertex.
template<class EdgeIt >
Vertex_handle | star_hole (Point p, EdgeIt edge_begin, EdgeIt edge_end)
| creates a new vertex `v` and use it to star the hole whose boundary is described by the sequence of edges `[edge_begin, edge_end)`.
template<class EdgeIt , class FaceIt >
Vertex_handle | star_hole (Point p, EdgeIt edge_begin, EdgeIt edge_end, FaceIt face_begin, FaceIt face_end)
| Same as above, except that the algorithm first recycles faces in the sequence `[face_begin, face_end)` and create new ones only when the sequence is exhausted.
Finite_vertices_iterator | finite_vertices_begin () const
| returns an iterator over finite vertices of the triangulation.
Finite_vertices_iterator | finite_vertices_end () const
| Past-the-end iterator.
Finite_edges_iterator | finite_edges_begin () const
| returns an iterator over finite edges of the triangulation.
Finite_edges_iterator | finite_edges_end () const
| Past-the-end iterator.
Finite_faces_iterator | finite_faces_begin () const
| returns an iterator over finite faces of the triangulation.
Finite_faces_iterator | finite_faces_end () const
| Past-the-end iterator.
Point_iterator | points_begin () const
Point_iterator | points_end () const
| Past-the-end iterator.
Finite_vertex_handles | finite_vertex_handles () const
| returns a range of iterators over finite vertices.
Finite_edges | finite_edges () const
| returns a range of iterators over finite edges.
Finite_face_handles | finite_face_handles () const
| returns a range of iterators over finite faces.
Points | points () const
| returns a range of iterators over the points of finite vertices.
All_vertices_iterator | all_vertices_begin () const
| returns an iterator over all vertices of the triangulation.
All_vertices_iterator | all_vertices_end () const
| Past-the-end iterator.
All_edges_iterator | all_edges_begin () const
| returns an iterator over all edges of the triangulation.
All_edges_iterator | all_edges_end () const
| Past-the-end iterator.
All_faces_iterator | all_faces_begin () const
| returns an iterator over all faces of the triangulation.
All_faces_iterator | all_faces_end () const
| Past-the-end iterator.
All_vertex_handles | all_vertex_handles () const
| returns a range of iterators over all vertices.
All_edges | all_edges () const
| returns a range of iterators over all edges.
All_face_handles | all_face_handles () const
| returns a range of iterators over all faces.
Line_face_circulator | line_walk (const Point &p, const Point &q, Face_handle f=Face_handle()) const
| This function returns a circulator that allows to visit the faces intersected by the line `pq`.
Face_circulator | incident_faces (Vertex_handle v) const
| returns a circulator over the faces incident to `v`.
Face_circulator | incident_faces (Vertex_handle v, Face_handle f) const
| returns a circulator over the faces incident to `v`.
Edge_circulator | incident_edges (Vertex_handle v) const
| returns a circulator over the edges incident to `v`.
Edge_circulator | incident_edges (Vertex_handle v, Face_handle f) const
| returns a circulator over the edges incident to `v`.
Vertex_circulator | incident_vertices (Vertex_handle v) const
| returns a circulator over the vertices adjacent to `v`.
Vertex_circulator | incident_vertices (Vertex_handle v, Face_handle f)
| returns a circulator over the vertices adjacent to `v`.
size_type | degree (Vertex_handle v) const
| returns the degree of `v`, that is, the number of incident vertices.
Vertex_handle | mirror_vertex (Face_handle f, int i) const
| returns the vertex of the \( i^{th}\) neighbor of `f` that is opposite to `f`.
int | mirror_index (Face_handle f, int i) const
| returns the index of `f` in its \( i^{th}\) neighbor.
Edge | mirror_edge (Edge e) const
| returns the same edge seen from the other adjacent face.
int | ccw (int i) const
| returns \( i+1\) modulo 3.
int | cw (int i) const
| returns \( i+2\) modulo 3.
Triangle | triangle (Face_handle f) const
| returns the triangle formed by the three vertices of `f`.
Segment | segment (Face_handle f, int i) const
| returns the line segment formed by the vertices `ccw(i)` and `cw(i)` of face `f`.
Segment | segment (const Edge &e) const
| returns the line segment corresponding to edge `e`.
Segment | segment (const Edge_circulator &ec) const
| returns the line segment corresponding to edge `*ec`.
Segment | segment (const Edge_iterator &ei) const
| returns the line segment corresponding to edge `*ei`.
const Point & | point (Face_handle f, int i) const
| returns the point given by vertex `i` of face `f`.
const Point & | point (Vertex_handle v) const
| Same as the previous method for vertex `v`.
Point | circumcenter (Face_handle f) const
| computes the circumcenter of the face pointed to by f.
void | set_infinite_vertex (const Vertex_handle &v)
| This is an advanced function.
bool | is_valid (bool verbose=false, int level=0) const
| checks the combinatorial validity of the triangulation and also the validity of its geometric embedding.
Public Member Functions inherited from CGAL::Triangulation_cw_ccw_2
| Triangulation_cw_ccw_2 ()
| Default constructor.
int | ccw (const int i) const
| returns the index of the neighbor or vertex that is next to the neighbor or vertex with index `i` in counterclockwise order around a face.
int | cw (const int i) const
| returns the index of the neighbor or vertex that is next to the neighbor or vertex with index `i` in counterclockwise order around a face.
Related Functions inherited from CGAL::Constrained_triangulation_2< Traits, Tds, Itag >
template<typename Traits , typename Tds , typename Itag >
std::ostream & | operator<< (std::ostream &os, const Constrained_triangulation_2< Traits, Tds, Itag > &ct)
| writes the triangulation as for `Triangulation_2<Traits,Tds>` and, for each face `f`, and integers `i=0,1,2`, writes "C" or "N" depending whether edge `(f,i)` is constrained or not.
template<typename Traits , typename Tds , typename Itag >
std::istream & | operator>> (std::istream &is, Constrained_triangulation_2< Traits, Tds, Itag > Ct &ct)
| reads a triangulation from stream `is` and assigns it to c`t`.
Related Functions inherited from CGAL::Triangulation_2< Traits, Tds >
ostream & | operator<< (ostream &os, const Triangulation_2< Traits, Tds > &T)
| inserts the triangulation into the stream `os`.
istream & | operator>> (istream &is, const Triangulation_2< Traits, Tds > &T)
| reads a triangulation from stream `is` and assigns it to the triangulation.

## Constructor & Destructor Documentation

## ◆ Constrained_Delaunay_triangulation_2()

template<typename Traits , typename Tds , typename Itag >
template<class ConstraintIterator >

CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::Constrained_Delaunay_triangulation_2 | ( | ConstraintIterator | first,
|  | ConstraintIterator | last,
|  | const Traits & | t = `Traits()`
| ) |  |

builds a constrained triangulation with constraints in the range `[first,last)` by calling `insert_constraints(first, last)`.

Template Parameters

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

## Member Function Documentation

## ◆ flip()

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::flip | ( | Face_handle & | f,
|  | int | i
| ) |  |

This is an advanced function.

Advanced

Flip `f` and `f->neighbor(i)`.

## ◆ get_boundary_of_conflicts()

template<typename Traits , typename Tds , typename Itag >
template<class OutputItBoundaryEdges >

OutputItBoundaryEdges CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::get_boundary_of_conflicts | ( | const Point & | p,
|  | OutputItBoundaryEdges | eit,
|  | Face_handle | start
| ) |  | const

outputs the boundary edges of the conflict zone of point `p` into an output iterator.

This functions outputs in the container pointed to by `eit`, the boundary of the zone in conflict with `p`. The boundary edges of the conflict zone are output in counterclockwise order and each edge is described through the incident face which is not in conflict with `p`. The function returns the resulting output iterator.

Template Parameters

  OutputItBoundaryEdges | is an `OutputIterator` with value type `Edge`.

## ◆ get_conflicts()

template<typename Traits , typename Tds , typename Itag >
template<class OutputItFaces >

OutputItFaces CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::get_conflicts | ( | const Point & | p,
|  | OutputItFaces | fit,
|  | Face_handle | start
| ) |  | const

outputs the faces of the conflict zone of point `p` into an output iterator.

Same as `get_conflicts_and_boundary` except that only the faces in conflict with `p` are output. The function returns the resulting output iterator.

Precondition
  `dimension()==2`.

## ◆ get_conflicts_and_boundary()

template<typename Traits , typename Tds , typename Itag >
template<class OutputItFaces , class OutputItBoundaryEdges >

std::pair< OutputItFaces, OutputItBoundaryEdges > CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::get_conflicts_and_boundary | ( | const Point & | p,
|  | OutputItFaces | fit,
|  | OutputItBoundaryEdges | eit,
|  | Face_handle | start
| ) |  | const

outputs the faces and boundary edges of the conflict zone of point `p` into output iterators.

This function outputs in the container pointed to by `fit` the faces which are in conflict with point `p`. It outputs in the container pointed to by `eit` the boundary of the zone in conflict with `p`. The boundary edges of the conflict zone are output in counterclockwise order and each edge is described through its incident face which is not in conflict with `p`. The function returns in a `std::pair` the resulting output iterators.

Template Parameters

  OutItFaces | is an `OutputIterator` with value type `Face_handle`.
  OutItBoundaryEdges | is an `OutputIterator` with value type `Edge`.

Precondition
  `dimension()==2`.

## ◆ insert() [1/3]

template<typename Traits , typename Tds , typename Itag >

Vertex_handle CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::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()`

## ◆ insert() [2/3]

template<typename Traits , typename Tds , typename Itag >
template<class PointIterator >

std::ptrdiff_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert | ( | PointIterator | first,
|  | PointIterator | last
| ) |  |

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

Returns the number of inserted points.

Template Parameters

  PointIterator | is an `InputIterator` with value type `Point`.

## ◆ insert() [3/3]

template<typename Traits , typename Tds , typename Itag >
template<class PointWithInfoIterator >

std::ptrdiff_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert | ( | PointWithInfoIterator | first,
|  | PointWithInfoIterator | last
| ) |  |

inserts the points in the iterator range `[first,last)`.

Returns the number of inserted points. Note that this function is not guaranteed to insert the points following the order of `PointWithInfoIterator`, as `spatial_sort()` is used to improve efficiency. Given a pair `(p,i)`, the vertex `v` storing `p` also stores `i`, that is `v.point() == p` and `v.info() == i`. If several pairs have the same point, only one vertex is created, and one of the objects of type `Vertex::Info` will be stored in the vertex.

Precondition
  `Vertex` must be model of the concept `TriangulationVertexBaseWithInfo_2`.

Template Parameters

  PointWithInfoIterator | is an `InputIterator` with value type `std::pair<Point,Vertex::Info>`.

## ◆ insert_constraint()

template<typename Traits , typename Tds , typename Itag >
template<class PointIterator >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert_constraint | ( | PointIterator | first,
|  | PointIterator | last,
|  | bool | close = `false`
| ) |  |

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

The polyline is considered as a polygon if the first and last point are equal or if `close = true`. This enables for example passing the vertex range of a `Polygon_2`.

Template Parameters

  PointIterator | is an `InputIterator` with value type `Point`.

## ◆ insert_constraints() [1/2]

template<typename Traits , typename Tds , typename Itag >
template<class ConstraintIterator >

std::size_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::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 | is an `InputIterator` with value type `std::pair<Point,Point>` or `Segment`.

## ◆ insert_constraints() [2/2]

template<typename Traits , typename Tds , typename Itag >
template<class PointIterator , class IndicesIterator >

std::size_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::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`

Note
  points are inserted even if they are not an endpoint of a constraint.

Returns
  the number of inserted points.

## ◆ insert_unique_constraints() [1/2]

template<typename Traits , typename Tds , typename Itag >
template<class ConstraintIterator >

std::size_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert_unique_constraints | ( | ConstraintIterator | first,
|  | ConstraintIterator | last
| ) |  |

Same as `insert_constraints(begin,end)` except that duplicated pairs of points are only considered once.

Inserting the same constraint several times may cause problems in case of intersecting segments and non-exact constructions. Indeed, when an inserted segment is subdivided, the resulting subsegments are slightly displaced by numerical error and may therefore intersect the next insertion of the same segment, creating additional vertices at each new insertion.

Returns
  the number of inserted points.

Template Parameters

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

## ◆ insert_unique_constraints() [2/2]

template<typename Traits , typename Tds , typename Itag >
template<class PointIterator , class IndicesIterator >

std::size_t CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::insert_unique_constraints | ( | PointIterator | points_first,
|  | PointIterator | points_last,
|  | IndicesIterator | indices_first,
|  | IndicesIterator | indices_last
| ) |  |

Same as `insert_constraint(points_first, points_last, indices_first, indices_last)` except that duplicated pairs of points are only considered once.

Inserting the same constraint several times may cause problems in case of intersecting segments and non-exact constructions. Indeed, when an inserted segment is subdivided, the resulting subsegments are slightly displaced by numerical error and may therefore intersect the next insertion of the same segment, creating additional vertices at each new insertion.

Returns
  the number of inserted points.

Template Parameters

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

## ◆ is_flipable()

template<typename Traits , typename Tds , typename Itag >

bool CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::is_flipable | ( | Face_handle | f,
|  | int | i
| ) |  | const

determines if edge `(f,i)` can be flipped.

Advanced

Returns true if edge `(f,i)` is not constrained and the circle circumscribing `f` contains the vertex of `f->neighbor(i)` opposite to edge `(f,i)`.

## ◆ propagating_flip()

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::propagating_flip | ( | List_edges & | edges | ) |

makes the triangulation constrained Delaunay by flipping edges.

Advanced

The list `edges` contains an initial list of edges to be flipped. The returned triangulation is constrained Delaunay if the initial list contains at least all the edges of the input triangulation that failed to be constrained Delaunay. (An edge is said to be constrained Delaunay if it is either constrained or locally Delaunay.)

## ◆ remove()

template<typename Traits , typename Tds , typename Itag >

void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::remove | ( | Vertex_handle & | v | ) |

removes vertex v.

Precondition
  Vertex `v` is not incident to a constrained edge.