CGAL  Halfedge Data Structures

The concept of a halfedge data structure (abbreviated as HalfedgeDS
, or HDS
for template parameters) defines an edgecentered 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 FEstructure [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 quadedge data structure [4]. In general, the quadedge data can represent nonorientable 2manifolds, but the variant here is restricted to orientable 2manifolds 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.
HalfedgeDS
organizes the internal storage of its items. Examples are a listbased or a vectorbased 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.
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 nonmutable counterparts, i.e., The mutable types are assignable to their nonmutable 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.
 
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 The following static member functions of 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  
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 vertexrelated and the facerelated member functions may not be provided for a  
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 The three  
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  
void  normalize_border () 
sorts halfedges such that the nonborder 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...  
HalfedgeDS< Traits, Items, Alloc >::HalfedgeDS  (  const HalfedgeDS< Traits, Items, Alloc > &  hds2) 
copy constructor.
hds2
contains no dangling handles. Halfedge_iterator HalfedgeDS< Traits, Items, Alloc >::border_halfedges_begin  (  ) 
halfedge iterator starting with the border edges.
The range [halfedges_begin(), border_halfedges_begin()
) denotes all nonborder edges. The range [border_halfedges_begin(), halfedges_end()
) denotes all border edges.
normalize_border()
has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then. Halfedge_handle HalfedgeDS< Traits, Items, Alloc >::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.
Returns a handle of the copy of h
.
Halfedge_handle HalfedgeDS< Traits, Items, Alloc >::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.
Returns a handle of the copy of h
.
h>opposite()
denotes a halfedge. Face_handle HalfedgeDS< Traits, Items, Alloc >::faces_push_back  (  const Face &  f) 
appends a copy of f
to the halfedge data structure.
Returns a handle of the new face.
void HalfedgeDS< Traits, Items, Alloc >::normalize_border  (  ) 
sorts halfedges such that the nonborder edges precede the border edges.
For each border edge that is incident to a face, the halfedge iterator will reference the halfedge incident to the face right before the halfedge incident to the open region.
HalfedgeDS<Traits,Items,Alloc>& HalfedgeDS< Traits, Items, Alloc >::operator=  (  const HalfedgeDS< Traits, Items, Alloc > &  hds2) 
assignment operator.
hds2
contains no dangling handles. void HalfedgeDS< Traits, Items, Alloc >::reserve  (  size_type  v, 
size_type  h,  
size_type  f  
) 
reserves storage for v
vertices, h
halfedges, and f
faces.
If all capacities are already greater or equal than the requested sizes nothing happens. Otherwise, the halfedge data structure will be resized and all handles, iterators and circulators are invalid.
Size HalfedgeDS< Traits, Items, Alloc >::size_of_border_edges  (  )  const 
number of border edges.
If size_of_border_edges()
is equal to size_of_border_halfedges()
all border edges are incident to a face on one side and to an open region on the other side.
normalize_border()
has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then. Size HalfedgeDS< Traits, Items, Alloc >::size_of_border_halfedges  (  )  const 
number of border halfedges.
An edge with no incident face counts as two border halfedges.
normalize_border()
has been called and no halfedge insertion or removal and no change in border status of the halfedges have occurred since then. Vertex_handle HalfedgeDS< Traits, Items, Alloc >::vertices_push_back  (  const Vertex &  v) 
appends a copy of v
to the halfedge data structure.
Returns a handle of the new vertex.