home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / graphics / 8961 < prev    next >
Encoding:
Internet Message Format  |  1992-08-18  |  2.6 KB
  1. Xref: sparky comp.graphics:8961 sci.math:10384
  2. Newsgroups: comp.graphics,sci.math
  3. Path: sparky!uunet!munnari.oz.au!uniwa!watson
  4. From: watson@maths.uwa.oz.au (David Watson)
  5. Subject: Re: Delaunay Interpolation
  6. Message-ID: <1992Aug19.002855.8728@uniwa.uwa.edu.au>
  7. Keywords: surface interpolation, Delaunay triangulation, CAGD
  8. Sender: news@uniwa.uwa.edu.au (USENET News System)
  9. Nntp-Posting-Host: madvax.maths.uwa.oz.au
  10. Organization: University of Western Australia
  11. References: <1992Aug18.174121.18067@blaze.cs.jhu.edu>
  12. Date: Wed, 19 Aug 1992 00:28:55 GMT
  13. Lines: 41
  14.  
  15.  
  16. pjt@newton.cs.jhu.edu (Paul Tanenbaum) writes:
  17.  
  18. >     Suppose I have a bunch of sample points from the boundary of a closed
  19. >volume in $R^3$.  Suppose in particular that I have been given the Delaunay
  20. >triangulation of these boundary points.  I'd like to interpolate a $C^3$
  21. >surface through these vertices.  The related surface-interpolation algorithms
  22. >I've found seem not to be applicable:  they either assume that the
  23. >triangulation is regular (usually of degree six) or that the surface is
  24. >monotonic with respect to some plane.
  25. >     Does there exist an algorithm to solve this problem?  References to
  26. >the literature would be greatly appreciated.
  27.  
  28. There are many ways to interpolate from a Delaunay tesselation.  The quickest
  29. is with barycentric coordinates but is only $C^0$.  If you require higher
  30. smoothness then it is a question of data set size - for 100 data or so just
  31. fit a radial basis spline.  If you must deal with subsets, splines will
  32. give discontinuities at subset boundaries.  Sibson's natural neighbour
  33. interpolation -
  34. Sibson, R., 1981, A brief description of natural neighbour interpolation, _in_ 
  35. Barnett, V., ed., Interpreting multivariate data: John Wiley, p.21--36.
  36. Alfield, P., 1989, Scattered data interpolation in three or more 
  37. variables, _in_ Mathematical methods in computer aided geometric 
  38. design, Lyche, T., and Schumaker, L.L., ed., Academic Press, San Diego,
  39. p. 12-13.
  40. Watson, D.F., and Philip, G.M., 1987, Neighborhood-based interpolation: Geobyte, 2(2),
  41. p. 12--16.
  42. will provide continuous slopes everywhere but at the data points themselves.
  43. Incorporating estimated gradients will give total continuity.
  44.  
  45. For a summary of interpolation techniques that can be extended to higher
  46. dimensions, see
  47.     ftp marlin.nosc.mil /pub/contour.file
  48. for an ASCII, TeX, or PostScript, file.
  49.  
  50. Email questions are welcome.
  51. --
  52. Dave Watson                          Internet: watson@maths.uwa.edu.au
  53. Department of Mathematics            
  54. The University of Western Australia               Tel: (61 9) 380 3359
  55. Nedlands, WA 6009  Australia.                     FAX: (61 9) 380 1028
  56.