Constructing a dem from grid-based data by computing intermediate contours

ABSTRACT

We present a technique for creating a digital elevation model (DEM) from grid-based contour data. The method computes new, intermediate contours in between existing isolines. These are found by finding the shortest line segment that connects points on two neighboring contours with differing elevations. The midpoint of the line segment becomes a point on the intermediate contour. The contours are completed by connecting individual points. The new contours are then used as data for successive iterations, until an initial surface is formed. Peaks are computed by Hermite splines that follow the slope trend. Gaussian smoothing is applied to the entire surface or only to newly computed elevations, yielding an approximated or interpolated surface, respectively. The DEMs are tested with quantitative methods, and are shown to compare favorably to well established algorithms.

REFERENCES

• 1: Ardiansyah, P. O. D., and Yokoyama, R. DEM generation method from contour lines based on the steepest slope segment chain and a monotone interpolation function. Journal of Photogrammetry and Remote Sensing 57, 1-2 (2002), 86--101.
• 2: Jack Bresenham, A linear algorithm for incremental digital display of circular arcs, Communications of the ACM, v.20 n.2, p.100-106, Feb. 1977 [doi>10.1145/359423.359432]
• 3: Briggs, I. Machine contouring using minimum curvature. Geophysics 39, 1 (February 1974), 39--48.
• 4: Carrara, A., Bitelli, G., and Carla', R. Comparison of techniques for generating digital terrain models from contour lines. International Journal of Geographical Information Science 11, 5 (1997), 451--473.
• 5: CRES. TAPES: Terrain programs for the environmental sciences. Centre for Resource and Environmental Studies.
• 6: CSIRO. TOPOG. CSIRO Land and Water and the Cooperative Research Center for Catchment Hydrology.
• 7: Paul Dierckx , Paul Suetens , Dirk Vandermeulen, An algorithm for surface reconstruction from planar contours using smoothing splines, Journal of Computational and Applied Mathematics, v.23 n.3, p.367-388, September 1988 [doi>10.1016/0377-0427(88)90007-6]
• 8: Douglas, D. H. The XYNIMAP family of programs for geographic information processing and thematic map production. InAuto--Carto 6:Sixth International Symposium on Computer-Assisted Cartography (1983), B. S. Wellar, Ed., vol.2, pp.2--14.
• 9: G. Farin, Curves and surfaces for computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1990
• 10: Franklin, W. R. Triangulated irregular network program, 1973.
• 11: Garcia, AntonioBello, et al. A contour line based triangulating algorithm. In Proceedings of the 5th International Symposium on Spatial Data Handling (Charleston SC USA, 1992), P. Bresnahan, E. Corwin, and D. Cowen, Eds., vol. 2, IGU Commission of GIS, pp.411--423.
• 12: Christopher Gold, Crust and anti-crust: a one-step boundary and skeleton extraction algorithm, Proceedings of the fifteenth annual symposium on Computational geometry, p.189-196, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304971]
• 13: Heine III, G. W. A controlled study of some two-dimensional interpolation methods. Computer Oriented Geological Society Computer Contributions 2, 2 (August 1986), 60--72.
• 14: Huber, M. Contour-to-dem: A new algorithm for contour line interpolation. InJoint European Conference and Exhibition on Geographical Information Proceedings (Basel, 1995), vol. 1, JEC-GI, pp.221--222. http://lbdsun.epfl.ch/ huber/ctdjec.html.
• 15: Hutchinson, M. F. Calculation of hydrologically sound digital elevation models. In Proceedings of the Third International Symposium on Spatial Data Handling (Columbus, Ohio, 1988), International Geographical Union, pp.117--133.
• 16: Hutchinson, M. F., and Gallant, J. C. Representation of terrain. InGeographical Information Systems: Principles and Technical Issues, Longley, Goodchild, Maguire, and Rhind, Eds., 2ed., vol.1. Wiley, 1999, pp.105--124.
• 17: Jaakkola, O., and Oksanen, J. Creating DEMs from contour lines: Interpolation techniques which save terrain morphology. GIM International 14, 9 (2000), 46--49.
• 18: Maunder, C. J. An automated method for constructing contour-based digital elevation models. Water Resources Research 35, 12 (1999), 3931--3940.
• 19: Peucker, T. K., and Chrisman, N. Cartographic data structures. The American Cartographer 2, 1 (1975), 55--69.
• 20: Reichenbach, P., Pike, R. J., Acevedo, W., and Mark, R. K. A new landform map of italy in computer-shaded relief. Bollettino Geodesia a Scienze Affini 52 (1993), 22--44.
• 21: Rinehart, R. E., and Coleman, E. J. Digital elevation models produced from digital line graphs. In Proceedings of the ACSM-ASPRS Annual Convention (1988), vol.2, American Congress on Surveying and Mapping, American Society for Photogrammetry and Remote Sensing, pp.291--299.
• 22: Robinson, G. J. The accuracy of digital elevation models derived from digitised contour data. Photogrammetric Record 14 (1994), 805--814.
• 23: Shmutter, B., and Doytsher, Y. Conversion of contours. In Auto--Carto 9:Ninth International Symposium on Computer-Assisted Cartography (1989), pp.245--254.
• 24: Sibson, R. A brief description of natural neighbor interpolation. InInterpreting Multivariate Data, Barnet, Ed. Wiley, 1981, pp.21--36.
• 25: Sarvajit S. Sinha , Brian G. Schunck, A Two-Stage Algorithm for Discontinuity-Preserving Surface Reconstruction, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.1, p.36-55, January 1992 [doi>10.1109/34.107012]
• 26: Smith, W. H. F., and Wessel, P. Gridding with continuous curvature splines in tension. Geophysics 55, 3 (1990), 293--305.
• 27: Hind Taud , Jean-François Parrot , Roman Alvarez, DEM generation by contour line dilation, Computers & Geosciences, v.25 n.7, p.775-783, Aug. 1999 [doi>10.1016/S0098-3004(99)00019-9]
• 28: Demetri Terzopoulos, The Computation of Visible-Surface Representations, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.417-438, July 1988 [doi>10.1109/34.3908]
• 29: Watson, D. Contouring: A Guide to the Analysis and Display of Spatial Data. Pergammon Press, Oxford, NY, 1992.
• 30: Joseph D. Wood , Peter F. Fisher, Assessing Interpolation Accuracy in Elevation Models, IEEE Computer Graphics and Applications, v.13 n.2, p.48-56, March 1993 [doi>10.1109/38.204967]
• 31: Zhu, H., Eastman, J. R., and Toledano, J. Triangulated irregular network optimization from contour data using bridge and tunnel edge removal. International Journal of Geographical Information Science 15, 3 (2001), 271--286.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING

General Terms:
Algorithms

Keywords:
DEM, GIS, approximation, contours, grid, interpolation