Robert J. Renka
Abstract
We present results of accuracy tests on scattered-data fitting methods that have been published as ACM algorithms. The algorithms include seven triangulation-based methods and three modified Shepard methods, two of which are new algorithms. Our purpose is twofold: to guide potential users in the selection of an appropriate algorithm and to provide a test suite for assessing the accuracy of new methods (or existing methods that are not included in this survey). Our test suite consists of five sets of nodes, with nodes counts ranging from 25 to 100, and 10 test functions. These are made available in the form of three Fortran subroutines: TESTDT returns one of the node sets; TSTFN1 returns a value and, optionally, a gradient value, of one of the test funciton; and TSTFN2 returns a value, first partials, and second partial derivatives of one of the test functions.
Supplemental Material
Available for Download
Software for "Accuracy test of ACM algorithms for interpolation of scattered data in the plane"
- AKIMA, H. 1978a. Algorithm 526: Bivariate interpolation and smooth surface fitting for irregularly distributed data points. ACM Trans. Math. Softw. 4, 2 (June 1978), 160-164. Google Scholar
- AKIMA, H. 1978b. A method of bivariate interpolation and smooth surface fitting for irregularly distributed data points. ACM Trans. Math. Softw. 4, 2 (June 1978), 148-159. Google Scholar
- AKIMA, H. 1996. Algorithm 761: Scattered data surface fitting that has the accuracy of a cubic polynomial. ACM Trans. Math. Softw. 22, 3 (Sept.), 362-371. Google Scholar
- BARNHILL, R. E. 1977. Representation and approximation of surfaces. In Mathematical Software III, J. R. Rice, Ed. Academic Press, Inc., New York, NY, 69-120.Google Scholar
- BENTLEY, g. L. AND FRIEDMAN, g. H. 1979. Data structures for range searching. ACM Comput. Surv. 11, 4 (Dec.), 397-409. Google Scholar
- BROWN, R. 1997. TableCurve 3D. Version 3. SPSS, Inc., Chicago, IL.Google Scholar
- CLOUGH, R. W. AND TOCHER, g. L. 1965. Finite elements stiffness matrices for analysis of plates in bending. In Proceedings of the Conference on Matrix Methods in Structural Mechanics.Google Scholar
- FRANKE, R. 1979. A critical comparison of some methods for interpolation of scattered data. NPS-53-79-003. Dept. of Mathematics, Naval Postgraduate School, Monterey, CA.Google Scholar
- FRANKE, R. 1982. Scattered data interpolation: Tests of some methods. Math. Comput. 38, 157 (Jan.), 181-200.Google Scholar
- FRANKE, R. AND NIELSON, G. 1980. Smooth interpolation of large sets of scattered data. Int. J. Numer. Method. Eng. 15, 1691-1704.Google Scholar
- PREUSSER, A. 1990a. Algorithm 684: C1- and C2-interplation on triangles with quintic and nonic bivariate polynomials. ACM Trans. Math. Softw. 16, 3 (Sept. 1990), 253-257. Google Scholar
- PREUSSER, A. 1990b. Efficient formulation of a bivariate nonic C2-hermite polynomial on triangles. ACM Trans. Math. Softw. 16, 3 (Sept. 1990), 246-252. Google Scholar
- RENKA, R.J. 1988a. Algorithm 660: QSHEP2D: Quadratic Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 14, 2 (June 1988), 149-150. Google Scholar
- RENKA, R.J. 1988b. Multivariate interpolation of large sets of scattered data. ACM Trans. Math. Softw. 14, 2 (June 1988), 139-148. Google Scholar
- RENKA, R.J. 1996a. Algorithm 751: TRIPACK: Constrained two-dimensional Delaunay triangulation package. ACM Trans. Math. Softw. 22, 1 (Mar.), 1-8. Google Scholar
- RENKA, R.J. 1996b. Algorithm 752: SRFPACK: Software for scattered data fitting with a constrained surface under tension. ACM Trans. Math. Softw. 22, 1 (Mar.), 9-17. Google Scholar
- RENKA, R. J. AND BROWN, R. 1998. Remark on Algorithm 761. ACM Trans. Math. Softw. 24, 4 (Dec.), 383-385. Google Scholar
- RENKA, R. J. AND BROWN, R. 1999a. Algorithm 790: CSHEP2D: Cubic Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25, 1 (Mar.). This issue. Google Scholar
- RENKA, R. J. AND BROWN, R. 1999b. Algorithm 791: TSHEP2D: Cosine series Shepard method for bivariate interpolation of scattered data. ACM Trans. Math. Softw. 25, 1 (Mar.). This issue. Google Scholar
- SCHUMAKER, L. L. 1976. Fitting surfaces to scattered data. In Approximation Theory, G. G. Lorentz, C. K. Chui, and L. L. Schumaker, Eds. Academic Press, Inc., New York, NY.Google Scholar
- SHEPARD, D. 1968. A two-dimensional interpolation function for irregularly spaced data. In Proceedings of the 23rd ACM National Conference. ACM, New York, NY, 517-524. Google Scholar
Index Terms
- Algorithm 792: accuracy test of ACM algorithms for interpolation of scattered data in the plane
Recommendations
Algorithm 791: TSHEP2D: cosine series Shepard method for bivariate interpolation of scattered data
We describe a new algorithm for scattered data interpolation. It is based on a modified Shepard method similar to that of Algorithm 660 but uses 10-parameter cosine series nodal functions in place of quadratic polynomials. Also, the interpolant has ...
Algorithm 790: CSHEP2D: cubic Shepard method for bivariate interpolation of scattered data
We describe a new algorithm for scattered data interpolation. The method is similar to that of Algorithm 660 but achieves cubic precision and C2 continuity at very little additional cost. An accompanying article presents test results that show the ...
Tri-cubic polynomial natural spline interpolation for scattered data
In this paper an interpolation problem for 3D scattered data defined on a rectangular parallelepiped with natural boundary conditions is considered. By using spline function theory in Hilbert space, we discuss the existence, uniqueness and ...
Comments