432 
ISPRS, Vol.34, Part 2W2, "Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001 
ISPRS, 
and evaluate their planar functions for the (x, y) of the grid node. 
These z estimates are then weighted and averaged as before. 
Fig. 21 shows the result of using Sibson interpolation with data 
point slopes. It gives an apparently excellent result - and looks 
even better than when the smoothing function Is added to it. 
While it is impossible to show the results of all our experiments 
in this paper, in order to see what was happening we used the 
method of (Burrough and Mcdonnell, 1988) to calculate slopes 
and profile curvature for grids created from various combinations 
of our available weighted-average methods. Somewhat 
surprisingly, the version without smoothing gives more 
consistent regions of coherent slopes, indicating that the 
smoothing function adds unwanted undulations to the surface. 
However, examination of the profile curvature map shows that 
without smoothing there are folds in the surface at the contour 
lines - as would be expected - although the effects are minor. 
Adding slopes to the simple TIN model (i.e. using the position in 
the triangle to provide the weights) produced results that were 
almost as good as the Sibson method where the sample points 
were closely spaced along the contours, but the Sibson method 
is much superior for sparser data, or where the points do not 
form contour lines. The gravity model does not provide 
particularly good slope estimates, but even here including the 
data point slope function produces a significant improvement. 
CONCLUSIONS. 
From our work, several broad generalizations may be made. To 
produce good surface models, with reasonable slopes, from 
contour maps the single most valuable contribution is the 
addition of skeleton points along the ridges, valleys, pits, 
summits and passes. These are guaranteed to eliminate flat 
triangles. Height estimates at these points may be based either 
on longitudinal or lateral slope consistency, depending on the 
physical model desired, or the detection of valley-head 
information. 
Figure 1: Triangulation of several small hills 
The second most important contribution is the addition of slope 
information at the data points, and its use in the weighted 
average. Even poor interpolation methods are significantly 
improved. Also important is the selection of a meaningful set of 
neighbours around the grid node to be estimated. 
Of lesser importance is the particular interpolation method used, 
although this statement is highly dependent on the data 
distribution and density. Gravity models in general should be 
avoided if possible. Surprisingly, mathematically guaranteed 
slope continuity is not usually critical, although we are continuing 
to work on an improved smoothing function that guarantees both 
slope continuity and minimum curvature - probably based on the 
work of Anton et al. (1998). Nevertheless, the moral is clear: 
both for finding adjacent points and skeleton extraction, a 
consistent definition of neighbourhood is essential for effective 
algorithm development. 
Figure 2: Sibson interpolation with slopes 
We conclude with another imaginary example. Fig. 22 shows 
four small hills defined by their contours, modelled by a simple 
triangulation. Fig. 23 shows the result using Sibson interpolation, 
slopes and skeletons. Skeleton heights were obtained using 
circumcircle ratios, as no valley-heads were detected. While our 
evaluation was deliberately subjective, we consider that our 
results in this case, as with the previous imaginary valley, closely 
follow the perceptual model of the original interpretation. Thus, 
for the reconstruction of surfaces from contours, we believe that 
our methods are a significant improvement on previous work. 
REFERENCES 
Amenta, N., M. Bern and D. Eppstein, 1998. The crust and the 
beta-skeleton: combinatorial curve reconstruction. Graphical 
Models and Image Processing, 60/2:2, pp. 125-135. 
Anton, F.; Gold, C.M. and Mioc, D., 1998, Local coordinates and 
interpolation in a Voronoi diagram for a set of points and line 
segments. Proceedings, 2nd Voronoi Conference on Analytic 
Number Theory and Space Tillings; Kiev, Ukraine, pp. 9-12. 
Aumann, G., H. Ebner, and L. Tang, 1991, Automatic derivation 
of skeleton lines from digitized contours, ISPRS Journal of 
Photogrammetry and Remote Sensing, 46 259-268, Elsevier 
Science Publishers B.V., Amsterdam. 
Blum, H., 1967. A transformation for extracting new descriptors 
of shape. In: W. Whaten Dunn (ed.), Models for the Perception 
of Speech and Visual Form. MIT Press, pp. 153-171. 
Burrough, P. and Mcdonnell, R.A., 1988, Principles Of 
Geographical Information Systems, 2 nd . Ed., 336p. Oxford 
University Press. 
Gold, C.M., 1989. Chapter 3 - Surface interpolation, spatial 
adjacency and G.I.S. In: Three Dimensional Applications in 
Geographic Information Systems (J. Raper, ed.), Taylor and 
Francis, Ltd., London, pp. 21-35. 
Gold, C.M., 1999, Crust and anti-crust: a one-step boundary and 
skeleton extraction algorithm. Proceedings, ACM Conference on 
Computational Geometry, Miami, Florida, pp. 189-196. 
Gold, C.M. and Snoeyink, J., 2001, A one-step crust and 
skeleton extraction algorithm. Algorithmica, (in press). 
Sibson R., 1980, A Vector Identity for the Dirichlet Tessellation, 
Math. Proc. Cambridge Philos. Soc., 87, pp. 151-155. 
Thibault, D. and Gold, C.M. 2000, Terrain Reconstruction from 
Contours by Skeleton Construction. Geolnfo. v. 4 pp. 349-373. 
Watson, D.F. and Philip, G.M., 1987, Neighborhood-based 
interpolation, Geobyte, 2(2), 12-16. 
A. 
A. 
A. 
A. 
B. 
B. 
B. 
B. 
C. 
C. 
C. 
c. 
c. 
c. 
c. 
c. 
D. 
D. 
D. 
D. 
D. 
D. 
D. 
D. 
E. 
E. 
E. 
F. ] 
F. ] 
F. ' 
F. ' 
G. 
G. 
G. 
G. 
G. 
G. 
H. 
H. 
H. 
H. 
H. 
H. 
H. 
H. 
H. 
H. 
H.