The TIN Model

Originally appeared as Unit 39 of the NCGIA Core Curriculum, 1990 version
Compiled with assistance from Thomas K. Poiker, Simon Fraser University
Originally posted to the web by Brian Klinkenberg, University of British Columbia

This unit is part of the NCGIA Core Curriculum in Geographic Information Science. These materials may be used for study, research, and education, but please credit the author, Thomas K. Poiker, and the project, NCGIA Core Curriculum in GIScience. All commercial rights reserved. Copyright 1990 by UC Regents.

Your comments on these materials are welcome. A link to an evaluation form is provided at the end of this document.

Full Table of Contents

The TIN Model

1. Introduction

• the Triangulated Irregular Network model is a significant alternative to the regular raster of a DEM, and has been adopted in numerous GISs and automated mapping and contouring packages
• the TIN model was developed in the early 1970's as a simple way to build a surface from a set of irregularly spaced points
• several prototype systems were developed in the 1970's
• commercial systems using TIN began to appear in the 1980's as contouring packages, some embedded in GISs

1.1. The TIN model

• irregularly spaced sample points can be adapted to the terrain, with more points in areas of rough terrain and fewer in smooth terrain
  • an irregularly spaced sample is therefore more efficient at representing a surface
• in a TIN model, the sample points are connected by lines to form triangles
  • within each triangle the surface is usually represented by a plane
• by using triangles we ensure that each piece of the mosaic surface will fit with its neighboring pieces - the surface will be continuous - as each triangle's surface would be defined by the elevations of the three corner points
• it might make sense to use more complex polygons as mosaic tiles in some cases, but they can always be broken down into triangles
  • for example, if a plateau is eroded by gullies, the remaining plateau would be a flat (planar) area bounded by an irregular, many-sided polygon. In the TIN model it would be represented by a number of triangles, each at the same elevation

  

• for vector GISs, TINs can be seen as polygons having attributes of slope, aspect and area, with three vertices having elevation attributes and three edges with slope and direction attributes
• the TIN model is attractive because of its simplicity and economy
• in addition, certain types of terrain are very effectively divided into triangles with plane facets
  • this is particularly true with fluvially-eroded landscapes
  • however, other landscapes, such as glaciated ones, are not well represented by flat triangles
  • triangles work best in areas with sharp breaks in slope, where TIN edges can be aligned with breaks, e.g. along ridges or channels

1.2. Creating TINs

• despite its simplicity, creating a TIN model requires many choices:
  • how to pick sample points
    • in many cases these must be selected from some existing, dense DEM or digitized contours
    • normally, a TIN of 100 points will do as well as a DEM of several hundred at representing a surface
  • how to connect points into triangles
  • how to model the surface within each triangle
    • this is almost always resolved by using a plane surface
    • however, if the surface is contoured, the contours will be straight and parallel within each triangle, but will kink sharply at triangle edges

• consequently, some implementations of TIN represent the surface in each triangle using a mathematical function chosen to ensure that slope changes continuously, not abruptly, at the edges of the triangle

2. How to pick points

• given a dense DEM or set of digitized contours, how should points be selected so that the surface is accurately represented?
  • consider the following 3 methods for selecting from a DEM
  • all of them try to select points at significant breaks of the surface
    • such breaks are common on terrain, absent on smooth mathematical surfaces

2.1. Fowler and Little algorithm

• this approach is based on the concept of surface-specific points which play a specific role in the surface
  • e.g. represent features such as peaks and pits

2.1.1. Procedure

• first examine the surface using a 3x3 window, looking at a small array of 9 points at each step
  • label the 8 neighbors of the central point + if higher, - if lower
  • a point is a peak if its 8 neighbors are all lower (8 +s)
  • a point is a pit if its 8 neighbors are all higher (8 -s)
  • a point is a pass if the +s and -s alternate around the point with at least two complete cycles, e.g

       + + - 
       -   - 
       - + + (2 cycles)

    or + - +
       -   - 
       + - + (4 cycles)

• next the surface is examined using a 2x2 window
  • except at the edges, every point appears in four positions of the window
  • a point is a potential ridge point if it is never lowest in any position of the window
  • a point is a potential channel point if it is never highest in any position of the window
• then starting at a pass, search through adjacent ridge points until a peak is reached
  • similarly, search from the pass through adjacent channel points until a pit is reached

2.1.2. Finishing the TIN

• the result of this process is a connected set of peaks, pits, passes, ridge lines and channel lines
  • Fowler and Little recommend that the number of points in each ridge and channel line be reduced by thinning using a standard thinning algorithm
  • it may be desirable to add additional points from the DEM which are not on ridges or channels if we can significantly reduce any substantial differences from the real surface by doing so
• triangles are built between all selected points
• the resulting surface will differ from the original DEM, perhaps substantially in some areas

2.1.3. Comments

• the Fowler and Little algorithm is complex
  • performs better on some types of landscape than others, particularly where there are sharp breaks of slope along ridges, and where channels are sharply incised
  • it may require substantial "fine tuning" to work well

2.2. VIP (Very Important Points) Algorithm

• unlike the previous algorithm which tries to identify the major features of the terrain, VIP works by examining the surface locally using a window
• this is a simplification of the technique used in ESRI's ARC/INFO

2.2.1. Procedure

• each point has 8 neighbors, forming 4 diametrically opposite pairs, i.e. up and down, right and left, upper left and lower right, and upper right and lower left
• for each point, examine each of these pairs of neighbors in turn
  • connect the two neighbors by a straight line, and compute the perpendicular distance of the central point from this line

• average the four distances to obtain a measure of "significance" for the point

• delete points from the DEM in order of increasing significance, deleting the least significant first
  • this continues until one of two conditions is met:
    • the number of points reaches a predetermined limit
    • the significance reaches a predetermined limit

2.2.2. Comments

• because of its local nature, this method is best when the proportion of points deleted is low
• because of its emphasis on straight lines, and the TIN's use of planes, it is less satisfactory on curved surfaces

2.3. Drop heuristic

• this method treats the problem as one of optimization
  • given a dense DEM, find the best subset of a predetermined number of points such that when the points are connected by triangles filled with planes, the TIN gives the best possible representation of the surface

2.3.1. Procedure

• start with the full DEM
  • examine each point in turn
  • temporarily drop the point and modify the surrounding triangles accordingly

• find the triangle containing the dropped point
• measure the difference between the elevation of the point, and the elevation of the new surface at the point
• restore the dropped point, storing the calculated elevation difference

• continue the process dropping each point in turn
• when all the points have been dropped, remove the point which produced the least difference and start the process again

2.3.2. Comments

• the TIN will likely be more accurate if the differences are measured not only for the point being dropped, but for all previously dropped points lying within the modified triangles as well, but this would be time- consuming
• rather than select points from the DEM, the best solution (in the sense of producing the best possible TIN for a given number of points) may be to locate TIN points at locations and elevations not in the original raster
  • these points may be chosen from air photographs or ground surveys

3. How to triangulate a TIN

• having selected a set of TIN points, these will become the vertices of the triangle network
  • there are several ways to connect vertices into triangles
• "fat" triangles with angles close to 60 degrees are preferred since this ensures that any point on the surface is as close as possible to a vertex
  • this is important because the surface representation is likely most accurate at the vertices
• consider the following two methods for building the triangles
  • in practice almost all systems use the second

3.1. Distance ordering

3.1.1. Procedure

• compute the distance between all pairs of points, and sort from lowest to highest
  • connect the closest pair of points
  • connect the next closest pair if the resulting line does not cross earlier lines
• repeat until no further lines can be selected
• the points will now be connected with triangles
  • this tends to produce many skinny triangles instead of the preferred "fat" triangles

3.2. Delaunay triangulation

• by definition, 3 points form a Delaunay triangle if and only if the circle which passes through them contains no other point

• another way to define the Delaunay triangulation is as follows:
  • partition the map by assigning all locations to the nearest vertex
  • the boundaries created in this process form a set of polygons called Thiessen polygons or Voronoi or Dirichlet regions 
  • Figure 1 - Delaunay triangles from Thiessen polygons
  • two vertices are connected in the Delaunay triangulation if their Thiessen polygons share an edge
• this method produces the preferred fat triangles
• the boundary edges on the Delaunay network form the Convex Hull, which is the smallest polygon to contain all of the vertices

3.2.1. Procedure

• there are several techniques for building the triangles: 1. since the convex hull will always be part of the Delaunay network
  • start with these edges and work inwards until the network is complete 2. connect the closest pair which by definition must be a Delaunay edge
  • search for a third point such that no other point falls in the circle through them
  • continue working outward from these edges for the next closest point

3.2.2. Problems

• Delaunay triangles are not hierarchical
  • they cannot be aggregated to form bigger triangles
  • if they are divided into smaller triangles, the results tend to be poorly shaped (not "fat")

4. Alternative methods of creating TINs

4.1. Break lines

• methods presented above concentrate on finding TIN vertices, then connecting them with triangles
• a major advantage of TINs is their ability to capture breaks of slope, if edges can be aligned with known ridges or channels
• this requires a different approach, where "breaklines" are incorporated into the triangle network as edges after the points have been triangulated
  • the result is generally non-Delaunay, i.e. an edge need not be an edge in the Delaunay network of the vertices
• this approach is now incorporated into some TIN software, e.g. the ARC/INFO TIN module

4.2 TINs from contours

• contours are a common source of digital elevation data
• rather than convert from contours to a grid (DEM) and then to a TIN, it is more direct to obtain the TIN from contours directly
• a TIN can be created by selecting points from the digitized contour lines
• selection may create a triangle with three vertices on the same contour (at the same elevation)
• such a "flat triangle" has no defined aspect, causes problems in modeling runoff
  • several ways of avoiding this problem have been devised

5. Storing TINs

• there are basically two ways of storing triangulated networks: 1. Triangle by triangle 2. Points and their neighbors
• Figure 2 - Storing TINs

5.1. Triangle by triangle

• in this case, a record usually contains:
  • a reference number for the triangle
  • the x,y,z-coordinates of the three vertices
  • the reference numbers of the three neighboring triangles
• since a vertex participates in, on the average, six triangles, repetition of coordinates can be avoided by creating a separate vertex file and referencing them in the triangle files

5.2. Points and their neighbors

• the alternative is to store for every vertex:
  • an identification number
  • the xyz coordinates
  • references (pointers) to the neighboring vertices in clockwise or counter-clockwise order
• this structure was the original TIN structure (Peucker et al, 1978)

5.3. Comparison of the two structures

• both structures are necessary, depending on the purpose
  • slope analysis needs the first
  • contouring and other traversing procedures work best with the second
• as long as one can be extracted from the other in close to linear time (i.e., without an exhaustive search per point), either will do
• the second generally needs less storage space
  • however, the savings within different TIN structures is minor compared to the reduction of points from the regular grid to the triangular network

6. Algorithms on TINSs

6.1. Slope and aspect

• compared to the DEM, it is simple to find slope and aspect at some location using a TIN - we simply find the slope and aspect attributes of the containing triangle

6.2. Contouring

• Figure 3 - Contouring TINs

6.2.1. Example: find the 100 m contour

• begin by determining, with a different algorithm, that an edge intersects the contour level of 100 meters
  • the vertex above the contour level is the "reference point" (r) and the one below the "sub-point" (s)
  • establish a position in memory for the pair of points which we will call present_edge
• computing P1, the first contour point, is then a trivial linear calculation
• now shift over to the traversing procedure
  • look at the third vertex in the triangle and ask whether it is a reference or a sub-point by testing whether it is above or below the contour level
  • the result replaces the appropriate value in present_edge and the next contour point is calculated.
• the vertices in present_edge represent a second triangle whose third vertex is the next candidate

6.3. Finding Drainage Networks

• two approaches can be used to find drainage networks and watersheds:

  1. treat each triangle as a discrete element

  • as with the DEM, water is passed from one triangle to another, selecting the neighbor in the direction of steepest slope in each case

  

  2. treat the surface as a mosaic of planes

  • two forms of flow occur - channel and overland
  • water flows over each triangle as a continuous sheet, and collects along edges
  • in this model, it is possible for water to collect in a "channel" between two triangles, flow to a vertex, and flow into the top of one or more triangles
    • in this case we must allow channel flow down the line of steepest slope from the apex of these triangles

    

  • if there is more than one such triangle, then a bifurcation is implied, with water flowing in more than one direction from the apex, and into more than one drainage basin
    • this is awkward, as we no longer have a clear definition of watershed

7. References

Chen, Z., and J.A. Guevara, 1987. "Systematic selection of very important points (VIP) from digital terrain models for construction triangular irregular networks," Proceedings, AutoCarto 8, ASPRS/ACSM, Falls Church, VA, pp. 50-56. A description of ESRI's VIP approach to constructing a TIN.

Fowler, R.J., and J.J. Little, 1979. "Automatic extraction of irregular network digital terrain models," Computer Graphics 13:199-207.

Heller, M., 1986. "Triangulation and Interpolation of Surfaces," in R. Sieber and K. Brassel (eds), A Selected Bibliography on Spatial Data Handling: Data Structures, Generalization and Three-Dimensional Mapping, Geo-Processing Series, vol 6, Department of Geography, University of Zurich, pp 36 - 45. A good overview with literature, mainly on triangulation.

Mark, D. M., 1975. "Computer Analysis of Topography: A Comparison of Terrain Storage Methods," Geografisker Annaler 57A:179-188. A quantitative comparison of regular grids and triangulated networks.

Mark, D.M., 1979. "Phenomenon-Based Data-Structuring and Digital Terrain Modelling," Geo-Processing 1:27-36. A very interesting conceptual article proposing a phenomenon-based approach to data structuring. Such an approach has to involve expert knowledge of the phenomenon.

Peucker, T.K., R.J. Fowler, J.J. Little and D.M. Mark, 1978. "The Triangulated Irregular Network," Proceedings, American Society of Photogrammetry: Digital Terrain Models (DTM) Symposium, St. Louis, Missouri, May 9-11, 1978, pp 516-540. The basic description of the original TIN project.

8. Discussion and exam questions

1. Argue the differences between the regular grid and the triangular net approaches. Apply the argument to the computation of slope, contouring and visibility.

2. Mark's article in 1979 argued that the TIN model was more appropriate to the nature of certain geographical phenomena. Do you agree? For what types of landforms is TIN most and least appropriate?

3. Discuss the various methods proposed for selecting TIN vertices from a DEM, and their relative strengths and weaknesses.

4. Describe how information on directions of flow can be obtained from a TIN, and the nature of the extracted stream network. How does this compare to networks derived from DEMs?

Evaluation

We are very interested in your comments and suggestions for improving this material.  Please follow the link above to the evaluation form if you would like to contribute in this manner to this evolving project.

Citation

To reference this material use the appropriate variation of the following format:

The correct URL for this page is: http://www.ncgia.ucsb.edu/giscc/units/u056/u056.html.
Created: 1990.  Last revised: August 7, 2000.

To the Core Curriculum Outline