Navigation: Up, Table of Contents,  Package Overview,  Bibliography,  Index,  Title Page , Acknowledging CGAL

CGAL::Constrained_Delaunay_triangulation_2<Traits,Tds,Itag>

Definition

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. The class Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> is designed to represent constrained Delaunay triangulations.

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. The desired version can be selected through the instantiation of the third template parameter Itag which can be one of the following :
CGAL::No_intersection_tag if intersections of input constraints are disallowed,
CGAL::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. CGAL::Exact_intersections_tag allows intersections between input constraints and is to be used in conjunction with an exact arithmetic type.

The template parameters Tds has to be instantiate with a model of TriangulationDataStructure_2. The geometric traits of a constrained Delaunay triangulation is required to provide the side_of_oriented_circle test as the geometric traits of a Delaunay triangulation and the Traits parameter has to be instantiated with a model DelaunayTriangulationTraits_2. When intersection of input constraints are supported, the geometric traits class is required to provide additional function object types to compute the intersection of two segments. and has then to be also a model of the concept ConstrainedTriangulationTraits_2.

A constrained Delaunay triangulation is not a Delaunay triangulation but it is a constrained triangulation. Therefore the class Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> 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 CGAL::Constrained_triangulation_face_base_2<Gt> and the default for the triangulation data structure parameter is the class CGAL::Triangulation_data_structure_2< CGAL::Triangulation_vertex_base_2<Gt>, CGAL::Constrained_triangulation_face_base_2<Gt> >. The default intersection tag is CGAL::No_intersection_tag.

#include <CGAL/Constrained_Delaunay_triangulation_2.h>

Inherits From

Constrained_triangulation_2<Traits,Tds,Itag>

Types

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

Creation

Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( Traits t = Traits());
Introduces an empty constrained Delaunay triangulation cdt.


Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( Constrained_Delaunay_triangulation_2 cdt1);
Copy constructor, all faces and vertices are duplicated and the constrained status of edges is copied.


template<class InputIterator>
Constrained_Delaunay_triangulation_2<Traits,Tds,Itag> cdt ( InputIterator first, InputIterator last, Traits t=Traits());
A templated constructor which introduces and builds a constrained triangulation with constrained edges in the range [.first, last.).
Precondition: The value_type of first and last is Constraint.

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 cdt.insert ( Point p, Face_handle f = Face_handle())
Inserts point p in the triangulation. If present f is used as an hint for the location of p.

Vertex_handle cdt.insert ( 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).

Vertex_handle cdt.push_back ( Point p) Equivalent to insert(p).

template < class InputIterator >
int cdt.insert ( InputIterator first, InputIterator last)
Inserts the points in the range [.first, last.). Returns the number of inserted points.
Precondition: The value_type of first and last is Point.

void cdt.insert_constraint ( Point a, Point b)
Inserts segment ab as a constrained edge in the triangulation.

void cdt.push_back ( Constraint c) Inserts constraints c as above.

void cdt.insert_constraint ( Vertex_handle va, Vertex_handle vb)
Inserts the line segment whose endpoints are the vertices va and vb as a constrained edge e in the triangulation.

void cdt.remove ( Vertex_handle & v) Removes vertex v.
Precondition: Vertex v is not incident to a constrained edge.

void cdt.remove_incident_constraints ( Vertex_handle v)
Make the edges incident to vertex v unconstrained edges.

void cdt.remove_constraint ( Face_handle f, int i)
Edge (f,i) is no longer constrained.

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>
cdt.get_conflicts_and_boundary ( Point p,
OutputItFaces fit,
OutputItBoundaryEdges eit,
Face_handle start)
OutItFaces is an output iterator with Face_handle as value type. OutItBoundaryEdges stands for an output iterator with Edge as value type. This members 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 <class OutputItFaces>
OutputItFaces cdt.get_conflicts ( Point p, OutputItFaces fit, Face_handle start)
Same as above except that only the faces in conflict with p are output. The function returns the resulting output iterator.

template <class OutputItBoundaryEdges>
OutputItBoundaryEdges cdt.get_boundary_of_conflicts ( Point p, OutputItBoundaryEdges eit, Face_handle start)
OutputItBoundaryEdges stands for an output iterator with Edge as value type. 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.

Checking

bool cdt.is_valid () Checks if the triangulation is valid and if each constrained edge is consistently marked constrained in its two incident faces.


begin of advanced section  advanced  begin of advanced section

Flips

bool cdt.is_flipable ( Face_handle f, int i)
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 cdt.flip ( Face_handle& f, int i) Flip f and f->neighbor(i).

void cdt.propagating_flip ( List_edges & edges)
Makes the triangulation constrained Delaunay by flipping edges. 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.)
end of advanced section  advanced  end of advanced section

See Also

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

Next: Constrained_triangulation_2<Traits,Tds,Itag>
Navigation: Up, Table of Contents,  Package Overview,  Bibliography,  Index,  Title Page , Acknowledging CGAL
CGAL Open Source Project. Release 3.3.1. 25 August 2007.