CGAL 6.0.1 - 2D Triangulations
Loading...
Searching...
No Matches
CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag > Class Template Reference

#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
Traitsis 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.
Tdsmust be a model of TriangulationDataStructure_2or Default.
Itagallows 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 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 constraints is given as a pair of indices of the points in the range [points_first, points_last).
 
void remove (Vertex_handle &v)
 Removes vertex v.
 
void remove_incident_constraints (Vertex_handle v)
 Make the edges incident to vertex v unconstrained edges.
 
void remove_constraint (const Face_handle &f, int i)
 Make 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, PointConstraint
 
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_iteratorConstrained_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_typeAll_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_iteratorAll_edges
 range type for iterating over all edges (including infinite ones).
 
typedef Iterator_range< unspecified_typeAll_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_typeFinite_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_iteratorFinite_edges
 range type for iterating over finite edges.
 
typedef Iterator_range< unspecified_typeFinite_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_iteratorPoints
 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
 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_2tds () 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.
 
bool includes_edge (Vertex_handle va, Vertex_handle vb, Vertex_handle &vbb, Face_handle &fr, int &i)
 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)
 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
 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.
 
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
 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.
 
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
 Starts at an arbitrary face incident to v.
 
Face_circulator incident_faces (Vertex_handle v, Face_handle f) const
 Starts at face f.
 
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.
 
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.
 
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.
 
Point circumcenter (Face_handle f) const
 Compute 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.
 

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
ConstraintIteratormust be an InputIterator with the 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 counter-clockwise 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
OutputItBoundaryEdgesis an OutputIterator with the 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
OutItFacesis an OutputIterator with the value type Face_handle.
OutItBoundaryEdgesis an OutputIterator with the 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
PointIteratormust be an InputIterator with the 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
PointWithInfoIteratormust be an InputIterator with the 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
PointIteratormust be an InputIterator with the 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
ConstraintIteratormust be an InputIterator with the 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 constraints 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
PointIteratoris an InputIterator with the value type Point.
IndicesIteratoris 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 endpoint of a constraint.
Returns
the number of inserted points.

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