Definition

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, Outer_ccb, Inner_ccb, and Isolated_vertex must be models of the concepts ArrangementDcelVertex, ArrangementDcelHalfedge, ArrangementDcelFace, ArrangementDcelOuterCcb, ArrangementDcelInnerCcb, and ArrangementDcelIsolatedVertex respectively.)

Has Models:

CGAL::Arr_dcel_base<V,H,F>

CGAL::Arr_default_dcel<Traits>

CGAL::Arr_face_extended_dcel<Traits,FData,V,H,F>

CGAL::Arr_extended_dcel<Traits,VData,HData,FData,V,H,F>

See also: ArrangementDcelVertex; ArrangementDcelHalfedge; ArrangementDcelFace; ArrangementDcelOuterCcb; ArrangementDcelInnerCcb; ArrangementDcelIsolatedVertex

Types
typedef unspecified_type	Vertex
	the vertex type. More...

typedef unspecified_type	Halfedge
	the halfedge type. More...

typedef unspecified_type	Face
	the face type. More...

typedef unspecified_type	Outer_ccb
	the Outer CCB type. More...

typedef unspecified_type	Inner_ccb
	the Inner CCB type. More...

typedef unspecified_type	Hole
	the hole (i.e., Inner_ccb) type. More...

typedef unspecified_type	Isolated_vertex
	the isolated vertex type. More...

typedef unspecified_type	Size
	used to represent size values (e.g., `size_t`). More...

typedef unspecified_type	Vertex_iterator
	a bidirectional iterator over the vertices. More...

typedef unspecified_type	Vertex_const_iterator
	a bidirectional iterator over the vertices. More...

typedef unspecified_type	Halfedge_iterator
	a bidirectional iterator over the halfedges. More...

typedef unspecified_type	Halfedge_const_iterator
	a bidirectional iterator over the halfedges. More...

typedef unspecified_type	Face_iterator
	a bidirectional iterator over the faces. More...

typedef unspecified_type	Face_const_iterator
	a bidirectional iterator over the faces. More...

Creation
	Arr_dcel ()
	constructs an empty DCEL with one unbounded face.

Face *	assign (const Self &other, const Face *uf)
	assigns the contents of the `other` DCEL whose unbounded face is given by `uf`, to `dcel`. More...

Access Functions
Size	size_of_vertices () const
	obtains the number of vertices. More...

Size	size_of_halfedges () const
	obtains the number of halfedges (always even). More...

Size	size_of_faces () const
	obtains the number of faces. More...

Size	size_of_outer_ccbs () const
	obtains the number of outer CCBs. More...

Size	size_of_inner_ccbs () const
	obtains the number of inner CCBs. More...

Size	size_of_holes () const
	obtains the number of holes (i.e., inner CCBs). More...

Size	size_of_isolated_vertices () const
	obtains the number of isolated vertices. More...

Vertex_iterator	vertices_begin ()
	obtains a begin-iterator of the vertices in `dcel`. More...

Vertex_iterator	vertices_end ()
	obtains a past-the-end iterator of the vertices in `dcel`. More...

unspecified_type	vertex_handles ()
	obtains a range over handles of the vertices in `dcel`. More...

Vertex_const_iterator	vertices_begin () const
	obtains a begin-iterator of the vertices in `dcel`. More...

Vertex_const_iterator	vertices_end () const
	obtains a past-the-end iterator of the vertices in `dcel`. More...

unspecified_type	vertex_handles () const
	obtains a const range (model of `ConstRange`) over handles of the vertices in `dcel`.

Halfedge_iterator	halfedges_begin ()
	obtains a begin-iterator of the halfedges in `dcel`. More...

Halfedge_iterator	halfedges_end ()
	obtains a past-the-end iterator of the halfedges in `dcel`. More...

unspecified_type	halfedge_handles ()
	obtains a range over handles of the halfedges in `dcel`. More...

Halfedge_const_iterator	halfedges_begin () const
	obtains a begin-iterator of the halfedges in `dcel`. More...

Halfedge_const_iterator	halfedges_end () const
	obtains a past-the-end iterator of the halfedges in `dcel`. More...

unspecified_type	halfedge_handles () const
	obtains a const range (model of `ConstRange`) over handles of the halfedges in `dcel`.

Face_iterator	faces_begin ()
	obtains a begin-iterator of the faces in `dcel`. More...

Face_iterator	faces_end ()
	obtains a past-the-end iterator of the faces in `dcel`. More...

unspecified_type	face_handles ()
	obtains a range over handles of the faces in `dcel`. More...

Face_const_iterator	faces_begin () const
	obtains a begin-iterator of the faces in `dcel`. More...

Face_const_iterator	faces_end () const
	obtains a past-the-end iterator of the faces in `dcel`. More...

unspecified_type	face_handles () const
	obtains a const range (model of `ConstRange`) over handles 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 halfedges and their opposite pointers are automatically set.
Vertex *	new_vertex ()
	creates a new vertex. More...

Halfedge *	new_edge ()
	creates a new pair of twin halfedges. More...

Face *	new_face ()
	creates a new face. More...

Hole *	new_outer_ccb ()
	creates a new outer CCB record. More...

Hole *	new_inner_ccb ()
	creates a new inner CCB record. More...

Hole *	new_hole ()
	creates a new hole (i.e., inner CCB) record. More...

Isolated_vertex *	new_isolated_vertex ()
	creates a new isolated vertex record. More...

void	delete_vertex (Vertex *v)
	deletes a given vertex `v`. More...

void	delete_edge (Halfedge *e)
	deletes a given halfedge `e` as well as its twin. More...

void	delete_face (Face *f)
	deletes a given face `f`. More...

void	delete_outer_ccb (Outer_ccb *oc)
	deletes a given outer CCB `oc`. More...

void	delete_inner_ccb (Inner_ccb *oc)
	deletes a given inner CCB `ic`. More...

void	delete_hole (Hole *ho)
	deletes a given hole (i.e., inner CCB) `ho`. More...

void	delete_isolated_vertex (Isolated_vertex *iv)
	deletes a given isolated vertex `iv`. More...

Member Typedef Documentation

◆ Face

typedef unspecified_type ArrangementDcel::Face

the face type.

◆ Face_const_iterator

typedef unspecified_type ArrangementDcel::Face_const_iterator

a bidirectional iterator over the faces.

Its value-type is Face.

◆ Face_iterator

typedef unspecified_type ArrangementDcel::Face_iterator

a bidirectional iterator over the faces.

Its value-type is Face.

◆ Halfedge

typedef unspecified_type ArrangementDcel::Halfedge

the halfedge type.

◆ Halfedge_const_iterator

typedef unspecified_type ArrangementDcel::Halfedge_const_iterator

a bidirectional iterator over the halfedges.

Its value-type is Halfedge.

◆ Halfedge_iterator

typedef unspecified_type ArrangementDcel::Halfedge_iterator

a bidirectional iterator over the halfedges.

Its value-type is Halfedge.

◆ Hole

typedef unspecified_type ArrangementDcel::Hole

the hole (i.e., Inner_ccb) type.

◆ Inner_ccb

typedef unspecified_type ArrangementDcel::Inner_ccb

the Inner CCB type.

◆ Isolated_vertex

typedef unspecified_type ArrangementDcel::Isolated_vertex

the isolated vertex type.

◆ Outer_ccb

typedef unspecified_type ArrangementDcel::Outer_ccb

the Outer CCB type.

◆ Size

typedef unspecified_type ArrangementDcel::Size

used to represent size values (e.g., size_t).

◆ Vertex

typedef unspecified_type ArrangementDcel::Vertex

the vertex type.

◆ Vertex_const_iterator

typedef unspecified_type ArrangementDcel::Vertex_const_iterator

a bidirectional iterator over the vertices.

Its value-type is Vertex.

◆ Vertex_iterator

typedef unspecified_type ArrangementDcel::Vertex_iterator

a bidirectional iterator over the vertices.

Its value-type is Vertex.

Member Function Documentation

◆ assign()

Face* ArrangementDcel::assign	(	const 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.

◆ delete_edge()

void ArrangementDcel::delete_edge ( Halfedge * e )

deletes a given halfedge e as well as its twin.

◆ delete_face()

void ArrangementDcel::delete_face ( Face * f )

deletes a given face f.

◆ delete_hole()

void ArrangementDcel::delete_hole ( Hole * ho )

deletes a given hole (i.e., inner CCB) ho.

◆ delete_inner_ccb()

void ArrangementDcel::delete_inner_ccb ( Inner_ccb * oc )

deletes a given inner CCB ic.

◆ delete_isolated_vertex()

void ArrangementDcel::delete_isolated_vertex ( Isolated_vertex * iv )

deletes a given isolated vertex iv.

◆ delete_outer_ccb()

void ArrangementDcel::delete_outer_ccb ( Outer_ccb * oc )

deletes a given outer CCB oc.

◆ delete_vertex()

void ArrangementDcel::delete_vertex ( Vertex * v )

deletes a given vertex v.

◆ face_handles()

unspecified_type ArrangementDcel::face_handles ( )

obtains a range over handles of the faces in dcel.

◆ faces_begin() [1/2]

Face_iterator ArrangementDcel::faces_begin ( )

obtains a begin-iterator of the faces in dcel.

◆ faces_begin() [2/2]

Face_const_iterator ArrangementDcel::faces_begin ( ) const

obtains a begin-iterator of the faces in dcel.

◆ faces_end() [1/2]

Face_iterator ArrangementDcel::faces_end ( )

obtains a past-the-end iterator of the faces in dcel.

◆ faces_end() [2/2]

Face_const_iterator ArrangementDcel::faces_end ( ) const

obtains a past-the-end iterator of the faces in dcel.

◆ halfedge_handles()

unspecified_type ArrangementDcel::halfedge_handles ( )

obtains a range over handles of the halfedges in dcel.

◆ halfedges_begin() [1/2]

Halfedge_iterator ArrangementDcel::halfedges_begin ( )

obtains a begin-iterator of the halfedges in dcel.

◆ halfedges_begin() [2/2]

Halfedge_const_iterator ArrangementDcel::halfedges_begin ( ) const

obtains a begin-iterator of the halfedges in dcel.

◆ halfedges_end() [1/2]

Halfedge_iterator ArrangementDcel::halfedges_end ( )

obtains a past-the-end iterator of the halfedges in dcel.

◆ halfedges_end() [2/2]

Halfedge_const_iterator ArrangementDcel::halfedges_end ( ) const

obtains a past-the-end iterator of the halfedges in dcel.

◆ new_edge()

Halfedge* ArrangementDcel::new_edge ( )

creates a new pair of twin halfedges.

◆ new_face()

Face* ArrangementDcel::new_face ( )

creates a new face.

◆ new_hole()

Hole* ArrangementDcel::new_hole ( )

creates a new hole (i.e., inner CCB) record.

◆ new_inner_ccb()

Hole* ArrangementDcel::new_inner_ccb ( )

creates a new inner CCB record.

◆ new_isolated_vertex()

Isolated_vertex* ArrangementDcel::new_isolated_vertex ( )

creates a new isolated vertex record.

◆ new_outer_ccb()

Hole* ArrangementDcel::new_outer_ccb ( )

creates a new outer CCB record.

◆ new_vertex()

Vertex* ArrangementDcel::new_vertex ( )

creates a new vertex.

◆ size_of_faces()

Size ArrangementDcel::size_of_faces ( ) const

obtains the number of faces.

◆ size_of_halfedges()

Size ArrangementDcel::size_of_halfedges ( ) const

obtains the number of halfedges (always even).

◆ size_of_holes()

Size ArrangementDcel::size_of_holes ( ) const

obtains the number of holes (i.e., inner CCBs).

◆ size_of_inner_ccbs()

Size ArrangementDcel::size_of_inner_ccbs ( ) const

obtains the number of inner CCBs.

◆ size_of_isolated_vertices()

Size ArrangementDcel::size_of_isolated_vertices ( ) const

obtains the number of isolated vertices.

◆ size_of_outer_ccbs()

Size ArrangementDcel::size_of_outer_ccbs ( ) const

obtains the number of outer CCBs.

◆ size_of_vertices()

Size ArrangementDcel::size_of_vertices ( ) const

obtains the number of vertices.

◆ vertex_handles()

unspecified_type ArrangementDcel::vertex_handles ( )

obtains a range over handles of the vertices in dcel.

◆ vertices_begin() [1/2]

Vertex_iterator ArrangementDcel::vertices_begin ( )

obtains a begin-iterator of the vertices in dcel.

◆ vertices_begin() [2/2]

Vertex_const_iterator ArrangementDcel::vertices_begin ( ) const