CGAL 6.0.1 - 2D Arrangements
Loading...
Searching...
No Matches
ArrangementDcel Concept Reference

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.
 
typedef unspecified_type Halfedge
 the halfedge type.
 
typedef unspecified_type Face
 the face type.
 
typedef unspecified_type Outer_ccb
 the Outer CCB type.
 
typedef unspecified_type Inner_ccb
 the Inner CCB type.
 
typedef unspecified_type Hole
 the hole (i.e., Inner_ccb) type.
 
typedef unspecified_type Isolated_vertex
 the isolated vertex type.
 
typedef unspecified_type Size
 used to represent size values (e.g., size_t).
 
typedef unspecified_type Vertex_iterator
 a bidirectional iterator over the vertices.
 
typedef unspecified_type Vertex_const_iterator
 a bidirectional iterator over the vertices.
 
typedef unspecified_type Halfedge_iterator
 a bidirectional iterator over the halfedges.
 
typedef unspecified_type Halfedge_const_iterator
 a bidirectional iterator over the halfedges.
 
typedef unspecified_type Face_iterator
 a bidirectional iterator over the faces.
 
typedef unspecified_type Face_const_iterator
 a bidirectional iterator over the faces.
 

Creation

 Arr_dcel ()
 constructs an empty DCEL with one unbounded face.
 
Faceassign (const Self &other, const Face *uf)
 assigns the contents of the other DCEL whose unbounded face is given by uf, to dcel.
 

Access Functions

Size size_of_vertices () const
 obtains the number of vertices.
 
Size size_of_halfedges () const
 obtains the number of halfedges (always even).
 
Size size_of_faces () const
 obtains the number of faces.
 
Size size_of_outer_ccbs () const
 obtains the number of outer CCBs.
 
Size size_of_inner_ccbs () const
 obtains the number of inner CCBs.
 
Size size_of_holes () const
 obtains the number of holes (i.e., inner CCBs).
 
Size size_of_isolated_vertices () const
 obtains the number of isolated vertices.
 
Vertex_iterator vertices_begin ()
 obtains a begin-iterator of the vertices in dcel.
 
Vertex_iterator vertices_end ()
 obtains a past-the-end iterator of the vertices in dcel.
 
unspecified_type vertex_handles ()
 obtains a range over handles of the vertices in dcel.
 
Vertex_const_iterator vertices_begin () const
 obtains a begin-iterator of the vertices in dcel.
 
Vertex_const_iterator vertices_end () const
 obtains a past-the-end iterator of the vertices in dcel.
 
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.
 
Halfedge_iterator halfedges_end ()
 obtains a past-the-end iterator of the halfedges in dcel.
 
unspecified_type halfedge_handles ()
 obtains a range over handles of the halfedges in dcel.
 
Halfedge_const_iterator halfedges_begin () const
 obtains a begin-iterator of the halfedges in dcel.
 
Halfedge_const_iterator halfedges_end () const
 obtains a past-the-end iterator of the halfedges in dcel.
 
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.
 
Face_iterator faces_end ()
 obtains a past-the-end iterator of the faces in dcel.
 
unspecified_type face_handles ()
 obtains a range over handles of the faces in dcel.
 
Face_const_iterator faces_begin () const
 obtains a begin-iterator of the faces in dcel.
 
Face_const_iterator faces_end () const
 obtains a past-the-end iterator of the faces in dcel.
 
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.

Vertexnew_vertex ()
 creates a new vertex.
 
Halfedgenew_edge ()
 creates a new pair of twin halfedges.
 
Facenew_face ()
 creates a new face.
 
Holenew_outer_ccb ()
 creates a new outer CCB record.
 
Holenew_inner_ccb ()
 creates a new inner CCB record.
 
Holenew_hole ()
 creates a new hole (i.e., inner CCB) record.
 
Isolated_vertexnew_isolated_vertex ()
 creates a new isolated vertex record.
 
void delete_vertex (Vertex *v)
 deletes a given vertex v.
 
void delete_edge (Halfedge *e)
 deletes a given halfedge e as well as its twin.
 
void delete_face (Face *f)
 deletes a given face f.
 
void delete_outer_ccb (Outer_ccb *oc)
 deletes a given outer CCB oc.
 
void delete_inner_ccb (Inner_ccb *oc)
 deletes a given inner CCB ic.
 
void delete_hole (Hole *ho)
 deletes a given hole (i.e., inner CCB) ho.
 
void delete_isolated_vertex (Isolated_vertex *iv)
 deletes a given isolated vertex iv.
 

Member Typedef Documentation

◆ Face_const_iterator

a bidirectional iterator over the faces.

Its value-type is Face.

◆ Face_iterator

a bidirectional iterator over the faces.

Its value-type is Face.

◆ Halfedge_const_iterator

a bidirectional iterator over the halfedges.

Its value-type is Halfedge.

◆ Halfedge_iterator

a bidirectional iterator over the halfedges.

Its value-type is Halfedge.

◆ Vertex_const_iterator

a bidirectional iterator over the vertices.

Its value-type is Vertex.

◆ 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.