Newsgroups:     comp.graphics,sci.math
From:           pjt@newton.cs.jhu.edu (Paul Tanenbaum)
Subject:        Delaunay Interpolation
Organization:   Johns Hopkins Computer Science Department, Baltimore, MD
Date:           Tue, 18 Aug 1992 17:41:21 GMT

     Suppose I have a bunch of sample points from the boundary of a closed
volume in $R^3$.  Suppose in particular that I have been given the Delaunay
triangulation of these boundary points.  I'd like to interpolate a $C^3$
surface through these vertices.  The related surface-interpolation algorithms
I've found seem not to be applicable:  they either assume that the
triangulation is regular (usually of degree six) or that the surface is
monotonic with respect to some plane.
     Does there exist an algorithm to solve this problem?  References to
the literature would be greatly appreciated.
     Thanks,
     +++paul

Newsgroups:     comp.graphics,sci.math
From:           watson@maths.uwa.oz.au (David Watson)
Subject:        Re: Delaunay Interpolation
Organization:   University of Western Australia
Date:           Wed, 19 Aug 1992 00:28:55 GMT

pjt@newton.cs.jhu.edu (Paul Tanenbaum) writes:

>     Suppose I have a bunch of sample points from the boundary of a closed
>volume in $R^3$.  Suppose in particular that I have been given the Delaunay
>triangulation of these boundary points.  I'd like to interpolate a $C^3$
>surface through these vertices.  The related surface-interpolation algorithms
>I've found seem not to be applicable:  they either assume that the
>triangulation is regular (usually of degree six) or that the surface is
>monotonic with respect to some plane.
>     Does there exist an algorithm to solve this problem?  References to
>the literature would be greatly appreciated.

There are many ways to interpolate from a Delaunay tesselation.  The quickest
is with barycentric coordinates but is only $C^0$.  If you require higher
smoothness then it is a question of data set size - for 100 data or so just
fit a radial basis spline.  If you must deal with subsets, splines will
give discontinuities at subset boundaries.  Sibson's natural neighbour
interpolation -
Sibson, R., 1981, A brief description of natural neighbour interpolation, _in_ 
Barnett, V., ed., Interpreting multivariate data: John Wiley, p.21--36.
Alfield, P., 1989, Scattered data interpolation in three or more 
variables, _in_ Mathematical methods in computer aided geometric 
design, Lyche, T., and Schumaker, L.L., ed., Academic Press, San Diego,
p. 12-13.
Watson, D.F., and Philip, G.M., 1987, Neighborhood-based interpolation: Geobyte, 2(2),
p. 12--16.
will provide continuous slopes everywhere but at the data points themselves.
Incorporating estimated gradients will give total continuity.

For a summary of interpolation techniques that can be extended to higher
dimensions, see
	ftp marlin.nosc.mil /pub/contour.file
for an ASCII, TeX, or PostScript, file.

Email questions are welcome.
--
Dave Watson                          Internet: watson@maths.uwa.edu.au
Department of Mathematics            
The University of Western Australia               Tel: (61 9) 380 3359
Nedlands, WA 6009  Australia.                     FAX: (61 9) 380 1028

Newsgroups:     comp.graphics.algorithms
From:           ensab@gdr.bath.ac.uk (A Bowyer)
Subject:        Re: Contours - How to draw ?
Organization:   School of Mechanical Engineering, University of Bath, UK
Date:           Tue, 31 Aug 1993 19:10:12 GMT

In the referenced article, ma@informatik.uni-kiel.dbp.de (Martin Ameskamp) writes:
>In <25pfi0$aqs@aggedor.rmit.OZ.AU> s914373@minyos.xx.rmit.OZ.AU (Simon Bullen) writes:
>
>>ajb@oasis.icl.co.uk (Adam Buckley) writes:
>>	A nice general way to make contour maps from a set of _ANY_ points
>>(ie you don't need a regular grid) is to calculate the Delaunay triangulation
>>from your set of points, and then doing the contour map is pretty easy.
>
>>	The Delaunay triangulation will turn your set of points into a 
>>surface composed entirely of triangles; then you merely need to solve the
>>contour map problem for each triangle in the graph, which is fairly straight
>>forward. You could then pass it through a bezier curve routine to smooth out
>>the straight lines, if you liked.
>
>Right, triangulation is almost always a good idea. I'm not so sure about
>the Bezier bit, though. After all, you expect certain things from contours,
>e.g. you wouldn't really like them to intersect, and I don't see how you could
>guarantee that by applying Bezier routines to a given set of (correct)
>piecewise linear contours.
>
>Martin
>--
>Martin Ameskamp, Inst. f. Informatik I (Computing Dept.)
>Kiel University, Olshausenstr. 40, 24118 Kiel, Germany
>Fax: ++49 431 8804054, Voice: ++49 431 8804474, 
>email: ma@informatik.uni-kiel.d400.de

The trouble with countouring methods based on Delaunay triangulations is
that they can `click' (i.e. produce contours with spurious kinks) on
near-degenerate data.  It's better to use natural-neighbour interpolation
(invented by Robin Sibson) on the Voronoi dual of the Delaunay triangulation.
Start with

Sibson, R, and Thompson, G.D. `A seamed Quadratic Element for Contouring' and
follow the reference tree.

			Adrian Bowyer

Part of Geometry in Action, a collection of applications of computational geometry.
David Eppstein, Theory Group, ICS, UC Irvine.

Last update: .