[DM-02-010] Triangular Irregular Network (TIN) Models

Lim, J. and Pilesjö, P. (2022). Triangulated Irregular Network (TIN) Models. The Geographic Information Science & Technology Body of Knowledge (2nd Quarter 2022 Edition). John P. Wilson (Ed.).  DOI: https://doi.org/10.22224/gistbok/2022.2.7.

This Topic is also available in the following editions: 

DiBiase, D., DeMers, M., Johnson, A., Kemp, K., Luck, A. T., Plewe, B., and Wentz, E. (2006). The Triangulated Irregular Network (TIN) Model. The Geographic Information Science & Technology Body of Knowledge. Washington, DC: Association of American Geographers.

1. Definitions
2. Introduction
3. How to Create Triangles
4. Characteristics of Facets
5. TIN Storage Formats
6. TIN Analyses and Applications

1. Definitions

Aspect: Azimuthal direction of sloping facet

Nodes: Points representing a sampled elevation value. These are the vertices of the triangles in a TIN.

Facet: A triangular face of a TIN

Edge: A line connecting two nodes

Contours: Lines that connect points of equal elevation. This may be stored in a raster or vector format.

Circumcircle (of a triangle): A circle passing through all the nodes of the triangle.

Delaunay triangulation: A triangulation method which ensures that no point lies within the circumcircle of any triangles in the network

Voronoi diagram: A partition of a plane into polygons such that each polygon has only one generating point. Any point in each polygon is close to its generating point than any other.

2. Introduction

There are different ways of representing continuous surfaces in a GIS environment. For example, the data (e.g. elevation values) can be stored in vector form as either points with coordinate pairs (Figure 1A), or contours where nodes that make up these lines are stored as coordinate pairs (Figure 1B). Alternatively, continuous surfaces may be represented by a grid in the raster format, where each cell represents one value (Figure 1C).

Another way of representing a continuous surface is by applying a Triangular Irregular Network (TIN) (Figure 1D). Introduced in the 1970s (Peucker et al., 1976), the surface is made up of adjacent, non-overlapping triangles. Typically, the triangulation of a point cloud (x, y, z data) or grids serve as the basis for generating TINs. In this data structure, each point is connected by non-overlapping lines (edges) to create planes of contiguous triangles of varied sizes (hence the name irregular).

Figure 1. An illustration of different ways of representing the same continuous surface at the same scale and extent. A. LiDAR point cloud data. B. Contours derived from the point cloud. C. Raster derived from LiDAR. D. TIN derived from the point cloud shown in A. LiDAR point cloud and raster data were directly obtained from U.S. Geological Survey. Source: authors.

The main advantages of the TIN model are as follows:

• It is not sensitive to varying data scales, meaning that smaller triangles (i.e. more points) can be used where the surface is complex (Figure 2A) , and larger triangles (i.e. less points) where the surface is simpler (Figure 2B). This makes TINs suitable for discontinuities in a surface, such as ridges and breaks of slope. Additionally, TINs allow for flexibility in the level of detail for the modelled surface. This level of detail depends on the scale of processes and features to be presented (Wolf, 2004). In this sense, TINs are more reliable than e.g. the raster format when it comes to specific surface details (Kidner & Smith, 1993).
•  It is efficient in terms of data storage. The irregularity of TIN allows for lesser points to be used to represent smooth terrains. In this sense, TINs are more efficient than the raster format, where all cells are allocated a value, even if it is the same as the value of neighbouring cells.

Figure 2. A comparison between an area with highly variable topography (A) and less variable topography (B). This difference in surface variability corresponds to the differences in the number of triangles. Data obtained from U.S. Geological Survey. Source: authors.

Some disadvantages and challenges associated with TINs are that:

• The complexity of the TIN’s data structure makes it less efficient than other formats (eg. raster) when it comes to data processing, and more time consuming and expensive to construct.
• It is challenging to compare TIN surfaces, since for different sets of points, different TINs will arise.
• It can be difficult to integrate TINs with other data types in a GIS environment
• Representing topographical breaklines is challenging since it can depend on the location of sampling points and and the methods used to sample points
• TIN storage requirements increase with terrain complexity due to the manner in which the triangles are stored; a single triangle utilises the same storage space as 10 raster cells (Kidner & Smith, 1993).

Quality can be measured and controlled to ensure that thin triangles do not result from the triangulation process, which can introduce errors. In some sense, this is also a measure of compactness since smaller triangles may be associated with better quality TINs due to a higher spatial detail.

To address the balance between data processing efficiency and integrity, multi-resolution TINs were introduced. As an integrated TIN model with different resolutions, it allows for terrains to be represented at varying resolutions depending on the requirements of the studied phenomena. In this sense, it offers more flexibility than single-resolution TINs. A detailed overview of methods used to generate these multi-resolution TINs is given by Heckbert & Garland (1997).

3.  How to Create Triangles

TINs are constructed via triangulation, using points, lines, or polygons as input data. Prior to the triangulation process, choices must be made on 1) how to select sampling points, 2) how to connect these points into triangles and 3) how to model the surface of each triangle. 

3.1 Selecting Sampling Points

Broadly speaking, the selection of sampling points involves establishing the importance of elevation points and rules to cease this selection procedure when a certain criteria is met. Points are deemed important when their elevations cannot be interpolated ‘closely’ from its neighbours. Among existing methods, the selection of points is terminated when a certain number of points have been selected, or when there are no more points that fulfils a pre-defined level of importance.

Numerous methods have been proposed to address the selection of points. For example, Fowler and Little’s (1979) algorithm is based on the idea that a terrain surface can be characterized by ‘surface specific’ points which represent features such as peaks and pits. The Very Important Points algorithm (Chen & Guevara, 1987) evaluates the importance of points by calculating how well it is estimated by its 8-grid neighbours. A higher importance is assigned to points with a greater difference between its actual and estimated elevation. At the end, points that are regarded as ‘least important’ are discarded.

3.2 Triangulation

Among the various triangulation methods is the commonly used Delaunay triangulation (Delaunay, 1934). As the straight-line dual of a Voroni diagram, it is constructed by connecting points. Many algorithms have been proposed for this triangulation, such as the Divide-and-Conquer algorithm (Lewis & Robinson, 1978) and the Convex Hull Insertion (Tsai & Vonderohe, 1991). Regardless of the algorithm, the salient features of the resulting triangulation are as follows:

• The smallest angle in each triangle is maximized
• No point lies within the circumcircle of any triangles in the network
• It is mostly unique, except when more than three neighbouring points are co-circular on the Euclidean plane

Although the Delaunay triangulation is a classic triangulation method associated with the construction of TINs, it may be too simple for certain applications. For example, it may not always capture hydrographic and landscape features that are crucial within the domain of hydrological modelling.

4. Characteristics of Facets

Each triangular facet represents the geometric characteristics of that part of the surface. This corresponds to a planar triangle with a specific slope and aspect, which are the same across the whole triangle/facet. So, every point on the facet, including the three vertices, are represented by a plane. Consequently, the equation of such a TIN triangle/facet/surface is that of a plane, where Z(x,y) represents the elevation at point (x,y):

Z (x, y) = b0 + b1x + b2y

The x, y and z coordinates of the three nodes of a facet are used to derive the coefficients b0, b1, and b2 by solving a system of equations. This interpolated facet may differ from the actual surface, depending how it was interpolated. The accuracy of this interpolated surface is highly dependent on the number of points over an area, their spatial distribution and the surface variability; for example, larger triangles over a relatively flat area would lead to better predictions, as opposed to larger triangles over a highly variable surface.

Parameters such as slope, aspect and surface area may be derived from TINs. The derivation of these parameters are typically facet-oriented, meaning that they are estimated individually for each facet. For example, slope and aspect, in degrees, can be estimated as follows:

However, it should be noted that these estimations have limitations. Since each triangular facet is an interpolated surface, the only parts of the surface that are likely to be completely accurate would be the three vertices/corner points. Additionally, estimations of basic terrain derivatives and second-order terrain derivatives – such as the profile, maximum, minimum and gaussian curvatures – are difficult to derive from triangular facets (Minár et al. 2013).

There have been attempts to obtain these derivatives using the triangle vertices (Hu et al., 2021). This work showed that slope and aspect results were more accurate compared to facet-based methods, and had a lower error sensitivity than employing a facet-based method. More recently, Hu et al. (2022) has shown land surface curvature can be calculated based on TIN facets and vertices. From this perspective, TINs could possibly serve a similar function as raster DEMs in digital terrain analyses.

It is important to emphasize that there are numerous factors that may influence potential differences between vertex-based and facet-based methods. These can include the source data, the triangulation method, sampling points and study region.

5. TIN Storage Format

TIN databases are stored in vector format, and contain the following geometric objects:

• Triangles that are stored as polygons. Each of them has a unique number.
• Points which represent the vertices/angles of each triangle. These are known as nodes.
• Lines which connect two nodes. These are known as edges and are connected to at least two edges.

Stored along with the data are also topological relationships between adjacent triangles. Hence, the complete data structure includes the triangle number, the number of its neighbouring triangles, and data files displaying the list of points, edges, data value, and coordinates (Figure 3).

Figure 3. TIN Data Structure. Source: authors.

6. TIN Analyses and Applications

Perhaps the most common application of the TIN model lies in topographical modelling, which relates to elevation changes in an area. Here, TIN models are used to estimate topographically related information. However, it is important to note that modelling any natural surface by a mathematical model is difficult. From this perspective, TINs are a simplified and optimized way to represent a terrain.

In the same vein, TINs have also been used in landscape evolution modelling as pioneered by Braun & Sambridge (1997). Many of such models are partially or wholly based on DEMs represented as TINs. Tucker et al. (2001) developed the channel-hillslope integrated landscape development model (CHILD) to quantify topographical and stratigraphical evolution resulting from erosion and sediment transport. Thereafter, an algorithm was further proposed by Clevis et al. (2006) using the same model to address the issue of linking TINs and raster discretization schemes; this was also applicable to the modelling of subsurface fluvial architecture and meanders.

TINs are also an important component in digital terrain analysis (DTA). TIN-based DEMs are used to represent the subsurface in catchment hydrology process models, which include the Penn State integrated hydrologic model (Qu & Duffy, 2007) and real-time integrated basin simulator (Ivanov et al., 2004a). It has been argued that TIN-based DEMs surpass raster-based DEMs in the high-precision hydrological modelling of small basins when considering sampling point density (Ivanov et al., 2004b).