Synonyms

Triangulated terrains; TIN

Definition

A Triangulated Irregular Network (TIN) is a special case of a Digital Elevation Model (DEM).

A terrain can be mathematically modeled as a function z = f (x, y) mapping a point (x, y) in a domain D in the plane to its elevation value f (x, y). In practice, the value of function f is known at a finite set S of points within D. A DEM provides an estimated value for function f at any point (x, y) of the domain, based on the values at the points of S. A DEM consists of a subdivision of the domain into cells and of a piece-wise interpolating function defined on such cells.

A TIN is a DEM in which the domain subdivision is a triangle mesh, i.e., a set T of triangles such that: (i) the set of vertices of T is S, (ii) the interiors of any two triangles of T do not intersect, (iii) if the boundaries of two triangles intersect, then the intersection is either a common vertex, or a common edge.

Usually, a linear interpolating function is defined on the triangles of T, thus providing a continuous terrain approximation. Given a triangle t = P 1 P 2 P 3 and a point P = (x,y) inside triangle t, the following function estimates the elevation value z at P. Let P 1 = (x 1,y 1,z 1) P 2 = (x 2,y 2,z 2) and P 3 = (x 3,y 3,z 3) be the coordinates of the three vertices of t. Then,

z = z 1 − (a(x − x 1) + b(y − y 1))∕c,

where (a,b,c) are the components of the normal vector to the triangle P 1 P 2 P 3 in 3D space:

  • a = (y 1 − y 2)(z 1 − z 3) − (z 1 − z 2)(y 1 − y 3)

  • b = (z 1 − z 2)(x 1 − x 3) − (x 1 − x 2)(z 1 − z 3)

  • c = (x 1 − x 2)(y 1 − y 3) − (y 1 − y 2)(x 1 − x 3)

Key Points

TINs have been extensively studied in Geographic Information Systems (GISs), in Computational Geometry, and in Computer Graphics. Several data structures and algorithms for representing, constructing and manipulating triangle meshes have been proposed.

The quality of the terrain approximation provided by a TIN depends on the underlying triangle mesh. Note that a point set S does not define a unique triangle mesh. The most widely used triangle mesh is the Delaunay one, in which the circumcircle of each triangle does not contain any data point in its interior. This means that the triangles of a Delaunay mesh are as much equiangular as possible. It has also been proven that the use of a Delaunay mesh as the basis of a TIN improves the quality of the terrain approximation and enhances numerical stability in computations. Other triangulation criteria have been proposed which consider the triangles of the mesh in 3D space.

Often, not only points, but also lines need to be included in a TIN. Such lines may represent morphological terrain features (coast lines, rivers, ridges), man-made structures (roads, railways, gas lines), political or administrative boundaries, or contour lines. The Delaunay criterion has been modified to deal with lines in two different ways: (i) in the constrained Delaunay triangulation, the lines appear as triangle edges (but it may present sliver triangles); (ii) in the conforming Delaunay triangulation, each line is discretized by adding points on it (but a large number of points may need to be added).

TINs are used in multiresolution terrain modeling.

Cross-references

Regular Entry on Digital Elevation Models (DEM)

Regular Entry on Multiresolution Terrain Modeling