Constrained Delaunay Triangulation (CDT)

About TTL

TTL is a generic triangulation library developed at SINTEF Applied Mathematics. TTL is generic in the sense that it does not rely on a special data structure. Thus, you can operate with your own application data structure and benefit from a variety of generic algorithms in TTL that can work directly on any data structure for triangulations.

If you do not want to bother with making your own data structure and adapt it to TTL, you can use one of the data structures that comes with TTL and use TTL as you would use any other triangulation library.

TTL is written in C++ and makes extensive use of function templates as a generic tool for the application programming interface. Moreover, it offers a new programming philosophy for triangulations based on a few clear and robust algebraic concepts which makes it easy to build applications and extend them with new functionality. The programming philosophy is somewhat like STL, The Standard Template Library, with iterator concepts. The code is limited to a few include files with the main interface in namespace ttl.

Examples of generic tools currently available are:

• Incremental Delaunay triangulation
• Constrained Delaunay triangulation
• Insert and remove nodes in a triangulation
• Searching and traversal operations
• Misc. queries for extracting information for visualisation systems etc.

Data structures distributed with TTL

A data structure represents the topology of the triangulation, i.e., how nodes, edges and triangles are glued together to form a triangulation. The well-known half-edge data structure is distributed with TTL and can be used if you do not have your own data structure. In the future we will also make other common data structures available.

Getting started

• If you just want to make a Delaunay triangulation from a set of points in the plane (with associated height values), compile and run the sample program in the file main.cpp. The program also demonstrates insertion of nodes and constraints, removal of nodes and other useful functionality in TTL. Modify the program for your needs. This program uses the half-edge data structure.

• If you want to adapt your own data structure and utilize the generic concepts of TTL, read the section Application Programming Interface to TTL (API). Implement your own DartType and TraitsType classes (or structs) interfacing your data structure similar to that of the half-edge data structure. Make a sample program similar to that of main.cpp and run Delaunay triangulation, remove/insert nodes etc., using function templates in namespace ttl.

Literature

The generic programming philosophy of TTL is published as one of the chapters the book:
Øyvind Hjelle and Morten Dæhlen. Triangulations and Applications. Springer-Verlag, 2006. (ISBN: 3-540-33260-X)

See also:
Ø. Hjelle. A Triangulation Template Library (TTL): Generic Design of Triangulation Software. Technical Report STF42 A00015, SINTEF 2000.
Full report (344 K, pdf)

Funding

The development of TTL has been supported by the Research Council of Norway under the research program 117644/223, "DYNAMAP II, Management and Use of Geodata".

Platform and compiler

TTL runs on a number of platforms, including Unix, Linux and Windows. If you have any problems it is straightforward to modify the source code. The C++ compiler must support the syntax: function< >(..,..) for calling function templates.

Download

TTL with the the half-edge data structure and its documentation, together with various examples and demos, can be downloaded from the downloads page.