There are two interface channels between TTL and the application data structure: DartType and TraitsType, which are template arguments to the TTL functions.

Function templates in TTL use either `DartType`

or both `DartType`

and `TraitsType`

depending on the complexity of the algorithms. `DartType`

is used for topological queries, and `TraitsType`

is used for topological modifiers and geometric calculations. The documentation in TTL tells which functionality is needed in `DartType`

and `TraitsType`

for each function template.

TTL consists of two namespaces with generic functions: ttl contains the main interface and ttl_util contains utility functions that can also be used by the application programmer. The figure below shows the (simple) architecture of an application using TTL.

In the following we explain how `DartType`

and `TraitsType`

must be implemented as an interface to the actual data structure. For more details see literature.

The generic functions in TTL navigates in the application data structure through a "topological element" call a *dart*, which must be implemented as a struct or a class by the application programmer. A dart can be considered as a unique triple *d* = (*V*, *E*, *T*), where *V* is a node of the edge *E*, and *V* and *E* is a node and an edge of the triangle *T*; see figure a) below where a dart is indicated as an arrow.

TTL expects that three functions, which we call *alpha-iterators*, are present in the dart class: `alpha0()`

, `alpha1()`

and `alpha2()`

. These functions reposition the dart in the triangulation as shown in figure b) above and return a reference to the modified dart itself. Thus, `alpha0()`

, `alpha1()`

and `alpha2()`

change the node, the edge and the triangle of the triple *d* = (*V*, *E*, *T*) respectively.

**Note:**- The
*dart*is not part of the data structure. It is a "dynamic" element that "moves" around in the actual application data structure when the alpha-iterators are applied to it. Thus, this mechanism does not require any extra memory other than that occupied by the (few) darts that are involved in a function template of TTL that is called.

- The

In addition to the alpha-iterators, TTL expects that standard class member functions such as constructors, assignment operators and the like are also implemented in the dart class.

The following syntax is required:

class MyDart { ... public: // Constructors and destructors ... MyDart(const MyDart& dart) {...} // copy constructor MyDart& operator= (const MyDart& dart) {...} // assignment operator // comparing dart objects bool operator==(const MyDart& dart) const {...} bool operator!=(const MyDart& dart) const {...} // alpha-iterators MyDart& alpha0() {...; return *this;} MyDart& alpha1() {...; return *this;} MyDart& alpha2() {...; return *this;} };

Thus, the alpha-iterators change the content of the dart and return a reference to the dart itself.

**Note:**- Note that
`alpha2()`

must return the dart itself without changing its content (when checked with the`==`

operator) if the edge associated with the dart is at the boundary of the triangulation. The source code of ttl::isBoundaryEdge illustrates this:

- Note that

template <class DartType> bool isBoundaryEdge(const DartType& dart) { DartType dart_iter = dart; if (dart_iter.alpha2() == dart) return true; else return false; }

Consult the definition and source code of class hed::Dart, which implements the dart class for the half-edge data structure, for a thorough example.

`TraitsType`

can be a static class or a struct that contains functionality required by the functions in TTL. The purpose with `TraitsType`

is twofold:

- Let the application programmer provide topological modifiers on the actual data structure that are not resolved by TTL, e.g., remove a triangle from the triangulation,
- Let the application programmer provide basic geometric calculations and thus control the level of accuracy for such calculations.

For example, assume that a function in TTL requires a scalar product between vectors in the plane, represented as darts, with the following syntax:

real_type scalarProduct2d(const DartType& d1, const DartType& d2)

Then this function must be implemented in the traits class together with the definition of `real_type:`

struct MyTraitsType { typedef double real_type; ... static real_type scalarProduct2d(const MyDart& v1, const MyDart& v2) { return ::my_scalarProduct2d(v1,v2); } ... static bool swapTestDelaunay(const MyDart& dart) { if (dart.getEdge().isConstrained()) return false; else return ttl::swapTestDelaunay<MyTraitsType>(dart); } };

The second function, `swapTestDelaunay`

, implements the Delaunay swapping test. The function desides if the edge associated with the given dart should be swapped according to the *circumcircle* criterion (or equivalently according to the *MaxMin* angle criterion). In the example above, it is first examined if the edge is constrained, in which case false is returned. Then the test is directed back to TTL again since the circumcircle test is present there; see ttl::swapTestDelaunay. Of course, the user could also make his/her own implementation of the circumcircle test, e.g., by using robust schemes with exact arithmetic as Jonathan Richard Shewchuk does (http://www-2.cs.cmu.edu/~quake/robust.html).

This example also illustrates the syntax `functionName<MyTraitsType>`

(...arguments...) when calling function templates using a traits class.

Actually, scalar product between vectors, as well as cross product and other point and vector algebra, are also present in the the namespace ttl_util. Assume that `MyDart::x()`

and `MyDart::y()`

deliver the coordinates in the plane of the node associated with a dart. Then the scalar product in `MyTraitsType`

can be implementes as:

static real_type scalarProduct2d(const MyDart& v1, const MyDart& v2) { MyDart v10 = v1; v10.alpha0(); Dart v20 = v2; v20.alpha0(); return ttl_util::scalarProduct2d(v10.x()-v1.x(), v10.y()-v1.y(), v20.x()-v2.x(), v20.y()-v2.y()); }

Consult the definition and source code of struct hed::TTLtraits, which implements the traits class for the half-edge data structure. This example shows which members that are required in the traits class for running incremental Delaunay triangulation and removing nodes in a triangulation.

Generated on Wed Nov 17 17:44:27 2010 for TTL by 1.6.1