Steps to Create a TIN: 18-Geom-B1 Digital Terrain Modelling, December 2014, 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. The height data of a DEM—either a regular grid of elevation posts or an irregular set of $(X,Y,Z)$ mass 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:

Assemble and clean the point set. Collect the mass points and any spot heights, remove duplicates and gross blunders, and identify the data extent (convex hull).
Select the significant points (grid DEM source). When the DEM is a regular grid, most posts on smooth ground are redundant, so a subset of surface-specific points is chosen before triangulating: e.g. the Very Important Points (VIP) method, which scores each post by how far it departs from the lines joining its opposite neighbours; Fowler–Little detection of peaks, pits, passes, ridge and channel points; or the drop heuristic / greedy error-threshold insertion, which keeps adding the post with the largest vertical error against the current TIN until every residual is within the specified tolerance. Retaining only these points gives a TIN that reproduces the grid surface to tolerance with far fewer vertices.
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)