The endpoints of constrained edges are of course vertices of the triangulation. However the triangulation may include 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 additonnal functionalities to deal with this information. These additional functionalities induce additionnal 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>
Triangulation_2<Traits,Tds>
| ||
| The type of input constraints | |
|
| The intersection tag which decides how intersections between input constraints are dealt with. |
| |||
default constructor.
| |||
| |||
Copy constructor, all faces and vertices
are duplicated and the constrained status of edges
is copied.
| |||
| |||
Introduces a constrained triangulation, the constrained edges of which
are the edges of the list lc.
| |||
| |||
| |||
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.
|
|
| |||
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. | ||||
|
| |||
Same as above except that the location of the point p to be inserted is assumed to be given by (lt,loc,i). | ||||
|
| |||
Equivalent to insert(p). | ||||
| ||||
|
| |||
Inserts the points in the range
first, last.
Returns the number of inserted points. Precondition: The value_type of first and last is Point. | ||||
|
| |||
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 proportionnal to the number of
removed triangles. Precondition: The relative interior of segment ab does not intersect the relative interior of another constrained edge. | ||||
|
| |||
Inserts constraints c as above. | ||||
|
| |||
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. | ||||
|
| |||
Removes a vertex v. Precondition: Vertex v is not incident to a constrained edge. | ||||
|
| |||
Make the edges incident to vertex v unconstrained edges. | ||||
|
| |||
Make edge (f,i) no longer constrained. |
advanced |
|
| |
Checks the validity of the triangulation and the consistency of the constrained marks in edges. |
advanced |
|
| |
Writes the triangulation and, for each face f, and integers i=0,1,2, write ``C'' or ``N'' depending whether edge (f,i) is constrained or not. |
The insertion of a constrained edge runs in time proportionnal to the number of triangles intersected by this edge.