Steps to Create a TIN: 18-Geom-B1 Digital Terrain Modelling, December 2015, Q6

Question 6: Steps to Create a TIN (5 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. DEM data—a regular grid of height posts or an irregular set of $(X,Y,Z)$ points—plus any breaklines, to be organized into a TIN.

Find. The procedure to construct the network.

Delaunay TIN: points are joined into triangles such that no other point falls inside any triangle's circumcircle (dashed), which maximizes the minimum angle and avoids sliver triangles.

Procedure. The standard construction is a Delaunay triangulation, built as follows:

Select the significant points from the DEM. A gridded DEM holds far more posts than a TIN needs, so the points that carry the terrain shape are extracted first: very important point (VIP) screening scores each post by how far it departs from the lines joining its opposite neighbours, and keeps only high-scoring posts; alternatively a drop heuristic removes, one at a time, the post whose deletion changes the surface least, or a greedy insertion method adds the post with the largest vertical error until every residual is within a set tolerance. Peaks, pits, ridge and channel posts are always retained.
Assemble and clean the point set. Combine the selected posts with any spot heights, remove duplicates and gross blunders, and identify the data extent (convex hull).
Triangulate by the Delaunay criterion. Connect the points into non-overlapping triangles so that the circumcircle of every triangle contains no other point (the empty-circle property). This equivalently maximizes the minimum interior angle, producing well-shaped triangles and avoiding thin slivers. Common algorithms are incremental point insertion with local edge flipping, divide-and-conquer, or sweep-line.
Enforce breaklines (constrained Delaunay). Insert breakline segments as required edges that triangles may not cross, re-triangulating locally so ridges, channels and feature edges are preserved even where that violates the pure empty-circle rule.
Store the topology. Record each triangle's three vertices and its neighbour adjacencies so slope, aspect, contours and volumes can be queried efficiently.
Validate. Check for degenerate/overlapping triangles, verify the hull, and confirm breaklines are honoured.

Concept & Theory

Topic. Delaunay (and constrained Delaunay) triangulation of irregular terrain points.

Key relations. Delaunay empty-circle property $\Leftrightarrow$ maximize the minimum angle; it is the straight-line dual of the Voronoi diagram; a set of $n$ points yields $\approx 2n$ triangles.

Why this works. Maximizing the minimum angle gives the most equilateral triangles available, which minimizes linear-interpolation error and numerical instability; the constrained form injects the morphology that the pure geometric criterion would ignore.

Common pitfall. Triangulating without breaklines, so triangle edges cross a ridge or ditch and interpolate straight through it, smearing the very feature the TIN was meant to preserve.

Source. Li, Zhu & Gold, ch. 5 (TIN); de Berg et al., Computational Geometry, ch. 9.

Question 6 of 12: Steps to Create a TIN

Question 6: Steps to Create a TIN (5 marks)