CGAL 6.1.1 - 2D Arrangements

Loading...
Searching...
No Matches
List of all members
AosDcel Concept Reference
Reference Manual » Concepts » DCEL Concepts

## 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 `AosDcel` 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 `AosDcelVertex`, `AosDcelHalfedge`, `AosDcelFace`, `AosDcelOuterCcb`, `AosDcelInnerCcb`, and `AosDcelIsolatedVertex` 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
  `AosDcelVertex`
  `AosDcelHalfedge`
  `AosDcelFace`
  `AosDcelOuterCcb`
  `AosDcelInnerCcb`
  `AosDcelIsolatedVertex`

## 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., `std::size_t`).
typedef unspecified_type | Vertex_iterator
| a bidirectional iterator over the vertices. Its value-type is `Vertex`.
typedef unspecified_type | Vertex_const_iterator
| a bidirectional iterator over the vertices. Its value-type is `Vertex`.
typedef unspecified_type | Halfedge_iterator
| a bidirectional iterator over the halfedges. Its value-type is `Halfedge`.
typedef unspecified_type | Halfedge_const_iterator
| a bidirectional iterator over the halfedges. Its value-type is `Halfedge`.
typedef unspecified_type | Face_iterator
| a bidirectional iterator over the faces. Its value-type is `Face`.
typedef unspecified_type | Face_const_iterator
| a bidirectional iterator over the faces. Its value-type is `Face`.

## 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`.

## 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.
Vertex * | new_vertex ()
| creates a new vertex.
Halfedge * | new_edge ()
| creates a new pair of twin halfedges.
Face * | new_face ()
| creates a new face.
Hole * | new_outer_ccb ()
| creates a new outer CCB record.
Hole * | new_inner_ccb ()
| creates a new inner CCB record.
Hole * | new_hole ()
| creates a new hole (i.e., inner CCB) record.
Isolated_vertex * | new_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 Function Documentation

## ◆ assign()

Face * AosDcel::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.