Halfedge Data Structure

Release Note

Beginning with CGAL R2.3, this package has a new design. The old design is still available for backwards compatibility and to support older compiler, such as MSVC++6.0. However its use is deprecated and the manual pages are not converted into this new manual format. Instead, see its old documentation in the manual of deprecated packages. The two designs are not interchangeable.

Summary

A halfedge data structure (abbreviated as HalfedgeDS, or HDS for template parameters) is an edge-centered data structure capable of maintaining incidence informations 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. These classes might be more convenient to use than the halfedge data structure directly, since the halfedge data structure is meant as an implementation layer. See for example the CGAL::Polyhedron_3 class in Chapter .

The data structure provided here is known as the FE-structure [Wei85], as halfedges [Män88, BFH95] or as the doubly connected edge list (DCEL) [dBvKOS97], although the original reference for the DCEL [MP78] describes a related but different data structure. The halfedge data structure can also be seen as one of the variants of the quad-edge data structure [GS85]. 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 [Ket99].

Concepts

HalfedgeDS<Traits,Items,Alloc>
HalfedgeDSItems
HalfedgeDSVertex
HalfedgeDSHalfedge
HalfedgeDSFace

Classes

CGAL::HalfedgeDS_default<Traits,HalfedgeDSItems,Alloc>
CGAL::HalfedgeDS_list<Traits,HalfedgeDSItems,Alloc>
CGAL::HalfedgeDS_vector<Traits,HalfedgeDSItems,Alloc>

CGAL::HalfedgeDS_min_items
CGAL::HalfedgeDS_items_2

CGAL::HalfedgeDS_vertex_base<Refs>
CGAL::HalfedgeDS_halfedge_base<Refs>
CGAL::HalfedgeDS_face_base<Refs>

CGAL::HalfedgeDS_vertex_min_base<Refs>
CGAL::HalfedgeDS_halfedge_min_base<Refs>
CGAL::HalfedgeDS_face_min_base<Refs>

CGAL::HalfedgeDS_items_decorator<HDS>
CGAL::HalfedgeDS_decorator<HDS>
CGAL::HalfedgeDS_const_decorator<HDS>

Links to the Reference Sections

• HalfedgeDS<Traits,Items,Alloc>.

• HalfedgeDSFace.

• HalfedgeDSHalfedge.

• HalfedgeDSItems.

• HalfedgeDSVertex.

• HalfedgeDS_const_decorator<HDS>.

• HalfedgeDS_decorator<HDS>.

• HalfedgeDS_default<Traits,HalfedgeDSItems,Alloc>.

• HalfedgeDS_face_base<Refs>.

• HalfedgeDS_face_min_base<Refs>.

• HalfedgeDS_halfedge_base<Refs>.

• HalfedgeDS_halfedge_min_base<Refs>.

• HalfedgeDS_items_2.

• HalfedgeDS_items_decorator<HDS>.

• HalfedgeDS_min_items.

• HalfedgeDS_list<Traits,HalfedgeDSItems,Alloc>.

• HalfedgeDS_vector<Traits,HalfedgeDSItems,Alloc>.

• HalfedgeDS_vertex_base<Refs>.

• HalfedgeDS_vertex_min_base<Refs>.