ArrangementDcel
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
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 unbounded 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 () const
|
returns the number of vertices.
|
|
Size
|
dcel.size_of_halfedges () const
|
returns the number of halfedges (always even).
|
|
Size
|
dcel.size_of_faces () const
|
returns the number of faces.
|
|
Size
|
dcel.size_of_holes () const
|
returns the number of holes (the number of connected components).
|
|
Size
|
dcel.size_of_isolated_vertices () const
|
| |
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.
|
|
|
Face_iterator
|
dcel.faces_begin ()
|
returns a begin-iterator of the faces in dcel.
|
|
Face_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 halfedges 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
ArrangementDcelVertex
ArrangementDcelHalfedge
ArrangementDcelFace
ArrangementDcelHole
ArrangementDcelIsolatedVertex
