An efficient dichotomizing interpolation algorithm for the refinement of TIN-based terrain surface from contour maps

Generating a triangulated irregular network (TIN) from contour maps is the most commonly used approach to build Digital Elevation Models (DEMs) for geo-databases. A well-known problem when building a TIN is that many pan slope triangles (or PSTs) may emerge from the vertices of contour lines. Those triangles should be eliminated from the TIN by adding additional terrain points when refining the local TIN. There are many methods and algorithms available for eliminating PSTs in a TIN, but their performances may not satisfy the requirements of some applications where efficiency rather than completeness is critical. This paper investigates commonly-used processes for eliminating PSTs and puts forward a new algorithm, referred to as ‘dichotomizing’ interpolation algorithm, to achieve a higher efficiency than from the conventional ‘skeleton’ extraction algorithm. Its better performance comes from reducing the number of the additional interpolated points to only those that are sufficient and necessary for eliminating PSTs. This goal is reached by dichotomizing PST polygons iteratively and locating additional points in the geometric centers of the polygons. This study verifies, both theoretically and experimentally, the higher efficiency of this new dichotomizing algorithm and also demonstrates its reliability for building DEMs in terms of accuracy for estimating terrain surface elevation.