Halfedge Data Structure Template Library
0. Introduction
In this project, we will develop a generic halfedge data structure template library. A brief overview of halfedge data structures by Herve Bronnimann is available here (Sections 1-3). In this project, we will follow the same design principle described in the introduction document, with various modifications and additions.
The purpose of this document is to share the design decisions with the Boost community, and receive feedback. Please feel free to comment and discuss possible ideas as all feedback are welcome.
1. Halfedge Data Structure Concepts
We give the concepts of halfedges in the following sections. First we analyze the halfedge data structure traits, which define various choices about the HDS and lets us configure the halfedges. Later we present the Halfedge data structure and design details.
1.0. HDS Traits
We define the HDS traits concept as a class, which provides all the component types for HDS and defines the choices. In this class the choices about the HDS is two folds:
- The mandatory types: such as the type of the HDS, iterators for halfedges.
- The optional types: such as enabling facets, enabling vertex types, using extra HDS access methods additional to the mandatory types.
The optional types are added to data structure only if they are explicitly defined, otherwise based on zero overhead principle no storage is assigned for them. In this traits class we discuss the advantages and disadvantages of each choice, including runtime options and storage options.
Figure 1. Halfedge data structure with all available features.
Figure 1 shows all available access methods and pointers for a halfedge data structure. However, not all of these have to be used in order to implement a HDS. Below we define the types in the HDS traits class, and discuss the options.
| Type | Mandatory or optional | Allocates memory | Definition |
| Vertex type | optional | Only if defined | Defines the type of vertex stored in the HDS. |
| Vertex handle | optional | Only if defined | Defined only if vertex type is defined. Defines an iterator to access vertices. |
| Vertex const handle | optional | Only if defined | Same as vertex handle, only iterator is defined as non mutable. |
| Halfedge type | mandatory | yes, based on #of types used | Defines the type of the halfedges stored in HDS (such as forward, backward, bidirectional etc.). |
| Halfedge handle | mandatory | yes, based on #of types used | Defines an iterator to access halfedges, based on halfedge type. |
| Halfedge const handle | mandatory | yes, based on #of types used | Same as halfedge handle, only non mutable. |
| Facet type | optional | Only if defined | Defines the type of the facet. |
| Facet handle | optional | Only if defined | Defined if only facet type is also defined. Defines an iterator to access facets. |
| Facet const handle | optional | Only if defined | Same as facet handle, only non mutable. |
| Hole type | optional | Only if defined | Requires facets are defined. By default we assume HDS has no holes. If set means that HDS supports holes. |
| Hole handle | optional | Only if defined | Requires Hole type defined. Defines an iterator to access holes in a facet. |
| Hole const handle | optional | Only if defined | Same as hole handle, only non mutable. |
HDS types and basic operations are defined as:
- Forward_hds: Defines that the rotations around vertices are clockwise and rotation around facets are counter clockwise. Requires at least one of next_at_facet(), next_at_source(), next_at_target() halfedge operations are implemented.
- Backwards_hds: Defines that the rotations around vertices are counter clockwise and rotation around facets are clockwise. Requires at least one of prev_at_facet(), prev_at_source(), prev_at_target() halfedge operations are implemented.
- Bidirectional_hds: Defines that rotations can be on both directions for both vertices and facets. Requires that at least one operation from forward_hds and backward_hds each is defined.
1.1. Halfedge Data Structure
This class provides the halfedges, access to halfedges, operations on halfedges based on the configuration done using the traits. HDS class has the following operations:
| Name | Definition |
| create new edge | Creates two halfedges, as halfedges are required to be created by their opposite. |
| delete edge | Deletes a halfedge and its opposite |
| opposite edge | Gets the opposite edge of the given halfedge |
| Default constructor | Create an empty HDS. |
| copy constructor | To create a new HDS. |
| Halfedge container | Grant access to the container. |
| Euler operations | Various Euler operations on the HDS. This contains multiple methods. |
2. Algorithms
A set of algorithms on entities obeying the defined concepts (in the intrusive fashion). More details coming soon.
3. Implementation details
An homemade implementation of the concepts (various HDS) as well as adapters for Leda and CGAL. More details coming soon.
4. Examples
Examples using halfedge data structures for Voronoi / Meshing and for 2D Polygonal Modeling. More details coming soon.
