Delaunay triangulations in TIN creation: an overview and a linear-time algorithm

Abstract The Delaunay triangulation is commonly used to generate triangulated irregular network (TIN) models for a best description of the surface morphology in a variety of applications in geographic information systems (GIS). This paper discusses the definitions and basic properties of the standard and constrained Delaunay triangulations. Several existing Delaunay algorithms are reviewed and classified into three categories according to their procedures: (1) divide-and-conquer methods, (2) incremental insertion methods, and (3) triangulation growth methods. Furthermore, a linear-time Convex Hull Insertion algorithm is presented to construct TINs for a set of points as well as specific features such as constraint breaklines and exclusion boundaries. Empirical results over various sets of up to 50000 points on personal computers show that the proposed algorithm efficiently expedites the construction of TIN models in approximately O(N) for N randomly distributed points.