Regular lattices such as grids provide a very inefficient means of storing details of surface topography. Areas that have similar slope could be better represented and stored using a series of inter-connected triangles forming an irregular mesh or network (a TIN). The nodes or vertices of these triangles can be placed closer together where landscape detail is more complex and further apart where surfaces are simpler. TINs may be designed or derived. Designed TINs arise in engineering and surveying models, whereas derived TINs are typically programmatically generated from grid-based datasets (digital elevation models or DEMs).
Although such TINs could be generated by selecting vertices using key feature extraction and surface modeling, a simpler and faster approach is to systematically divide the entire region into more and more triangles based on simple subdivision rules. For example, if you start with a rectangular region and define vertices at each of the four corners, two triangulations are possible: (i) a line connecting the NE-SW corners creates one pair of triangles; or (ii) a line connecting the NW-SE corners creates a second pair. For each triangle a statistic can be computed, such as the maximum deviation in elevation of the triangle from the original DEM. The arrangement that produces the smallest maximum absolute deviation (a minimax criterion) can then be selected as the preferred triangulation. Each of the two initial triangles can then be subdivided further. For example, a point can be placed at the centroid of each triangle which creates a further three triangles, or 6 in total. The minimax criterion test can be applied for each of the subdivisions of the two original triangles and the process proceeds iteratively until the minimax criterion is less than a pre-defined threshold value (e.g. 5 meters) or the number of triangles generated has reached a maximum value, also pre-defined. This kind of procedure is used in many GIS packages — for example TNTMips describes this process as adaptive densification. TINs and DEMs are discussed in more detail in Chapter 6 (see for example, Figure 6‑5).
