Definition

The concept of a halfedge data structure (abbreviated as HalfedgeDS, or HDS for template parameters) defines an edge-centered data structure capable of maintaining incidence information of vertices, edges, and faces, for example for planar maps or polyhedral surfaces. It is a combinatorial data structure, geometric interpretation is added by classes built on top of the halfedge data structure.

The data structure defined here is known as the FE-structure [9], as halfedges [6], [2] or as the doubly connected edge list (DCEL) [3], although the original reference for the DCEL [7] describes a different data structure. The halfedge data structure can also be seen as one of the variants of the quad-edge data structure [4]. In general, the quad-edge data can represent non-orientable 2-manifolds, but the variant here is restricted to orientable 2-manifolds only. An overview and comparison of these different data structures together with a thorough description of the design implemented here can be found in [5].

Each edge is represented by two halfedges with opposite orientations. Each halfedge can store a reference to an incident face and an incident vertex. For each face and each vertex an incident halfedge is stored. Reduced variants of the halfedge data structure can omit some of these incidences, for example the reference to halfedges in vertices or the storage of vertices at all. See Figure figureOptionalMethods for the incidences, the mandatory and optional member functions possible for vertices, halfedges, and faces.

The three classes Vertex, Halfedge, and Face of the halfedge data structure. Member functions with shaded background are mandatory. The others are optionally supported.

A HalfedgeDS organizes the internal storage of its items. Examples are a list-based or a vector-based storage. The HalfedgeDS exhibits most of the characteristics of the container class used internally, for example the iterator category. A vector resizes automatically when a new item exceeds the reserved space. Since resizing is an expensive operation for a HalfedgeDS in general and only possible in a well defined state of the data structure (no dangling handles), it must be called explicitly in advance for a HalfedgeDS before inserting new items beyond the current capacity. Classes built on top of a HalfedgeDS are advised to call the reserve() member function before creating new items.

Parameters

A HalfedgeDS is a class template and will be used as argument for other class templates, for example CGAL::Polyhedron_3. The template parameters to instantiate the HalfedgeDS will be provided by this other class template. Therefore, the three template parameters and their meaning are mandatory. We distinguish between the template HalfedgeDS and an instantiation of it.

Traits is a traits class that will be passed to the item types in Items. It will not be used in HalfedgeDS itself. Items is a model of the HalfedgeDSItems concept. Alloc is an allocator that fulfills all requirements of allocators for STL container classes. The rebind mechanism from Alloc will be used to create appropriate allocators internally. A default argument is mandatory for Alloc, for example, the macro CGAL_ALLOCATOR(int) from the <CGAL/memory.h> header file can be used as default allocator.

Has Models:

CGAL::HalfedgeDS_default

CGAL::HalfedgeDS_list

CGAL::HalfedgeDS_vector

See also: HalfedgeDSItems; CGAL::Polyhedron_3<Traits>; CGAL::HalfedgeDS_vertex_base<Refs>; CGAL::HalfedgeDS_halfedge_base<Refs>; CGAL::HalfedgeDS_face_base<Refs>; CGAL::HalfedgeDS_items_decorator<HDS>; CGAL::HalfedgeDS_decorator<HDS>; CGAL::HalfedgeDS_const_decorator<HDS>

Types
typedef unspecified_type	Items
	model of `HalfedgeDSItems` concept.

typedef unspecified_type	size_type
	size type.

typedef unspecified_type	difference_type
	difference type.

typedef unspecified_type	iterator_category
	iterator category for all iterators.

typedef unspecified_type	allocator_type
	allocator type `Alloc`.

typedef unspecified_type	Vertex
	model of `HalfedgeDSVertex` concept.

typedef unspecified_type	Halfedge
	model of `HalfedgeDSHalfedge` concept.

typedef unspecified_type	Face
	model of `HalfedgeDSFace` concept.

Handles and Iterators
The following handles and iterators have appropriate non-mutable counterparts, i.e., `const_handle` and `const_iterator`. The mutable types are assignable to their non-mutable counterparts. The iterators are assignable to the respective handle types. Wherever the handles appear in function parameter lists, the corresponding iterators can be used as well. Note The handle types must have a default constructor that creates a unique and always the same handle value. It will be used in analogy to `NULL` for pointers.
typedef unspecified_type	Vertex_handle
	handle to vertex.

typedef unspecified_type	Halfedge_handle
	handle to halfedge.

typedef unspecified_type	Face_handle
	handle to face.

typedef unspecified_type	Vertex_iterator
	iterator over all vertices.

typedef unspecified_type	Halfedge_iterator
	iterator over all halfedges.

typedef unspecified_type	Face_iterator
	iterator over all faces.

typedef unspecified_type	Supports_vertex_halfedge
	`Vertex::halfedge()`.

typedef unspecified_type	Supports_halfedge_prev
	`Halfedge::prev()`.

typedef unspecified_type	Supports_halfedge_vertex
	`Halfedge::vertex()`.

typedef unspecified_type	Supports_halfedge_face
	`Halfedge::face()`.

typedef unspecified_type	Supports_face_halfedge
	`Face::halfedge()`.

typedef unspecified_type	Supports_removal
	removal of individual elements.

Static Member Functions
Advanced When writing an items type, such as a user defined vertex, certain functions need to create a handle but knowing only a pointer, for example, the `this`-pointer. The following static member functions of `HalfedgeDS` create such a corresponding handle for an item type from a pointer. This conversion encapsulates possible adjustments for hidden data members in the true item type, such as linked-list pointers. Note that the user provides item types with the `Items` template argument, which may differ from the `Vertex`, `Halfedge`, and `Face` types defined in `HalfedgeDS`. If they differ, they are derived from the user provided item types. We denote the user item types with `Vertex_base`, `Halfedge_base`, and `Face_base` in the following. The fully qualified name for `Vertex_base` would be for example - assuming that the type `Self` refers to the instantiated `HalfedgeDS` - typedef typename Items::template Vertex_wrapper<Self,Traits> Vertex_wrapper; typedef typename Vertex_wrapper::Vertex Vertex_base; Implementing these functions relies on the fundamental assumption that an iterator (or handle) of the internally used container class can be constructed from a pointer of a contained item only. This is true and controlled by us for `CGAL::In_place_list`. It is true for the `std::vector` of major STL distributions, but not necessarily guaranteed. We might switch to an internal implementation if need arises.
static Vertex_handle	vertex_handle (Vertex_base *v)

static Vertex_const_handle	vertex_handle (const Vertex_base *v)

static Halfedge_handle	halfedge_handle (Halfedge_base *h)

static Halfedge_const_handle	halfedge_handle (const Halfedge_base *h)

static Face_handle	face_handle (Face_base *f)

static Face_const_handle	face_handle (const Face_items *f)

Creation
	HalfedgeDS ()
	empty halfedge data structure.

	HalfedgeDS (size_type v, size_type h, size_type f)
	storage reserved for `v` vertices, `h` halfedges, and `f` faces.

	HalfedgeDS (const HalfedgeDS< Traits, Items, Alloc > &hds2)
	copy constructor. More...

HalfedgeDS< Traits, Items, Alloc > &	operator= (const HalfedgeDS< Traits, Items, Alloc > &hds2)
	assignment operator. More...

void	reserve (size_type v, size_type h, size_type f)
	reserves storage for `v` vertices, `h` halfedges, and `f` faces. More...

Access Member Functions
Size	size_of_vertices () const
	number of vertices.

Size	size_of_halfedges () const
	number of halfedges.

Size	size_of_faces () const
	number of faces.

Size	capacity_of_vertices () const
	space reserved for vertices.

Size	capacity_of_halfedges () const
	space reserved for halfedges.

Size	capacity_of_faces () const
	space reserved for faces.

size_t	bytes () const
	bytes used for the halfedge data structure.

size_t	bytes_reserved () const
	bytes reserved for the halfedge data structure.

allocator_type	get_allocator () const
	allocator object.

Vertex_iterator	vertices_begin ()
	iterator over all vertices.

Vertex_iterator	vertices_end ()

Halfedge_iterator	halfedges_begin ()
	iterator over all halfedges

Halfedge_iterator	halfedges_end ()

Face_iterator	faces_begin ()
	iterator over all faces.

Face_iterator	faces_end ()

Insertion
Note that the vertex-related and the face-related member functions may not be provided for a `HalfedgeDS` that does not support vertices or faces respectively.
Vertex_handle	vertices_push_back (const Vertex &v)
	appends a copy of `v` to the halfedge data structure. More...

Halfedge_handle	edges_push_back (const Halfedge &h, const Halfedge &g)
	appends a copy of `h` and a copy of `g` to the halfedge data structure and makes them opposite to each other. More...

Halfedge_handle	edges_push_back (const Halfedge &h)
	appends a copy of `h` and a copy of `h->opposite()` to the halfedge data structure and makes them opposite to each other. More...

Face_handle	faces_push_back (const Face &f)
	appends a copy of `f` to the halfedge data structure. More...

Removal
Erasing single elements is optional and indicated with the type tag `Supports_removal`. The three `pop_back()` and the `clear()` member functions are mandatory. If vertices or faces are not supported for a `HalfedgeDS` the three `pop_back()` and the `clear()` member functions must be provided as null operations.
void	vertices_pop_front ()
	removes the first vertex if vertices are supported and `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	vertices_pop_back ()
	removes the last vertex.

void	vertices_erase (Vertex_handle v)
	removes the vertex `v` if vertices are supported and `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	vertices_erase (Vertex_handle first, Vertex_handle last)
	removes the range of vertices `[first,last)` if vertices are supported and `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	edges_pop_front ()
	removes the first two halfedges if `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	edges_pop_back ()
	removes the last two halfedges.

void	edges_erase (Halfedge_handle h)
	removes the pair of halfedges `h` and `h->opposite()` if `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	edges_erase (Halfedge_handle first, Halfedge_handle last)
	removes the range of edges `[first},last)` if `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	faces_pop_front ()
	removes the first face if faces are supported and `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	faces_pop_back ()
	removes the last face.

void	faces_erase (Face_handle f)
	removes the face `f` if faces are supported and `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	faces_erase (Face_handle first, Face_handle last)
	removes the range of faces `[first,last)` if faces are supported and `Supports_removal` \( \equiv\) `CGAL::Tag_true`.

void	vertices_clear ()
	removes all vertices.

void	edges_clear ()
	removes all halfedges.

void	faces_clear ()
	removes all faces.

void	clear ()
	removes all elements.

Operations with Border Halfedges
Advanced The following notion of border halfedges is particular useful where the halfedge data structure is used to model surfaces with boundary, i.e., surfaces with missing faces or open regions. Halfedges incident to an open region are called border halfedges. A halfedge is a border edge if the halfedge itself or its opposite halfedge is a border halfedge. The only requirement to work with border halfedges is that the `Halfedge` class provides a member function `HalfedgeDSHalfedge::is_border()` returning a `bool`. Usually, the halfedge data structure supports faces and the value of the default constructor of the face handle will indicate a border halfedge, but this may not be the only possibility. The `HalfedgeDSHalfedge::is_border()` predicate divides the edges into two classes, the border edges and the non-border edges. The following normalization reorganizes the sequential storage of the edges such that the non-border edges precede the border edges, and that for each border edge the latter of the two halfedges is a border halfedge (the first one might be a border halfedge too). The normalization stores the number of border halfedges, as well as the halfedge iterator where the border edges start at, within the halfedge data structure. These values will be invalid after further halfedge insertions or removals and changes in the border status of a halfedge. There is no automatic update required.
void	normalize_border ()
	sorts halfedges such that the non-border edges precede the border edges. More...

Size	size_of_border_halfedges () const
	number of border halfedges. More...

Size	size_of_border_edges () const
	number of border edges. More...

Halfedge_iterator	border_halfedges_begin ()
	halfedge iterator starting with the border edges. More...