A. INTRODUCTION

B. HOW TO PICK POINTS

C. HOW TO TRIANGULATE A TIN

D. ALTERNATIVE METHODS OF CREATING TINS

E. STORING TINS

F. ALGORITHMS ON TINS

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

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

but there will be sharp changes of slope at triangle edges

other possibilities exist, especially useful in finite element modeling, involving curved surfaces and quadrilaterals, that ensure no sharp changes of slope

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

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

given a dense DEM or set of digitized contours, how should points be selected so that the surface is accurately represented?

consider the following methods for selecting from a DEM

they try to select points at significant breaks of the surface

such breaks are common on terrain, absent on smooth mathematical surfaces

VIP works by examining the surface locally using a window

this is a simplification of the technique used in ESRI's ARC/INFO

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

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

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

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

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

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

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

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

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

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

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

there are basically two ways of storing triangulated networks:

1. Triangle by triangle

2. Points and their neighbors

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

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)

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

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

 diagram

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

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.

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?