ArrangementDcel
Definition
A doubly-connected edge-list (DCEL for short) data-structure. It consists
of three containers of records: vertices , halfedges , and faces .
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 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
