EVALUATION OF ALGORITHMS FOR SURFACE INTERPOLATION 
OVER TRIANGULAR PATCH 
Jenn-Taur Lee 
Department of Civil and Environmental Engineering 
University of Wisconsin-Madison 
Madison, WI 53706 
ABSTRACT 
Surface interpolation over a triangulation with scattered DEM may 
maintain the continuity and smoothness of surface while it is contributed 
by a condition that two triangles in each shaded quadrilateral must be 
related to the same planar affine map. In other words, two adjacent surface 
patches posses the same tangent plane at each point of their common 
boundary. According to this principle, two numerical experiments were 
used to examine three piecewise polynomial interpolants which are linear, 
cubic, and quintic polynomials. Five criteria including average absolute 
and relative accuracy, root mean square error, CPU time, and visualization 
were chosen to evaluate the tasks of surface construction. Conclusively, the 
best performance is the cubic polynomial interpolation. 
KEY WORDS: DEM, surface interpolation, smoothness, triangulation. 
1. INTRODUCTION 
A smooth interpolatory surface from scattered 
DEM is especially desirable when a visual 
impression of the data is called for. This task may 
be handled by a method of surface interpolation on 
a triangular patch. Let the data set be comprised 
of a set of points (xi,y;), arbitrarily distributed in 
the x-y plane, with corresponding ordinates Z,i- 
1,...,n. These points are the components for a 
bivariate function F(x,y) which interpolates the 
data values, i.e., F(x<;,y;) = 7; This is denoted by 
bivariate interpolation and it should satisfy two 
requirements: first, the interpolant should be 
continuously differentiated everywhere in the 
underlying domain; second, the scheme should be 
local, i.e., evaluating the interpolant at a point 
within a specific triangle should require only 
function and gradient values at the vertices of that 
triangle. This approach, which has been 
employed by Lawson (1977) and Akima (1978); it 
consists of the following three procedures: 
(1)Partition the convex hull of the set of points 
into triangles by connecting the points with 
line segments. 
(2)Estimate partial derivatives of F with respect 
to x and y at each of the points using the 
data values on either a set of nearby points 
or all of the points. 
(3)For an arbitrary point (x, y) in the convex 
hull of the set of points, determine which 
triangle contains the point, and compute an 
interpolated value F(x, y) using the data 
values and estimated partial derivatives at 
each of the three vertices of the triangle. 
Later, the construction of triangulation from the 
scattered data is described briefly. Three different 
degree polynomials with gradient estimation were 
used to construct two different experimental 
surfaces. According to the error analysis and 
visualized judgement, three algorithms were 
evaluated. 
928 
2. TRIANGULATION IN A PLANE 
Suppose that P - {p; = (x, y,)}4" is a set of n 
distinct points in the plane. The set T = (vii, v2, 
v3, 4! of triples of integers chosen from (1,..., n) 
is called a triangulation of P provided that the 
oints ; ) are the vertices of a triangle 
p Py1, Pv2. Py, 
t; for 1 <i< m. Each triangle contains exactly 
three points of T and these are precisely the 
vertices of the triangle. The interior of the 
triangles Tm are pairwise disjoint, i.e., no 
overlapping. The union of {T;};™ is equal to the 
convex hull of P. 
In general, a given point set P can be triangulated 
in several ways and all triangulations of P can be 
shown by induction as the following relationship: 
m - number of triangles - 2n - ny - 2 
n, = number of edges - 3n - ny -3 
where ny denotes the number of boundary 
vertices. A triangulation is completely described 
by the set T of the integer triples giving the vertices 
of the triangles making up the triangulation. 
Hence, to store a triangulation in a computer, the 
2n numbers describing P and the 3m integers 
describing T are needed. Before constructing the 
triangulation from a general set of points, it will 
be convenient to first consider the problem of 
triangulation a set of four points whose convex 
hull is a convex quadrilateral. In this case there 
- are precisely two different triangulations which 
may denote by t4 and t» (Figure 1). 
  
S 5 JAM ect Cy hp FH 0 
ct 
cet