“Automated contour mapping using triangular element data structures and an interpolant over each irregular triangular domain” by Gold, Charters and Ramsden

Surface display techniques, including contour mapping, usually use an interpolant when data values are on a rectangular grid; but when values are irregularly located some form of assumed or estimated distance-weighting function is often used to estimate the “influence” of data points at other locations. If moving average (or some other) techniques are then applied, slopes may be zero at data points; extrema may fall at data points exclusively; or surfaces may not pass through data points.An alternative method is proposed whereby a map area is automatically divided into suitable triangular domains with a data point at each vertex. Surface estimation and contour plotting are then performed independently for each triangle using a measured or best-fit plane associated with each data point. The approach requires the utilization of three non-original aspects: 1) the derivation of a local homogeneous “area” coordinate system for any arbitrary triangle; 2) the construction of a data-structure linking each triangular domain with its three neighbouring triangles and three associated data points, and 3) the use of a “conforming” triangular finite-element interpolating function.Use of the first two of these concepts permits the economic generation and optimization of a triangular mesh from a set of data points. Optimization criteria used to define the “best” triangular partition are described in some detail, along with computer timing for this step. Use of the first and third concepts permits the interpolation of a smooth surface over the whole map area even though each triangular element is estimated and plotted independently. The requirements for a suitable interpolating function are discussed, and an interpolant is suggested that preserves elevation and slope at each data point as well as elevation and slope continuity between domains. Extrema need not be located at data points but are constrained by their associated planes. Contour line segments are produced by division of each triangle into N2 sub-triangles, elevation estimation at each resulting node, and linear interpolation and plotting withing each sub-triangle. Resolution is then a function of N and local data point density. Extension of the method to higher dimensions is briefly discussed.

1. Bengtsson, B. F. and Nordbeck, S. Construction of isarithms and isarithmic maps by computers. B. I. T. 4, (1964), 87-105.
2. Feuerbach, K. W. Grundriss zu analytischen Untersuchungen der dreieckigen Pyramide. Nuremburg, 1827.
3. Frenkel, Y. and Gill, D. An algorithm for contouring random data without gridding. Israeli J. Earth Sciences 24, (1975), 56.
4. Gold, C. M. Triangular element data structures. The University of Alberta Computing Services Users Applications Symposium Proceedings, Edmonton, (May 1976), 43-54.
5. Gold, C. M. Surface estimation from irregularly spaced data points using an interpolant over irregular triangular domains. Geological and Mineralogical Associations of Canada Program with Abstracts 1, (May 1976), 84.
6. Heap, B. R. Algorithms for the production of contour maps over an irregular triangular mesh. N. P. L. report NAC 10, (1972).
7. Irons, B. M. A conforming quartic triangular element for plate bending. Int. J. Num. Meth. Eng. 1, (1969), 29-46.
8. McLain, D. H. Drawing contours from arbitrary data points. Computer J. 17, (1974), 318-324.
9. McLain, D. H. Two dimensional interpolaticn from random data. Computer J. 19, (1976), 178-181.
10. Peucker, T. K. Computer Cartography: Commission on College Geography resource paper no. 17, Association of American Geographers, Washington D. C., (1972).
11. Pitteway, N. I. K. Computer graphics research in an academic environment. Datafair 73 Conference proceedings 2, (1973), 471-478.
12. Rhind, D. A skeletal overview of spatial interpolation techniques. Computer Applications 2, (1975), 293-309.
13. Sampson, R. J. SURFACE II Graphics System. Series on Spatial Analysis no. 1, Kansas Geological Survey, Lawrence, Kansas, (1975).
14. SCA. MCS – Mapping Contouring System. Scientific Computer Applications Inc., Tulsa, Oklahoma, (1970).
15. Zienkiewicz, O. C. The Finite Element Method in Engineering Science. McGraw Hill, London, (1971).