TIN is the current version of my efficient Triangulated Irregular Network computation program, for input points on a grid. Degeneracies, such as included points falling on the edge of the square, or on an existing edge, are handled. TIN uses an incremental greedy method. It stops when a predetermined maximum absolute error is reached, or when a given number of points have been included.
Due to its compact and simple data structures, TIN can process, in memory, a 10800x10800 grid of points on a PC.
In contrast to other TIN implementations, our TIN operates incrementally by repeating the following loop.
- Find the point that is vertically farthest from the current triangulation (and that is not already one of the triangulation vertices).
- Insert that point into the triangulation.
Therefore, stopping after N points have been inserted, identifies, in some sense, the N most important points in the terrain. We use this property in one of our Alternate Terrain Reps by fitting a surface to these points.
Code. This is the 2001 version. It fixes an error in the 1999 version, where edges were not always swapped properly, and cleans things up.
TIN-73
This is the Triangulated Irregular Network (TIN) program that I wrote at Simon Fraser University in the summer of 1973, at Tom Poiker's and Dave Douglas's suggestion. SFAIK, this was the first TIN program written anywhere in a GIS context. The code is in PL/1 There are also some related programs, such as a simple convex hull code.
Code .
Interview
Jeff Thurston, Looking Back and Ahead: The Triangulated Irregular Network (TIN) GEOinformatics, Vol 6, oct/nov 2003 (not online any more).