Triangulated Irregular Network (TIN) Data Model

The Triangulated Irregular Network (TIN) is a data model that describes surfaces, especially terrain. It has been developed as an alternative to the two other data models for surfaces, the Regular (Rectangular) Grid and the Contour Model. The summary term is digital terrain model (DTM).

The philosophy that underlies TIN is that triangles are a good approximation of terrain that is less than smooth (i.e., has breaks such as ridges). TIN needs a fraction of the units of regular grids and is computationally faster than contour modeling.

A triangle has three components: (1) one area, (2) three edges, and (3) three vertices. It shares each edge with one other triangle and each vertex (node) with an average of five other triangles. This sharing allows the linkage of the triangles into a network. The resulting relationships are usually identified under the term topology.

All structures have topology. For the regular grid, topology is implicit; that is, each vertex in the network is given by its numbered location, the northwest corner usually being the position 0,0. The neighbors of vertex (i, j) are (i ± 1, j ± 1). For the contour structure, contours often have with them stored the labels of the contours above and below (the “contour tree”). This we could call a “partially explicit” topology.

The implementation of the TIN model into a data structure can happen in different ways.

• The first structure stores in one array the triangles together with their edges and, in a second array, the edges with their limiting vertices. A third array would have the vertices [Page 2884]with their coordinates. All topological relations are stored explicitly.
• The second structure is based on the edge as the main carrier. With each edge are stored the labels of the two endpoints and the labels of the two triangles that are bordering the edge, leading, again, to an explicit topology. A separate array holds the coordinates of each vertex.
• A third structure has the edges as the basis. Each record stores the label of the “leading vertex” or node and the labels of all vertices that are linked to the node. The edges are arranged in clockwise order around the node, starting due north. There is a record for every node in the network. Another array stores the coordinates of all nodes. This structure is different from the other two in that the node records are of variable length and the topology is partially given implicitly through the sequence of neighboring edges. This is likely the structure that needs the smallest amount of storage and is fastest for searches across the network.

So what is a data structure such as TIN good for? First of all, to enter a set of data points into a structure with all the topological attributes gives the points accuracy and solidity. Second, a structure allows for the production of a variety of applications. Most operations that involve surface networks are searches across the surface with one or two of the dimensions (x, y, and height, or z) kept constant. The most frequent application is likely the creation of regular, rectangular grids, because a number of geographic information systems use TIN only for storage purposes, and as soon as something is done with the data, they are converted into the regular grid. These grids are the result of searches across the network with first the y dimension kept constant (horizontal lines) and then the x dimension (vertical lines). The drawing of contours means searching the network with the z dimension kept constant.

...