= 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 [http://geometry.poly.edu/HDSTL/doc/hdstl/hdstl_introduction.htm 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.

{{{
#!html
<IMG src="http://geometry.poly.edu/HDSTL/doc/hdstl/halfedge.png" halfedge/>
<br>
<b>Figure 1. </b> 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.