\( \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.4 - 2D Triangulation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
CGAL::Constrained_triangulation_2< Traits, Tds, Itag > Class Template Reference

#include <CGAL/Constrained_triangulation_2.h>

Inherits from

CGAL::Triangulation_2< Traits, Tds >.

Inherited by CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >.

Definition

A constrained triangulation is a triangulation of a set of points which has to include among its edges a given set of segments joining the points.

The given segments are called constraints and the corresponding edges in the triangulation are called constrained edges.

The endpoints of constrained edges are of course vertices of the triangulation. However the triangulation may include other vertices as well. There are three versions of constrained triangulations

  • In the basic version, the constrained triangulation does not handle intersecting constraints, and the set of input constraints is required to be a set of segments that do not intersect except possibly at their endpoints. Any number of constrained edges are allowed to share the same endpoint. Vertical constrained edges are allowed as well as constrained edges with null length.
  • The two other versions support intersecting input constraints. In those versions, input constraints are allowed to be intersecting, overlapping or partially overlapping segments. The triangulation introduce additional vertices at each point which is a proper intersection point of two constraints. A single constraint intersecting other constraints will then appear as the union of several constrained edges of the triangulation. The two versions dealing with intersecting constraints, slightly differ in the way intersecting constraints are dealt with.
    • One of them is designed to be robust when predicates are evaluated exactly but constructions (i. e. intersection computations) are approximate.
    • The other one is designed to be used with an exact arithmetic (meaning exact evaluation of predicates and exact computation of intersections.) This last version finds its full efficiency when used in conjunction with a constraint hierarchy data structure as provided in the class Constrained_triangulation_plus_2. See Section Constrained Triangulations Plus.
constraints.png
Template Parameters
Traitsis a geometric traits class and must be a model of the concept TriangulationTraits_2. 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. It has then to be a model of the concept ConstrainedTriangulationTraits_2.
Tdsmust be a model of the concept TriangulationDataStructure_2.
Itagis the intersection tag which serves to choose between the different strategies to deal with constraints intersections. CGAL provides three valid types for this parameter:

The information about constrained edges is stored in the faces of the triangulation. 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 default instantiations for the template parameters Tds and Itag, and for the ConstrainedTriangulationFaceBase_2. 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 < Triangulation_vertex_base_2<Gt>, Constrained_triangulation_face_base_2<Gt> >. The default intersection tag is No_intersection_tag.

See Also
CGAL::Triangulation_2<Traits,Tds>
TriangulationDataStructure_2
TriangulationTraits_2
ConstrainedTriangulationTraits_2
ConstrainedTriangulationFaceBase_2

Implementation

The insertion of a constrained edge runs in time proportional to the number of triangles intersected by this edge.

Related Functions

(Note that these are not member functions.)

ostream & operator<< (ostream &os, const Constrained_triangulation_2< Traits, Tds > &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.
 
istream & operator>> (istream &is, Constrained_triangulation_2< Traits, Tds > Ct &t)
 Reads a triangulation from stream is and assigns it to t. More...
 

Types

typedef std::pair< Point, PointConstraint
 The type of input constraints.
 
typedef Itag Intersection_tag
 The intersection tag which decides how intersections between input constraints are dealt with.
 

Creation

 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.
 
template<class InputIterator >
 Constrained_triangulation_2 (InputIterator first, InputIterator last, const Traits &t=Traits())
 A templated constructor which introduces and builds a constrained triangulation with constrained edges in the range [first,last). More...
 

Queries

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. More...
 

Insertion and Removal

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. More...
 
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 InputIterator >
std::ptrdiff_t insert (InputIterator first, InputIterator last)
 Inserts the points in the range [first,last). More...
 
void insert_constraint (Point a, Point b)
 Inserts points a and b, and inserts segment ab as a constraint. More...
 
void push_back (const Constraint &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 constrained edge. More...
 
void remove (Vertex_handle v)
 Removes a vertex v. More...
 
void remove_incident_constraints (Vertex_handle v)
 Make the edges incident to vertex v unconstrained edges.
 
void remove_constrained_edge (Face_handle f, int i)
 Make 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.
 

Additional Inherited Members

- 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 the finite vertices of the triangulation.
 
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::Triangulation_2< Traits, Tds >
 Triangulation_2 (const Traits &gt=Traits())
 Introduces an empty triangulation.
 
 Triangulation_2 (const Triangulation_2 &tr)
 Copy constructor. More...
 
Triangulation_2 operator= (const Triangulation_2< Traits, Tds > &tr)
 Assignment. More...
 
void swap (Triangulation_2 &tr)
 The triangulations tr and *this are swapped. More...
 
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
 a face incident to the infinite vertex.
 
Vertex_handle infinite_vertex () const
 the infinite vertex.
 
Vertex_handle finite_vertex () const
 a vertex distinct from the infinite vertex.
 
const Geom_traitsgeom_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_2tds ()
 Returns a reference to the triangulation data structure.
 
bool is_infinite (Vertex_handle v) const
 true iff v is the infinite vertex.
 
bool is_infinite (Face_handle f) const
 true iff face f is infinite.
 
bool is_infinite (Face_handle f, int i) const
 true iff edge (f,i) is infinite.
 
bool is_infinite (Edge e) const
 true iff edge e is infinite.
 
bool is_infinite (Edge_circulator ec) const
 true iff edge *ec is infinite.
 
bool is_infinite (All_edges_iterator ei) const
 true iff edge *ei is infinite.
 
bool is_edge (Vertex_handle va, Vertex_handle vb)
 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. More...
 
bool includes_edge (Vertex_handle va, Vertex_handle &vb, Face_handle &fr, int &i)
 true if the line segment from va to vb includes an edge e incident to va. More...
 
bool is_face (Vertex_handle v1, Vertex_handle v2, Vertex_handle v3)
 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. More...
 
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. More...
 
Face_handle inexact_locate (const Point &query, Face_handle start=Face_handle()) const
 Same as locate() but uses inexact predicates. More...
 
Face_handle locate (const Point &query, Locate_type &lt, int &li, Face_handle h=Face_handle()) const
 Same as above. More...
 
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. More...
 
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. More...
 
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). More...
 
Vertex_handle insert (const Point &p, Face_handle f=Face_handle())
 Inserts point p in the triangulation and returns the corresponding vertex. More...
 
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 InputIterator >
std::ptrdiff_t insert (InputIterator first, InputIterator last)
 Inserts the points in the range [first,last). More...
 
void remove (Vertex_handle v)
 Removes the vertex from the triangulation. More...
 
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. More...
 
Vertex_handle move (Vertex_handle v, const Point &p)
 same as above if there is no collision. More...
 
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. More...
 
Vertex_handle insert_in_edge (const Point &p, Face_handle f, int i)
 Inserts vertex v in edge i of f. More...
 
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. More...
 
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. More...
 
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). More...
 
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. More...
 
Finite_vertices_iterator finite_vertices_begin () const
 Starts at an arbitrary finite vertex.
 
Finite_vertices_iterator finite_vertices_end () const
 Past-the-end iterator.
 
Finite_edges_iterator finite_edges_begin () const
 Starts at an arbitrary finite edge.
 
Finite_edges_iterator finite_edges_end () const
 Past-the-end iterator.
 
Finite_faces_iterator finite_faces_begin () const
 Starts at an arbitrary finite face.
 
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.
 
All_vertices_iterator all_vertices_begin () const
 Starts at an arbitrary vertex.
 
All_vertices_iterator all_vertices_end () const
 Past-the-end iterator.
 
All_edges_iterator all_edges_begin () const
 Starts at an arbitrary edge.
 
All_edges_iterator all_edges_end () const
 Past-the-end iterator.
 
All_faces_iterator all_faces_begin () const
 Starts at an arbitrary face.
 
All_faces_iterator all_faces_end () const
 Past-the-end iterator.
 
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. More...
 
Face_circulator incident_faces (Vertex_handle v) const
 Starts at an arbitrary face incident to v.
 
Face_circulator incident_faces (Vertex_handle v, Face_handle f) const
 Starts at face f. More...
 
Edge_circulator incident_edges (Vertex_handle v) const
 Starts at an arbitrary edge incident to v.
 
Edge_circulator incident_edges (Vertex_handle v, Face_handle f) const
 Starts at the first edge of f incident to v, in counterclockwise order around v. More...
 
Vertex_circulator incident_vertices (Vertex_handle v) const
 Starts at an arbitrary vertex incident to v.
 
Vertex_circulator incident_vertices (Vertex_handle v, Face_handle f)
 Starts at the first vertex of f adjacent to v in counterclockwise order around v. More...
 
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. More...
 
int mirror_index (Face_handle f, int i) const
 returns the index of f in its \( i^{th}\) neighbor. More...
 
Edge mirror_edge (Edge e) const
 returns the same edge seen from the other adjacent face. More...
 
int ccw (int i) const
 Returns \( i+1\) modulo 3. More...
 
int cw (int i) const
 Returns \( i+2\) modulo 3. More...
 
Triangle triangle (Face_handle f) const
 Returns the triangle formed by the three vertices of f. More...
 
Segment segment (Face_handle f, int i) const
 Returns the line segment formed by the vertices ccw(i) and cw(i) of face f. More...
 
Segment segment (const Edge &e) const
 Returns the line segment corresponding to edge e. More...
 
Segment segment (const Edge_circulator &ec) const
 Returns the line segment corresponding to edge *ec. More...
 
Segment segment (const Edge_iterator &ei) const
 Returns the line segment corresponding to edge *ei. More...
 
Point circumcenter (Face_handle f) const
 Compute the circumcenter of the face pointed to by f. More...
 
void set_infinite_vertex (const Vertex_handle &v)
 This is an advanced function. More...
 
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. More...
 
- 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.
 

Constructor & Destructor Documentation

template<typename Traits , typename Tds , typename Itag >
template<class InputIterator >
CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::Constrained_triangulation_2 ( InputIterator  first,
InputIterator  last,
const Traits &  t = Traits() 
)

A templated constructor which introduces and builds a constrained triangulation with constrained edges in the range [first,last).

Template Parameters
InputIteratormust be an input iterator with the value type Constraint.

Member Function Documentation

template<typename Traits , typename Tds , typename Itag >
template<class OutputItEdges >
OutputItEdges CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::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.

Template Parameters
OutputItEdgesis an output iterator with Edge as value type.
template<typename Traits , typename Tds , typename Itag >
Vertex_handle CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::insert ( Point  p,
Face_handle  f = Face_handle() 
)

Inserts point p and restores the status (constrained or not) of all the touched edges.

If present f is used as an hint for the location of p.

template<typename Traits , typename Tds , typename Itag >
Vertex_handle CGAL::Constrained_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()
template<typename Traits , typename Tds , typename Itag >
template<class InputIterator >
std::ptrdiff_t CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::insert ( InputIterator  first,
InputIterator  last 
)

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

Returns the number of inserted points.

Precondition
The value_type of first and last is Point.
template<typename Traits , typename Tds , typename Itag >
void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::insert_constraint ( Point  a,
Point  b 
)

Inserts points a and b, and inserts segment ab as a constraint.

Removes the faces crossed by segment ab and creates new faces instead. If a vertex c lies on segment ab, constraint ab is replaced by the two constraints ac and cb. Apart from the insertion of a and b, the algorithm runs in time proportional to the number of removed triangles.

Precondition
The relative interior of segment ab does not intersect the relative interior of another constrained edge.
template<typename Traits , typename Tds , typename Itag >
void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::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 constrained edge.

The triangles intersected by s are removed and new ones are created.

template<typename Traits , typename Tds , typename Itag >
void CGAL::Constrained_triangulation_2< Traits, Tds, Itag >::remove ( Vertex_handle  v)

Removes a vertex v.

Precondition
Vertex v is not incident to a constrained edge.

Friends And Related Function Documentation

template<typename Traits , typename Tds , typename Itag >
istream & operator>> ( istream &  is,
Constrained_triangulation_2< Traits, Tds > Ct &  t 
)
related

Reads a triangulation from stream is and assigns it to t.

Data in the stream must have the same format operator<< uses. Note that t is first cleared.