|
CGAL 5.3 - 2D Triangulation
|
|
CGAL 5.3 - 2D Triangulation
|
#include <CGAL/Delaunay_triangulation_2.h>
CGAL::Triangulation_2< Traits, Tds >.
The class Delaunay_triangulation_2 is designed to represent the Delaunay triangulation of a set of points in a plane.
A Delaunay triangulation of a set of points is a triangulation of the sets of points that fulfills the following empty circle property (also called Delaunay property): the circumscribing circle of any facet of the triangulation contains no point of the set in its interior. For a point set with no case of co-circularity of more than three points, the Delaunay triangulation is unique, it is the dual of the Voronoi diagram of the points.
| Tds | must be a model of TriangulationDataStructure_2. CGAL provides a default instantiation for this parameter, which is the class CGAL::Triangulation_data_structure_2 < CGAL::Triangulation_vertex_base_2<Traits>, CGAL::Triangulation_face_base_2<Traits> >. |
| Traits | must be a model of DelaunayTriangulationTraits_2. The concept DelaunayTriangulationTraits_2 refines the concept TriangulationTraits_2, providing a predicate type to check the empty circle property. |
Changing this predicate type allows the user to build Delaunay triangulations for different metrics such that \( L_1\) or \( L_{\infty}\) or any metric defined by a convex object. However, the user of an exotic metric must be careful that the constructed triangulation has to be a triangulation of the convex hull which means that convex hull edges have to be Delaunay edges. This is granted for any smooth convex metric (like \( L_2\)) and can be ensured for other metrics (like \( L_{\infty}\)) by the addition to the point set of well chosen sentinel points. The concept of DelaunayTriangulationTraits_2 is described DelaunayTriangulationTraits_2.
When dealing with a large triangulations, the user is advised to encapsulate the Delaunay triangulation class into a triangulation hierarchy, which means to use the class Triangulation_hierarchy_2<Tr> with the template parameter instantiated with Delaunay_triangulation_2. The triangulation hierarchy will then offer the same functionalities but be much more for efficient for locations and insertions.
Types
All the types defined in Triangulation_2<Traits,Tds> are inherited.
Implementation
Insertion is implemented by inserting in the triangulation, then performing a sequence of Delaunay flips. The number of flips is \( O(d)\) if the new vertex is of degree \( d\) in the new triangulation. For points distributed uniformly at random, insertion takes time \( O(1)\) on average.
Removal calls the removal in the triangulation and then re-triangulates the hole in such a way that the Delaunay criterion is satisfied. Removal of a vertex of degree \( d\) takes time \( O(d^2)\). The degree \( d\) is \( O(1)\) for a random vertex in the triangulation.
After a point location step, the nearest neighbor is found in time \( O(n)\) in the worst case, but in time \( O(1)\) for vertices distributed uniformly at random and any query point.
CGAL::Triangulation_2<Traits,Tds> TriangulationDataStructure_2 DelaunayTriangulationTraits_2 Triangulation_hierarchy_2<Tr> Creation | |
| Delaunay_triangulation_2 (const Traits >=Traits()) | |
| default constructor. | |
| Delaunay_triangulation_2 (const Delaunay_triangulation_2< Traits, Tds > &tr) | |
| copy constructor. More... | |
| template<class InputIterator > | |
| Delaunay_triangulation_2 (InputIterator first, InputIterator last, Traits gt=Traits()) | |
| Equivalent to constructing an empty triangulation with the optional traits class argument and calling insert(first,last). | |
Insertion and Removal | |
The following insertion and removal functions overwrite the functions inherited from the class In the degenerate case when there are co-circular points, the Delaunay triangulation is known not to be uniquely defined. In this case, CGAL chooses a particular Delaunay triangulation using a symbolic perturbation scheme [2]. Note that the other modifier functions of | |
| Vertex_handle | insert (const Point &p, Face_handle f=Face_handle()) |
inserts point p. More... | |
| Vertex_handle | insert (const Point &p, Locate_type <, Face_handle loc, int li) |
inserts a point p at the location given by (lt,loc,li). More... | |
| 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). More... | |
| template<class PointWithInfoInputIterator > | |
| std::ptrdiff_t | insert (PointWithInfoInputIterator first, PointWithInfoInputIterator last) |
inserts the points in the iterator range [first,last). More... | |
| void | remove (Vertex_handle v) |
| removes the vertex from the triangulation. | |
Displacement | |
| 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 move_if_no_collision(), if there is no collision. More... | |
Queries | |
| Vertex_handle | nearest_vertex (const Point &p, Face_handle f=Face_handle()) const |
returns any nearest vertex of p. More... | |
| 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... | |
Voronoi Diagram | |
The following member functions provide the elements of the dual Voronoi diagram. | |
| Point | dual (const Face_handle &f) const |
Returns the center of the circle circumscribed to face f. More... | |
| Object | dual (const Edge &e) const |
returns a segment, a ray or a line supported by the bisector of the endpoints of e. More... | |
| Object | dual (const Edge_circulator &ec) const |
| Idem. | |
| Object | dual (const Edge_iterator &ei) const |
| Idem. | |
| template<class Stream > | |
| Stream & | draw_dual (Stream &ps) |
output the dual Voronoi diagram to stream ps. | |
Predicates | |
| Oriented_side | side_of_oriented_circle (Face_handle f, const Point &p) const |
Returns the side of p with respect to the circle circumscribing the triangle associated with f. | |
Miscellaneous | |
The checking function | |
| bool | is_valid (bool verbose=false, int level=0) const |
tests the validity of the triangulation as a Triangulation_2 and additionally tests the Delaunay property. More... | |
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 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::Triangulation_2< Traits, Tds > | |
| Triangulation_2 (const Traits >=Traits()) | |
| Introduces an empty triangulation. | |
| Triangulation_2 (const Triangulation_2 &tr) | |
| Copy constructor. More... | |
| template<class InputIterator > | |
| Triangulation_2 (InputIterator first, InputIterator last, const Traits >=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. 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 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. More... | |
| 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. 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) |
If there is no collision during the move, this function is the same as move_if_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. | |
| Finite_vertex_handles | finite_vertex_handles () const |
| returns a range of iterators over finite vertices. More... | |
| 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. More... | |
| 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. More... | |
| 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. More... | |
| 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::Triangulation_2< Traits, Tds > | |
| ostream & | operator<< (ostream &os, const Triangulation_2< Traits, Tds > &T) |
Inserts the triangulation into the stream os. More... | |
| istream & | operator>> (istream &is, const Triangulation_2< Traits, Tds > &T) |
Reads a triangulation from stream is and assigns it to the triangulation. More... | |
| CGAL::Delaunay_triangulation_2< Traits, Tds >::Delaunay_triangulation_2 | ( | const Delaunay_triangulation_2< Traits, Tds > & | tr | ) |
copy constructor.
All the vertices and faces are duplicated.
| Point CGAL::Delaunay_triangulation_2< Traits, Tds >::dual | ( | const Face_handle & | f | ) | const |
Returns the center of the circle circumscribed to face f.
f is not infinite. | Object CGAL::Delaunay_triangulation_2< Traits, Tds >::dual | ( | const Edge & | e | ) | const |
returns a segment, a ray or a line supported by the bisector of the endpoints of e.
If faces incident to e are both finite, a segment whose endpoints are the duals of each incident face is returned. If only one incident face is finite, a ray whose endpoint is the dual of the finite incident face is returned. Otherwise both incident faces are infinite and the bisector line is returned.
| OutputItBoundaryEdges CGAL::Delaunay_triangulation_2< Traits, Tds >::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 function 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.
| OutputItBoundaryEdges | is an output iterator with Edge as value type. |
| OutputItFaces CGAL::Delaunay_triangulation_2< Traits, Tds >::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::Delaunay_triangulation_2< Traits, Tds >::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, i. e., the faces whose circumcircle contains p. It outputs in the container pointed to by eit the 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 its incident face which is not in conflict with p. The function returns in a std::pair the resulting output iterators.
| OutItFaces | is an output iterator with Face_handle as value type. |
| OutItBoundaryEdges | is an output iterator with Edge as value type. |
dimension()==2. | Vertex_handle CGAL::Delaunay_triangulation_2< Traits, Tds >::insert | ( | const Point & | p, |
| Face_handle | f = Face_handle() |
||
| ) |
inserts point p.
If point p coincides with an already existing vertex, this vertex is returned and the triangulation is not updated. Optional parameter f is used to initialize the location of p.
| Vertex_handle CGAL::Delaunay_triangulation_2< Traits, Tds >::insert | ( | const Point & | p, |
| Locate_type & | lt, | ||
| Face_handle | loc, | ||
| int | li | ||
| ) |
inserts a point p at the location given by (lt,loc,li).
Triangulation_2::locate() | std::ptrdiff_t CGAL::Delaunay_triangulation_2< Traits, Tds >::insert | ( | PointInputIterator | first, |
| PointInputIterator | last | ||
| ) |
inserts the points in the range [first,last).
Returns the number of inserted points. Note that this function is not guaranteed to insert the points following the order of PointInputIterator, as spatial_sort() is used to improve efficiency.
| PointInputIterator | must be an input iterator with the value type Point. |
| std::ptrdiff_t CGAL::Delaunay_triangulation_2< Traits, Tds >::insert | ( | PointWithInfoInputIterator | first, |
| PointWithInfoInputIterator | 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 PointWithInfoInputIterator, 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.| PointWithInfoInputIterator | must be an input iterator with the value type std::pair<Point,Vertex::Info>. |
| bool CGAL::Delaunay_triangulation_2< Traits, Tds >::is_valid | ( | bool | verbose = false, |
| int | level = 0 |
||
| ) | const |
tests the validity of the triangulation as a Triangulation_2 and additionally tests the Delaunay property.
This method is mainly useful for debugging Delaunay triangulation algorithms.
| Vertex_handle CGAL::Delaunay_triangulation_2< Traits, Tds >::move | ( | Vertex_handle | v, |
| const Point & | p | ||
| ) |
same as move_if_no_collision(), if there is no collision.
Otherwise, v is deleted and the vertex placed on p is returned.
v must be finite. | Vertex_handle CGAL::Delaunay_triangulation_2< Traits, Tds >::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.
Otherwise, the triangulation is not modified and the vertex at point p is returned.
v must be finite. | Vertex_handle CGAL::Delaunay_triangulation_2< Traits, Tds >::nearest_vertex | ( | const Point & | p, |
| Face_handle | f = Face_handle() |
||
| ) | const |
returns any nearest vertex of p.
The implemented function begins with a location step and f may be used to initialize the location.
1.8.13