|
The endpoints of constrained edges are of course vertices of the triangulation. However the triangulation may include other vertices as well. There are three versions of constrained triangulations
The class Constrained_triangulation_2<Traits,Tds,Itag> of the Cgal library
implements constrained triangulations.
The template parameter Traits
stands for a geometric traits class. It has to be a model
of the concept TriangulationTraits_2.
When intersection of input constraints are supported,
the geometric traits class
is required to provide additional function object types
to compute the intersection of two segments.
It has then to be a model of the concept
ConstrainedTriangulationTraits_2.
The template parameter Tds
stands for
a triangulation data structure class that has to be a model
of the concept TriangulationDataStructure_2.
The third parameter Itag is the intersection tag
which serves to choose between the different
strategies to deal with constraints intersections.
Cgal provides three valid types for this parameter :
CGAL::No_intersection_tag disallows intersections of
input constraints,
CGAL::Exact_predicates_tag is to be used when the traits
class
provides exact predicates but approximate constructions of the
intersection points.
CGAL::Exact_intersections_tag is to be used in conjunction
with an exact arithmetic type.
The information about constrained edges is stored in the faces of the triangulation. Thus the nested Face type of a constrained triangulation offers additional functionalities to deal with this information. These additional functionalities induce additional requirements on the base face class plugged into the triangulation data structure of a constrained Delaunay triangulation. The base face of a constrained Delaunay triangulation has to be a model of the concept ConstrainedTriangulationFaceBase_2.
Cgal provides default instantiations for the template parameters Tds and Itag, and for the ConstrainedTriangulationFaceBase_2. If Gt is the geometric traits parameter, the default for ConstrainedTriangulationFaceBase_2 is the class 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_triangulation_2.h>
| typedef std::pair<Point,Point> | Constraint; | The type of input constraints |
| typedef Itag | Intersection_tag; | The intersection tag which decides how intersections between input constraints are dealt with. |
| Constrained_triangulation_2<Traits,Tds,Itag> ct; | |||
|
default constructor.
| |||
| Constrained_triangulation_2<Traits,Tds,Itag> ct ( Constrained_triangulation_2 ct1); | |||
|
Copy constructor, all faces and vertices
are duplicated and the constrained status of edges
is copied.
| |||
| template<class InputIterator> | |||
| Constrained_triangulation_2<Traits,Tds,Itag> ct ( 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.).
| |||
| Vertex_handle | ct.insert ( Point p, Face_handle f = Face_handle()) | |||
| Inserts point p and restores the status (constrained or not) of all the touched edges. If present f is used as an hint for the location of p. | ||||
| Vertex_handle | ct.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 | ct.push_back ( Point p) | Equivalent to insert(p). | ||
| template < class InputIterator > | ||||
| std::ptrdiff_t | ct.insert ( InputIterator first, InputIterator last) | |||
Inserts the points in the range
[.first, last.).
Returns the number of inserted points.
| ||||
| void | ct.insert_constraint ( Point a, Point b) | |||
Inserts points a and b, and inserts segment ab as a
constraint. Removes the faces crossed by segment ab and creates new
faces instead. If a vertex c lies on segment ab, constraint ab is
replaced by the two constraints ac and cb. Apart from the insertion of
a and b, the algorithm runs in time proportional to the number of
removed triangles.
| ||||
| void | ct.push_back ( Constraint c) | Inserts constraints c as above. | ||
| void | ct.insert_constraint ( Vertex_handle va, Vertex_handle vb) | |||
| Inserts the line segment s whose endpoints are the vertices va and vb as a constrained edge e. The triangles intersected by s are removed and new ones are created. | ||||
| void | ct.remove ( Vertex_handle v) |
Removes a vertex v.
| ||
| void | ct.remove_incident_constraints ( Vertex_handle v) | |||
| Make the edges incident to vertex v unconstrained edges. | ||||
| void | ct.remove_constrained_edge ( Face_handle f, int i) | |||
| Make edge (f,i) no longer constrained. | ||||
| bool | ct.is_valid ( bool verbose = false, int level = 0) const | |
| Checks the validity of the triangulation and the consistency of the constrained marks in edges. | ||
| ostream & | ostream& os << Constrained_triangulation_2<Traits,Tds> Ct | |
| Writes the triangulation as for CGAL::Triangulation_2<Traits,Tds> and, for each face f, and integers i=0,1,2, write ``C'' or ``N'' depending whether edge (f,i) is constrained or not. | ||
| istream& | istream& is >> Constrained_triangulation_2<Traits,Tds> Ct& t | |
| Reads a triangulation from stream is and assigns it to t. Data in the stream must have the same format operator<< uses. Note that t is first cleared. | ||
The insertion of a constrained edge runs in time proportional to the number of triangles intersected by this edge.