A DCEL (Doubly Connected Edge List) consists of vertices V, edges E, facets F and an incidence relation on them. Each edge is represented by two halfedges with opposite orientations. A DCEL serves as an interface for the Topological_map<Dcel> so a model of it must be provided as a template parameter. The predefined DCEL class implementation described in the next section can be used as a starting point for building one's own DCEL class. (The naming conventions were chosen to comply with those of the Halfedge_data_structure.)

A model for the TopologicalMapDcel concept must provide the following types and operations. (In addition to the requirements here, the local types Vertex,Halfedge and Face must be models of the concepts TopologicalMapDcelVertex, TopologicalMapDcelHalfedge and TopologicalMapDcelFace respectively.)


vertex type.

halfedge type.

face type.

type for size values.

a bidirectional iterator over the vertices. Its value-type is Vertex.

a bidirectional iterator over the halfedges. Its value-type is Halfedge.

a bidirectional iterator over the faces. Its value-type is Face.


TopologicalMapDcel d;
constructs an empty DCEL with one unbouned face.

Access Functions

Size d.size_of_vertices ()
number of vertices.
Size d.size_of_halfedges ()
number of halfedges (always even).
Size d.size_of_faces () number of faces.

The following operations have an equivalent const operations such as Vertex_const_iterator vertices_begin(); etc.

Vertex_iterator d.vertices_begin ()
returns the begin-iterator of the vertices in d.
Vertex_iterator d.vertices_end () returns the past-the-end iterator of the vertices in d.

Halfedge_iterator d.halfedges_begin ()
returns the begin-iterator of the halfedges in d.
Halfedge_iterator d.halfedges_end () returns the past-the-end iterator of the halfedges in d.

Vertex_iterator d.faces_begin () returns the begin-iterator of the faces in d.
Vertex_iterator d.faces_end () returns the past-the-end iterator of the faces in d.


The following operations allocate a new element of the respective type. Halfedges are always allocated in pairs of opposite halfedges. The twin pointers are automatically set.

Vertex* d.new_vertex () creates a default vertex.
Halfedge* d.new_edge () creates a new pair of opposite halfedges.
Face* d.new_face () creates a new face.

void d.delete_vertex ( Vertex* v)
deletes the vertex v.
void d.delete_edge ( Halfedge* h)
deletes the pair of opposite halfedges h.
void d.delete_face ( Face* f)
deletes the face f.

Has Models


See Also