W Randolph Franklin home page
... (old version)
Research/ home page Login

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.

  1. Find the point that is vertically farthest from the current triangulation (and that is not already one of the triangulation vertices).
  2. 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.


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 .


Jeff Thurston, Looking Back and Ahead: The Triangulated Irregular Network (TIN) GEOinformatics, Vol 6, oct/nov 2003 (not online any more).