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.