Go to Paper
Return to GeoComputation 99 Index

What’s the Point? Interpolation and Extrapolation with a Regular Grid DEM

KIDNER, David (dbkidner@glam.ac.uk), DOREY, Mark, University of Glamorgan, School of Computing, SMITH, Derek, Division of Mathematics & Computing, Pontypridd, Rhondda Cynon Taff, Wales, CF37 1DL, U.K.

Key Words: digital terrain modelling, DEMs, interpolation, surface polynomials and splines, extrapolation, linear and non-linear prediction, Lagrange multipliers, data compression

This paper advocates the use of more sophisticated approaches to mathematical modelling of elevation samples for applications that rely on interpolation and extrapolation. The computational efficiency of simple, linear algorithms is no longer an excuse to hide behind today's advances in processor performance. The limitations of current algorithms are illustrated for a number of applications ranging from contouring and visibility analysis to data compression.

A regular grid digital elevation model (DEM) represents the heights at discrete samples of a continuous surface. As such, there is not a direct topological relationship between points; however, for a variety of reasons, users consider these elevations to lie at the vertices of a regular grid, thus imposing an implicit representation of surface form. For most GIS, a linear relationship between vertices is assumed, while a bilinear representation is assumed within each DEM cell. The consequences of imposing such assumptions can be critical for those applications that interpolate unsampled points from the DEM. Small interpolation or elevation errors can propagate through to large application errors. This is true for intervisibility analysis and even more traditional GIS algorithms, such as contouring. While these applications are well understood and have been with us for many years, bilinear interpolation is still the most commonly used method for retrieving surface estimates from DEMs. The first part of the paper demonstrates the problems of interpolation within a DEM and evaluates a variety of alternative approaches such as bi-quadratic, cubic, and quintic polynomials and splines that attempt to derive the shape of the surface at interpolated points.

Extrapolation is an extension of interpolation to locations outside the current spatial domain. One can think of extrapolation as standing in the terrain and given my field of view, what is my elevation at a location one step backwards? This approach to elevation prediction is at the heart of many new techniques of data compression applied to DEMs. The demand for better data compression algorithms is a consequence of finer resolution data, e.g. LiDAR, and the wider dissemination of DEMs by intranet and internet. In a similar manner to the interpolation algorithms, the basis of elevation prediction is to determine the local surface form by correlating values within the Afield of view. The extent of this field of view can be the nearest three DEM vertices that are used to bilinearly determine the next vertex. The second part of the paper evaluates this approach for more extensive fields of view, using both linear and non-linear techniques.