Steps to Create a TIN: 18-Geom-B1 Digital Terrain Modelling, December 2016, 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. A DEM — a regular grid of height posts $(X,Y,Z)$ — plus any available breaklines and spot heights, to be converted into a TIN.

Find. The procedure to construct the network, including how the significant points are chosen from the grid.

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. Triangulating every grid post would just reproduce the grid as a very large TIN, so the conversion first selects the significant points and then applies a Delaunay triangulation:

Clean the DEM. Remove blunders (spikes and pits) and void/no-data cells, and fix the data extent (the grid boundary, or its convex hull).
Select the significant points from the grid. Keep only the posts that carry the terrain shape. Very Important Point (VIP) screening scores each post by how far it departs from the straight lines joining its opposite neighbours (N–S, E–W and both diagonals) and keeps the high scorers, which are the peaks, pits, ridge and channel points. A drop heuristic works the other way: start from all posts, and repeatedly delete the point whose removal changes the triangulated surface least, until the maximum vertical error reaches a set tolerance (e.g. 0.5 m). Surface-specific points (peaks, pits, passes) and any spot heights are always kept, and the four grid corners are kept so the TIN covers the whole extent.
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)