|
CGAL 4.6.2 - 2D Triangulation
|
|
CGAL 4.6.2 - 2D Triangulation
|
#include <CGAL/Constrained_Delaunay_triangulation_2.h>
CGAL::Constrained_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.
| 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. |
| Itag | allows to select if intersecting constraints are supported and how they are handled.
|
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_intersection_tag.
Types
All types used in this class are inherited from the base class Constrained_triangulation_2<Traits,Tds,Itag>.
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()) | |
A templated constructor which introduces and builds a constrained triangulation with constraints in the range [first,last). More... | |
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). More... | |
| 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). More... | |
| template<class PointWithInfoIterator > | |
| std::ptrdiff_t | insert (PointWithInfoIterator first, PointWithInfoIterator last) |
inserts the points in the iterator range [first,last). More... | |
| 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). More... | |
| template<class ConstraintIterator > | |
| std::size_t | insert_constraints (ConstraintIterator first, ConstraintIterator last) |
inserts the constraints in the range [first,last). More... | |
| template<class PointIterator , class IndicesIterator > | |
| std::size_t | insert_constraints (PointIterator points_first, PointIterator points_last, IndicesIterator indices_first, IndicesIterator indices_last) |
| Same as above except that each constraints is given as a pair of indices of the points in the range [points_first, points_last). More... | |
| void | remove (Vertex_handle &v) |
| Removes vertex v. More... | |
| 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 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 | |
| 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. More... | |
| 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. More... | |
| 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. More... | |
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. More... | |
| void | flip (Face_handle &f, int i) |
| This is an advanced function. More... | |
| void | propagating_flip (List_edges &edges) |
| makes the triangulation constrained Delaunay by flipping edges. More... | |
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. More... | |
| 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 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::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. More... | |
| 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. | |
| 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 <, 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). | |
| void | insert_constraint (Point a, Point b) |
Inserts points a and b in this order, and inserts the line segment ab as a constraint. More... | |
| 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. More... | |
| 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). 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. | |
| Public Member Functions inherited from CGAL::Triangulation_2< Traits, Tds > | |
| Triangulation_2 (const Traits >=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_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 |
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, Vertex_handle &vbr, 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 <, 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. | |
| Related Functions inherited from CGAL::Constrained_triangulation_2< Traits, Tds, Itag > | |
| 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... | |
| CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::Constrained_Delaunay_triangulation_2 | ( | ConstraintIterator | first, |
| ConstraintIterator | last, | ||
| const Traits & | t = Traits() |
||
| ) |
A templated constructor which introduces and builds a constrained triangulation with constraints in the range [first,last).
| ConstraintIterator | must be an InputIterator with the value type std::pair<Point,Point> or Segment. |
| void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::flip | ( | Face_handle & | f, |
| int | i | ||
| ) |
This is an advanced function.
Flip f and f->neighbor(i).
| 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.
| OutputItBoundaryEdges | is an OutputIterator with the value type Edge. |
| 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.
dimension()==2. | 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.
| OutItFaces | is an OutputIterator with the value type Face_handle. |
| OutItBoundaryEdges | is an OutputIterator with the value type Edge. |
dimension()==2. | 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).
Triangulation_2::locate() | 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.
| PointIterator | must be an InputIterator with the value type Point. |
| 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.
Vertex must be model of the concept TriangulationVertexBaseWithInfo_2.| PointWithInfoIterator | must be an InputIterator with the value type std::pair<Point,Vertex::Info>. |
| 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.
| PointIterator | must be an InputIterator with the value type Point. |
| 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.
| ConstraintIterator | must be an InputIterator with the value type std::pair<Point,Point> or Segment. |
| 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)
| 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 |
| 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.
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).
| void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::propagating_flip | ( | List_edges & | edges) |
makes the triangulation constrained Delaunay by flipping edges.
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.)
| void CGAL::Constrained_Delaunay_triangulation_2< Traits, Tds, Itag >::remove | ( | Vertex_handle & | v) |
Removes vertex v.
v is not incident to a constrained edge. 
1.8.4