CGAL 4.7 - 2D Triangulation Data Structure
CGAL::Triangulation_data_structure_2< Vb, Fb > Class Template Reference

#include <CGAL/Triangulation_data_structure_2.h>

Definition

The class Triangulation_data_structure_2 is a model for the TriangulationDataStructure_2 concept.

It can be used to represent an orientable 2D triangulation embedded in a space of any dimension.

The vertices and faces are stored in two nested containers, which are implemented using Compact_container. The class may offer some flexibility for the choice of container in the future, in the form of additional template parameters.

Is Model Of:
TriangulationDataStructure_2

Modifiers

In addition to the modifiers required by the TriangulationDataStructure_2 concept, the Triangulation_data_structure_2 class supports also the modifiers below. Note also that the modifiers below guarantee the combinatorial validity of the resulting data structure.

Illustrations

The join and split operations.
Insertion and removal of degree 2 vertices.

Types

typedef
Triangulation_data_structure_2
< Vb, Fb >
Tds

typedef Vb::template
Rebind_TDS< Tds >::Other
Vertex
The vertex type. More...

typedef Fb::template
Rebind_TDS< Tds >::Other
Face
The face type. More...

In addition to the interface documented in the concept, the class offers the following types.

typedef Compact_container< VertexVertex_range
Vertex container type. More...

typedef Compact_container< FaceFace_range
Face container type. More...

Operations

In addition to the interface documented in the concept, the class offers the following functions.

Face_rangefaces () const
Returns a reference to the container of faces. More...

Face_rangefaces ()
Returns a reference to the container of faces. More...

Vertex_rangevertices () const
Returns a reference to the container of vertices. More...

Vertex_rangevertices ()
Returns a reference to the container of vertices. More...

Modifiers

Vertex_handle join_vertices (Face_handle f, int i)
Joins the vertices that are endpoints of the edge (f,i), and returns a vertex handle to common vertex (see Fig. figtdssplitjoin). More...

Vertex_handle join_vertices (Edge e)
Joins the vertices that are endpoints of the edge e, and returns a vertex handle to common vertex. More...

Vertex_handle join_vertices (Edge_iterator eit)
Joins the vertices that are endpoints of the edge *eit, and returns a vertex handle to common vertex. More...

Vertex_handle join_vertices (Edges_circulator ec)
Joins the vertices that are endpoints of the edge *ec, and returns a vertex handle to common vertex. More...

boost::tuples::tuple
< Vertex_handle, Vertex_handle,
Face_handle, Face_handle
split_vertex (Vertex_handle v, Face_handle f1, Face_handle f2)
Splits the vertex v into two vertices v1 and v2. More...

Vertex_handle insert_degree_2 (Face_handle f, int i)
Inserts a degree two vertex and two faces adjacent to it that have two common edges. More...

void remove_degree_2 (Vertex_handle v)
Removes a degree 2 vertex and the two faces adjacent to it. More...

Member Typedef Documentation

template<typename Vb , typename Fb >
 typedef Fb::template Rebind_TDS::Other CGAL::Triangulation_data_structure_2< Vb, Fb >::Face

The face type.

template<typename Vb , typename Fb >
 typedef Compact_container CGAL::Triangulation_data_structure_2< Vb, Fb >::Face_range

Face container type.

template<typename Vb , typename Fb >
 typedef Triangulation_data_structure_2 CGAL::Triangulation_data_structure_2< Vb, Fb >::Tds
template<typename Vb , typename Fb >
 typedef Vb::template Rebind_TDS::Other CGAL::Triangulation_data_structure_2< Vb, Fb >::Vertex

The vertex type.

template<typename Vb , typename Fb >
 typedef Compact_container CGAL::Triangulation_data_structure_2< Vb, Fb >::Vertex_range

Vertex container type.

Member Function Documentation

template<typename Vb , typename Fb >
 Face_range& CGAL::Triangulation_data_structure_2< Vb, Fb >::faces ( ) const

Returns a reference to the container of faces.

template<typename Vb , typename Fb >
 Face_range& CGAL::Triangulation_data_structure_2< Vb, Fb >::faces ( )

Returns a reference to the container of faces.

template<typename Vb , typename Fb >
 Vertex_handle CGAL::Triangulation_data_structure_2< Vb, Fb >::insert_degree_2 ( Face_handle f, int i )

Inserts a degree two vertex and two faces adjacent to it that have two common edges.

The edge defined by the face handle f and the integer i is duplicated. It returns a handle to the vertex created (see Fig. figtdsirdeg2).

template<typename Vb , typename Fb >
 Vertex_handle CGAL::Triangulation_data_structure_2< Vb, Fb >::join_vertices ( Face_handle f, int i )

Joins the vertices that are endpoints of the edge (f,i), and returns a vertex handle to common vertex (see Fig. figtdssplitjoin).

Precondition
f must be different from Face_handle() and i must be 0, 1 or 2.
template<typename Vb , typename Fb >
 Vertex_handle CGAL::Triangulation_data_structure_2< Vb, Fb >::join_vertices ( Edge e )

Joins the vertices that are endpoints of the edge e, and returns a vertex handle to common vertex.

template<typename Vb , typename Fb >
 Vertex_handle CGAL::Triangulation_data_structure_2< Vb, Fb >::join_vertices ( Edge_iterator eit )

Joins the vertices that are endpoints of the edge *eit, and returns a vertex handle to common vertex.

template<typename Vb , typename Fb >
 Vertex_handle CGAL::Triangulation_data_structure_2< Vb, Fb >::join_vertices ( Edges_circulator ec )

Joins the vertices that are endpoints of the edge *ec, and returns a vertex handle to common vertex.

template<typename Vb , typename Fb >
 void CGAL::Triangulation_data_structure_2< Vb, Fb >::remove_degree_2 ( Vertex_handle v )

Removes a degree 2 vertex and the two faces adjacent to it.

The two edges of the star of v that are not incident to it are collapsed (see Fig. figtdsirdeg2).

Precondition
The degree of v must be equal to 2.
template<typename Vb , typename Fb >
 boost::tuples::tuple CGAL::Triangulation_data_structure_2< Vb, Fb >::split_vertex ( Vertex_handle v, Face_handle f1, Face_handle f2 )

Splits the vertex v into two vertices v1 and v2.

The common faces f and g of v1 and v2 are created after (in the counter-clockwise sense) the faces f1 and f2. The 4-tuple (v1,v2,f,g) is returned (see Fig. figtdssplitjoin).

Precondition
dimension() must be equal to 2, f1 and f2 must be different from Face_handle() and v must be a vertex of both f1 and f2.
template<typename Vb , typename Fb >
 Vertex_range& CGAL::Triangulation_data_structure_2< Vb, Fb >::vertices ( ) const

Returns a reference to the container of vertices.

template<typename Vb , typename Fb >
 Vertex_range& CGAL::Triangulation_data_structure_2< Vb, Fb >::vertices ( )

Returns a reference to the container of vertices.