ArrangementDcel

A doubly-connected edge-list (DCEL for short) data-structure. It consists of three containers of records: vertices $$V, halfedges $$E, and faces $$F. It maintains the incidence relation among them. The halfedges are ordered in pairs sometimes referred to as twins, such that each halfedge pair represent an edge.

A model of the ArrangementDcel concept must provide the following types and operations. (In addition to the requirements here, the local types Vertex,Halfedge, Face Hole and Isolated_vertex must be models of the concepts ArrangementDcelVertex, ArrangementDcelHalfedge, ArrangementDcelFace, ArrangementDcelHole and ArrangementDcelIsolatedVertex respectively.)

Types

ArrangementDcel::Vertex
	the vertex type.
ArrangementDcel::Halfedge
	the halfedge type.
ArrangementDcel::Face
	the face type.
ArrangementDcel::Hole
	the hole type.
ArrangementDcel::Isolated_vertex
	the isolated vertex type.
ArrangementDcel::Size
	used to represent size values (e.g., size_t).
ArrangementDcel::Vertex_iterator
	a bidirectional iterator over the vertices. Its value-type is Vertex.
ArrangementDcel::Halfedge_iterator
	a bidirectional iterator over the halfedges. Its value-type is Halfedge.
ArrangementDcel::Face_iterator
	a bidirectional iterator over the faces. Its value-type is Face.

The non-mutable iterators Vertex_const_iterator, Halfedge_const_iterator and Face_const_iterator are also defined.

Creation

ArrangementDcel dcel;
	constructs an empty DCEL with one unbouned face.

Face*	dcel.assign ( Self other, const Face *uf)
		assigns the contents of the other DCEL whose unbounded face is given by uf, to dcel. The function returns a pointer to the unbounded face of dcel after the assignment.

Access Functions

Size	dcel.size_of_vertices ()
		returns the number of vertices.
Size	dcel.size_of_halfedges ()
		returns the number of halfedges (always even).
Size	dcel.size_of_faces ()
		returns the number of faces.
Size	dcel.size_of_holes ()
		returns the number of holes (the number of connected components).
Size	dcel.size_of_isolated_vertices ()
		returns the number of isolated vertices.

The following operations have an equivalent const operations that return the corresponding non-mutable iterators:

Vertex_iterator	dcel.vertices_begin ()
		returns a begin-iterator of the vertices in dcel.
Vertex_iterator	dcel.vertices_end ()
		returns a past-the-end iterator of the vertices in dcel.
Halfedge_iterator	dcel.halfedges_begin ()
		returns a begin-iterator of the halfedges in dcel.
Halfedge_iterator	dcel.halfedges_end ()
		returns a past-the-end iterator of the halfedges in dcel.
Vertex_iterator	dcel.faces_begin ()
		returns a begin-iterator of the faces in dcel.
Vertex_iterator	dcel.faces_end ()	returns a past-the-end iterator of the faces in dcel.

Modifiers

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

Vertex*	dcel.new_vertex ()	creates a new vertex.
Halfedge*	dcel.new_edge ()	creates a new pair of twin halfedges.
Face*	dcel.new_face ()	creates a new face.
Hole*	dcel.new_hole ()	creates a new hole record.
Isolated_vertex*	dcel.new_isolated_vertex ()
		creates a new isolated vertex record.
void	dcel.delete_vertex ( Vertex* v)
		deletes the vertex v.
void	dcel.delete_edge ( Halfedge* e)
		deletes the halfedge e as well as its twin.
void	dcel.delete_face ( Face* f)
		deletes the face f.
void	dcel.delete_hole ( Hole* ho)
		deletes the hole ho.
void	dcel.delete_isolated_vertex ( Isolated_vertex* iv)
		deletes the isolated vertex iv.

Has Models

Arr_dcel_base<V,H,F>
Arr_default_dcel<Traits>
Arr_face_extended_dcel<Traits,FData,V,H,F>
Arr_extended_dcel<Traits,VData,HData,FData,V,H,F>

See Also