HalfedgeDS<Traits,Items,Alloc>

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.

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 [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 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].

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 24.2 for the incidences, the mandatory and optional member functions possible for vertices, halfedges, and faces.

A HalfedgeDS<Traits,Items,Alloc> organizes the internal storage of its items. Examples are a list-based or a vector-based storage. The HalfedgeDS<Traits,Items,Alloc> 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<Traits,Items,Alloc> 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<Traits,Items,Alloc> before inserting new items beyond the current capacity. Classes built on top of a HalfedgeDS<Traits,Items,Alloc> are advised to call the reserve() member function before creating new items.

Parameters

A HalfedgeDS<Traits,Items,Alloc> 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<Traits,Items,Alloc> will be provided by this other class template. Therefore, the three template parameters and their meaning are mandatory. We distinguish between the template HalfedgeDS<Traits,Items,Alloc> 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<Traits,Items,Alloc> itself. Items is a model of the HalfedgeDSItems concept. Alloc is a standard 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.

Types

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.

Creation

Access Member Functions

The following member functions return the non-mutable iterator if hds is declared const.

Insertion

Note that the vertex-related and the face-related member functions may not be provided for a HalfedgeDS<Traits,Items,Alloc> that does not support vertices or faces respectively.

Removal

Erasing single elements is optional and indicated with the type tag Supports_removal. The pop_back and the clear member functions are mandatory. If vertices or faces are not supported for a HalfedgeDS<Traits,Items,Alloc> the pop_back and the clear member functions must be provided as null operations.

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>

Implementation

Classes parameterized with a halfedge data structure, such as CGAL::Polyhedron_3, need to declare a class template as one of its template parameters for the HalfedgeDS<Traits,Items,Alloc>. For compilers not supporting this (i.e. the flag CGAL_CFG_NO_TMPL_IN_TMPL_PARAM is set), the following workaround is required, which defines a HalfedgeDS<Traits,Items,Alloc> as a normal class that contains a member class template named HDS, which is the actual halfedge data structure as defined here. The following program fragment illustrates this workaround:

#ifndef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
    template <class Traits, class Items, class Alloc> 
    class HalfedgeDS {
    public:
        typedef HalfedgeDS<Traits,Items,Alloc> Self;
        HalfedgeDS_vector(); // constructors
#else
    struct HalfedgeDS {
    template <class Traits, class Items, class Alloc> 
    class HDS {
    public:
        typedef HDS<Traits,Items,Alloc> Self;
        HDS(); // constructors
#endif
        // ... further member functions. Self denotes the HalfedgeDS.
    };
#ifdef CGAL_CFG_NO_TMPL_IN_TMPL_PARAM
    };
#endif