18-Geom-B1 Digital Terrain Modelling · December 2017
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Paper format: National Exams, December 2017 — 3 hours, closed book (one approved Casio or Sharp calculator permitted). The schedule prints TWELVE questions and states that "10 questions constitute a complete paper": Part A (Q1–Q8) is compulsory, Part B requires ONE of Q9–Q10, and Part C requires ONE of Q11–Q12, for a 100-mark paper. All twelve questions are solved below for completeness (a candidate would answer only Q1–Q8 plus one from each of Parts B and C).
Reference texts: Li, Zhu & Gold, Digital Terrain Modeling — Principles and Methodology (CRC Press, 2005); Maune (ed.), Digital Elevation Model Technologies and Applications: The DEM Users Manual (2nd ed., ASPRS, 2007); Wilson & Gallant, Terrain Analysis — Principles and Applications (Wiley, 2000); Wolf, Dewitt & Wilkinson, Elements of Photogrammetry with Applications in GIS (4th ed., McGraw-Hill, 2014); Isaaks & Srivastava, An Introduction to Applied Geostatistics (Oxford, 1989). Canadian datums throughout (NAD83(CSRS), CGVD2013).
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. An irregular set of points to be triangulated into a TIN, and the dual Voronoi construction.
Find. (9.1) two defining conditions of a Delaunay triangulation; (9.2) the meaning of the Voronoi diagram and a Voronoi region.
9.1 Two characteristic conditions of a Delaunay triangulation.
(i) The empty-circumcircle (empty-circle) condition. A triangulation is Delaunay if and only if the circumscribing circle of every triangle contains no other point of the set in its interior. Each triangle’s three vertices lie on its circumcircle and no fourth point falls inside — the property that uniquely defines the Delaunay network (for points in general position) and is the criterion tested during construction (e.g. the incremental “flip” algorithm swaps the shared edge of two triangles whenever a neighbour’s vertex lies inside the circumcircle).
(ii) The max-min angle (equiangularity) condition. Among all possible triangulations of the point set, the Delaunay triangulation maximizes the minimum interior angle of its triangles. It therefore produces the most nearly equilateral, “fattest” triangles available and systematically avoids long thin slivers — which is exactly what is wanted for terrain interpolation, because well-shaped triangles minimize the linear-interpolation error and numerical instability. The two conditions are equivalent: enforcing the empty circle is the same as maximizing the minimum angle.
9.2 Voronoi diagram and Voronoi region. Given the same set of points (called sites or generators), the Voronoi diagram partitions the plane into cells, one per site, that tile the whole plane without gaps or overlaps. The Voronoi region (Voronoi cell / Thiessen polygon) of a site $p_i$ is the set of all locations in the plane that are closer to $p_i$ than to any other site: $V(p_i) = \{x : \lVert x - p_i \rVert \le \lVert x - p_j \rVert \ \forall j \ne i\}$. Its boundaries are segments of the perpendicular bisectors between neighbouring sites, so a Voronoi edge separates two sites of equal nearest distance and a Voronoi vertex is equidistant from three sites (the circumcentre of a Delaunay triangle). The Delaunay triangulation is the straight-line dual of the Voronoi diagram: joining every pair of sites whose Voronoi regions share an edge produces exactly the Delaunay triangles — which is why a TIN can be built by first constructing the Voronoi diagram and then connecting adjacent generators.
