Triangulated Irregular Network
Triangulated irregular network (TIN) is a digital data structure used in a geographic information system (GIS) for the representation of a surface. A TIN is a vector based representation of the physical land surface or sea bottom, made up of irregularly distributed nodes and lines with three dimensional coordinates (x, y, and z) that are arranged in a network of non-overlapping triangles. TINs are often derived from the elevation data of a rasterized digital elevation model (DEM).
Comparison of TIN with DEM.
1. Points of a TIN are distributed variably based on an algorithm that determines which points are most necessary to an accurate representation of the terrain.
2. Data input is therefore flexible and fewer points need to be stored than in a DEM with regularly distributed points.
3. TIN may be less suited than a DEM raster for certain kinds of GIS applications, such as analysis of a surface's slope and aspect.
4. TIN enables the portraying of terrain in three dimensions.
A TIN comprises a triangular network of vertices, known as mass points, with associated coordinates in three dimensions connected by edges to form a triangular tessellation. Tessellation or tiling of the plane is a collection of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of the parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Three-dimensional visualizations are readily created by rendering of the triangular facets. In regions where there is little variation in surface height, the points may be widely spaced whereas in areas of more intense variation in height the point density is increased.
A tessellation of a disk used to solve a finite element problem. Solving the two-dimensional problem uxx + uyy = − 4 in the disk centered at the origin and radius 1, with zero boundary conditions.
Although usually associated with 3-dimensional data (x, y, and z) and topography, TINs are also useful for the description and analysis of horizontal (x and y) distributions and relationships
A TIN is typically based on a Delaunay triangulation but its utility will be limited by the selection of input data points: well-chosen points will be located so as to capture significant changes in surface form, such as topographical summits, breaks of slope, ridges, valley floors, pits and cols (depression in mountain chain).
Delaunay Triangulation
In mathematics, and computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid skinny triangles. The triangulation was invented by Boris Delaunay in 1934.
Based on Delaunay's definition, the circumcircle of a triangle formed by three points from the original point set is empty if it does not contain vertices other than the three that define it (other points are permitted only on the very perimeter, not inside).
A triangle net is a Delaunay triangulation if all the circumcircles of all the triangles in the net are empty. This is the original definition for bidimensional spaces. It is possible to use it in tridimensional spaces by using a circumscribed sphere in place of the circumcircle.
For a set of points on the same line there is no Delaunay triangulation (in fact, the notion of triangulation is undefined for this case).
For 4 points on the same circle (e.g., the vertices of a rectangle) the Delaunay triangulation is not unique: clearly, the two possible triangulations that split the quadrangle into two triangles satisfy the Delaunay condition.
A Delaunay triangulation in the plane with circumcircles shown
Example: Looking at two triangles ABD and BCD with the common edge BD (see figures), if the sum of the angles α and γ is less than or equal to 180°, the triangles meet the Delaunay condition.
This is an important property because it allows the use of a flipping technique. If two triangles do not meet the Delaunay condition, switching the common edge BD for the common edge AC produces two triangles that do meet the Delaunay condition:
This triangulation does not meet the Delaunay condition (the sum of α and γ is bigger than 180°).
This triangulation does not meet the Delaunay condition (the circumferences contain more than 3 points, 4th falling within the circle which is not allowed)
Flipping the common edge produces a Delaunay triangulation for the four points.
Algorithms for Testing Delaunay Conditions
All algorithms for computing Delaunay triangulations rely on fast operations for detecting when a point is within a triangle's circumcircle and an efficient data structure for storing triangles and edges. In two dimensions, one way to detect if point D lies in the circumcircle of A, B, C is to evaluate the determinant:
Assuming A, B and C to lie counter-clockwise, this is positive if and only if D lies in the circumcircle.
Assume the following values for the corners in the above triangles. A:(5,5), B: (10,2), C: (15,5), D: (10,20). Substituting these values in the above determinant we have
Then determinant
Then the point D does not lie in the circumcircle.
If the y coordinate of the point D is changed to 10 and the determinant recomputed we obtain . Then the point D lies in the circumcircle
The TIN model represents a surface as a set of contiguous, non-overlapping triangles. Within each triangle the surface is represented by a plane. The triangles are made from a set of points called mass points.
Mass points can occur at any location, the more carefully selected, the more accurate the model of the surface. Well-placed mass points occur where there is a major change in the shape of the surface, for example, at the peak of a mountain, the floor of a valley, or at the edge (top and bottom) of cliffs.
The TIN model is attractive because of its simplicity and economy and is a significant alternative to the regular raster of the GRID model.
Quick comparison:
TIN / GRIDAdvantages / · ability to describe the surface at different level of resolution
· efficiency in storing data / · easy to store and manipulate
· easy integration with raster databases
· smoother, more natural appearance of derived terrain features
Disadvantages / · in many cases require visual inspection and manual control of the network / · inability to use various grid sizes to reflect areas of different complexity of relief.
The Delaunay Triangulation
Delaunay triangulation is a proximal method that satisfies the requirement that a circle drawn through the three nodes of a triangle will contain no other node
Delaunay triangulation has several advantages over other triangulation methods:
· The triangles are as equi-angular as possible, thus reducing potential numerical precision problems created by long skinny triangles
· Ensures that any point on the surface is as close as possible to a node
· The triangulation is independent of the order the points are processed
TIN from contours
Contours are a common source of digital elevation data. In general all the vertices of the contour lines are used as mass points for triangulation. In many cases this will cause the presence of flat triangles in the surface.
Flat triangles are created whenever a triangle is formed from three nodes with the same elevation value
Flat triangles are frequently generated along contours when the sample points occur along the contour at a distance that is less than the distance between contours. When these "excess" vertices are not removed , the Delaunay triangulation discovers that the closest sample points are those along the same contour, causing the generation of flat triangles.
The flat triangles have a slope of 0 and do not have defined aspect. They might cause problems when the surface is used for modeling.
Example
The contours / The triangulation - We can see several flat triangles hereThe elevation / The slope- The green areas indicate
Slope = 0 (flat triangles)
How can we avoid the flat triangles ?
· By adding more mass points
· Generalizing the contours
· By adding break lines
Break lines
Linear features which define and control surface behavior in terms of smoothness and continuity are called break lines.
Types of break lines:
· Soft break lines are used to ensure that linear features and polygon edges are maintained in the TIN surface model by enforcing the break line as TIN edges. However, they do not define interruptions in surface smoothness – break lines with no Z value
· Hard break lines define interruptions in surface smoothness – break lines with Z value
Example:
No break lines / Soft break lines / Hard break linesThe Data
The Triangulation
The Surface
3D View
Storing TINs
There are basically two ways of storing triangulated networks:
· Triangle by triangle
· Points and their neighbors
The first method is better for storing attributes (slope, aspect ..) for each triangle, but uses more storage space. The second one is better for generating contours and uses less storage space, but slope, aspect , etc must be calculated and stored separately.
TIN and ArcView
The 3D Analyst extension has a very good algorithm for building TINs. It has plenty of functions to analyze and visualize a TIN surface. It stores the TIN structure using the second method above. That's why the slope, aspect and hillshade analysis functions create grids to represent the results. The build TIN and create contours procedures are fast and efficient.
EditTools 3.1 extension creates TIN structures and stores the data as a 3D triangles (PolygonZ shape file). After analysis the slope, aspect and hillshade values are stored as attributes for each triangle. This allows fast visualization of the different surface derivatives. The TIN interpolation procedure and the deriving of contours from the surface are slower, but the results are pretty much the same as these obtained from 3D Analyst.
1