Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!ames!fred!kerlick
From: kerlick@fred (G David Kerlick)
Newsgroups: comp.graphics
Subject: Re: Interpolation Query.
Message-ID: <3380@ames.arpa>
Date: Thu, 12-Nov-87 13:50:15 EST
Article-I.D.: ames.3380
Posted: Thu Nov 12 13:50:15 1987
Date-Received: Sat, 14-Nov-87 18:42:52 EST
References: <15310@watmath.waterloo.edu>
Sender: usenet@ames.arpa
Reply-To: kerlick@fred.UUCP (G David Kerlick)
Organization: NASA Ames Research Center, Mountain View, CA
Lines: 31
Keywords: interpolation algorithm surface

Gentlemen and Ladies:

For the interpolation of randomly scattered data in 2D or 3D, there
are two main approaches.

In the first approach, an auxiliary rectangular grid is used
and the data is interpolated twice, first to the auxiliary
grid, and then to the desired value of the independent variables.
One can do tricks with smoothing splines, etc, to make the interpolation
satisfy certain rules, for example that the interpolant nowhere
attains a greater value then the original data (no overshoots).
Typical of this approach is the paper of Tom Foley, ACM Transactions
on Graphics, Vol 6 No 1 (Jan 1987) pp 1-18.

In the second approach, the space of independent variables (x,y in the case 
of plotting f(x,y) ) is broken down in to triangular elements by
means of the so-called Delaunay Triangulation.  What is essentially
a Delaunay triangulation is done e.g. in the NCAR plotting library.
(National Center for Atmospheric Research, Boulder Colo).  I don't
know of a production code that does this in 3D (i.e. contours 
f(x,y,z) ).  Papers on this approach include P.J. Green and R. Sibson,
Computer Journal (UK) vol 21 pp 168-173 (1978) and a recent
paper by C.L. Lawson, Computer Aided Geometrical Design, Vol 3 (1986)
pp 231-246, and references cited therein.

Hope this information is helpful.

					G. David Kerlick
					Advanced Computer Graphics Group
					NASA Ames Research Center
					Moffett Field California