Constrained Delaunay Triangulation (CDT)
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:
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.
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)
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".
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.
TTL with the the half-edge data structure and its documentation, together with various examples and demos, can be downloaded from the downloads page.
Published November 16, 2009