GeneralPolygonSetDcel

Navigation: Up Table of Contents Package Overview Bibliography Index Title Acknowledging CGAL

GeneralPolygonSetDcel

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 GeneralPolygonSetDcel 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, GeneralPolygonSetDcelFace , ArrangementDcelHole, and ArrangementDcelIsolatedVertex respectively.) Notice that this concept differs from the concept ArrangemenDcel only in the type Face.

Types

GeneralPolygonSetDcel::Vertex
	the vertex type.
GeneralPolygonSetDcel::Halfedge
	the halfedge type.
GeneralPolygonSetDcel::Face
	the face type.
GeneralPolygonSetDcel::Hole
	the hole type.
GeneralPolygonSetDcel::Isolated_vertex
	the isolated vertex type.

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

GeneralPolygonSetDcel::Vertex_iterator
	a bidirectional iterator over the vertices. Its value-type is Vertex.
GeneralPolygonSetDcel::Halfedge_iterator
	a bidirectional iterator over the halfedges. Its value-type is Halfedge.
GeneralPolygonSetDcel::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

GeneralPolygonSetDcel 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 () 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.

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>