LECTURE 15 - THE TIN MODEL

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

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

other possibilities exist, especially useful in finite element modeling, involving curved surfaces and quadrilaterals

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

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

B. 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

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

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)

+ - +
- -
+ - + (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

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

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. 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

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

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

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

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

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

C. 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

1. Distance ordering

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

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

Link to diagram

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

Procedure

there are several techniques for building the triangles:

start with these edges and work inwards until the network is complete

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

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")

D. ALTERNATIVE METHODS OF CREATING TINS

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

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

E. STORING TINS

there are basically two ways of storing triangulated networks:

Link to diagram

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

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)

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

F. ALGORITHMS ON TINS

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

Contouring

Link to diagram

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

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

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

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.

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?