The Half Edge Data Structure and Adaption to TTL
An implementation of the the well-known half-edge data structure for triangulations is documented briefly on these pages, together with adaption of this data structure to "TTL, The Triangulation Template Library". Only the class hed::Dart and the
(static) struct hed::TTLtraits are documented thoroughly. These compounds represent the interface channels between TTL and the application data structure. See [Application Programming Interface to TTL] for a general documentation of this mechanism. Follow the links to the source code for classes that are not documented in detail --- most member functions are self-explanatory.
The classes hed::Node, hed::Edge and hed::Triangulation represent the half-edge data structure shown as a class diagram in the figure below. (Here "Edge" denotes a half-edge). These classes, together with hed::Dart and hed::TTLtraits for adaption to TTL, are encapsulated in the namespace hed.
Class Diagram for the Half-Edge Data Structure
Each half-edge has a pointer to the hed::Node it starts from, a pointer to the next half-edge belonging to the same triangle
(counterclockwise), and a pointer to its "twin-edge" belonging to another triangle.
The class hed::Triangulation containts a list of (half-)edges, each of which represents one triangle in the triangulation.
In addition, the class hed::Triangulation also serves as an interface to the TTL as it implements hed::TTLtraits::swapEdge, hed::TTLtraits::splitTriangle etc., which are functions required on the application side by function templates in TTL (via the traits class).
Consult the file main.cpp for a program using TTL and the half-edge data structure.