A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A New Method of Interpolation and Smooth Curve Fitting Based on Local Procedures

Full text

Pdf (766 KB)

Source

Journal of the ACM (JACM) archive
Volume 17 , Issue 4 (October 1970) table of contents

Pages: 589 - 602

Year of Publication: 1970

ISSN:0004-5411

Author

Hiroshi Akima

ESSA Research Laboratories, Institute for Telecommunication Sciences, Boulder, Colorado

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 49, Downloads (12 Months): 352, Citation Count: 28

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321607.321609 What is a DOI?

ABSTRACT

A new mathematical method is developed for interpolation from a given set of data points in a plane and for fitting a smooth curve to the points. This method is devised in such a way that the resultant curve will pass through the given points and will appear smooth and natural. It is based on a piecewise function composed of a set of polynomials, each of degree three, at most, and applicable to successive intervals of the given points. In this method, the slope of the curve is determined at each given point locally, and each polynomial representing a portion of the curve between a pair of given points is determined by the coordinates of and the slopes at the points. Comparison indicates that the curve obtained by this new method is closer to a manually drawn curve than those drawn by other mathematical methods.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	ACKLAND, T .G . On osculatory interpolation, where the given values of the function are at unequal intervals. J. Inst. Actuar. 9 (1915), 369-375.
	2	AKIMA, H. A method of smooth curve fitting. ESSA Tech. Rep. ERL 101-ITS 73. US Government Printing Office, Washington, D. C., Jan. 1969.
	3	GREVILLE, T. N .E . Spline functions, interpolation, and numerical quadrature. In Mathematical Methods for Digital Computers, Vol. 2, A. Ralston and H. S. Wilf (Eds.), Wiley, New York, 1967, Ch. 8.
	4	Begnaud Francis Hildebrand, Introduction to numerical analysis: 2nd edition, Dover Publications, Inc., New York, NY, 1987
	5	KARUP, J. On a new mechanical method of graduation. In Transactions of the Second International Actuarial Congress. C. and E. Layton, London, 1899, pp. 78-109.
	6	MILNE, W. E. Numerical Calculus. Princeton U. Press, Princeton, N. J., 1949, Ch. III.

CITED BY 28

	Luc Devroye, Sample-based non-uniform random variate generation, Proceedings of the 18th conference on Winter simulation, p.260-265, December 08-10, 1986, Washington, D.C., United States
	Bahattin Koc , Yuan-Shin Lee , Yawei Ma, Max-fit biarc fitting to STL models for rapid prototyping processes, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.225-233, May 2001, Ann Arbor, Michigan, United States
	Henry Moreton , Carlo Séquin, Surface design with minimum energy networks, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.291-301, June 05-07, 1991, Austin, Texas, United States
	George Wolberg , Itzik Alfy, An energy-minimization framework for monotonic cubic spline interpolation, Journal of Computational and Applied Mathematics, v.143 n.2, p.145-188, 15 June 2002
	Luc Devroye, Recent results in non-uniform random variate generation, Proceedings of the 13th conference on Winter simulation, p.517-521, December 09-11, 1981, Atlanta, Georgia, United States
	A. Preusser, Algorithm 671: FARB-E-2D: fill area with bicubics on rectangles—a contour plot program, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.79-89, March 1989
	Won L. Chung, Automatic Curve Fitting Using an Adaptive Local Algorithm, ACM Transactions on Mathematical Software (TOMS), v.6 n.1, p.45-57, March 1980
	Hiroshi Akima, A method of bivariate interpolation and smooth surface fitting based on local procedures, Communications of the ACM, v.17 n.1, p.18-20, Jan. 1974
	Michael W. Vannier , Jeffrey L. Marsh , James O. Warren, Three dimensional computer graphics for craniofacial surgical planning and evaluation, ACM SIGGRAPH Computer Graphics, v.17 n.3, p.263-273, July 1983
	D. F. McAllister , J. A. Roulier , M. Evans, Generation of random numbers using shape preserving quadratic splines, Proceedings of the 16th annual Southeast regional conference, p.216-218, April 13-15, 1978, Atlanta, Georgia
	Hiroshi Akima, Algorithm 433: interpolation and smooth curve fitting based on local procedures [E2], Communications of the ACM, v.15 n.10, p.914-918, Oct. 1972
	Hiroshi Akima, A method of univariate interpolation that has the accuracy of a third-degree polynomial, ACM Transactions on Mathematical Software (TOMS), v.17 n.3, p.341-366, Sept. 1991
	Azriel Rosenfeld, Progress in Picture Processing: 1969--71, ACM Computing Surveys (CSUR), v.5 n.2, p.81-108, June 1973
	N. Burtnyk , M. Wein, Interactive skeleton techniques for enhancing motion dynamics in key frame animation, Communications of the ACM, v.19 n.10, p.564-569, Oct. 1976
	Hiroshi Akima, Bivariate interpolation and smooth surface fitting based on local procedures, Communications of the ACM, v.17 n.1, p.26-31, Jan. 1974
	Daniel J. Filip , Thomas W. Ball, Procedurally Representing Lofted Surfaces, IEEE Computer Graphics and Applications, v.9 n.6, p.27-33, November 1989
	Les Piegl, On NURBS: a Survey, IEEE Computer Graphics and Applications, v.11 n.1, p.55-71, January 1991
	Yates Fletcher , David F. McAllister, A Tension-Compatible Patch for Shape-Preserving Surface Interpolation, IEEE Computer Graphics and Applications, v.9 n.3, p.45-55, May 1989
	Anne Kellerman, An investigation of curve fitting methods using an APL graphics terminal, Proceedings of the sixth international conference on APL, p.249-265, January 1974
	Jean-Laurent Mallet, Discrete smooth interpolation, ACM Transactions on Graphics (TOG), v.8 n.2, p.121-144, April 1989
	Yates Fletcher , David F. McAllister, Curves: Automatic Tension Adjustment for Interpolatory Splines, IEEE Computer Graphics and Applications, v.10 n.1, p.10-17, January 1990
	M. Fischer , P. Oja, Monotonicity preserving rational spline histopolation, Journal of Computational and Applied Mathematics, v.175 n.2, p.195-208, 15 March 2005
	Isabella Cravero , Carla Manni, Shape-preserving interpolants with high smoothness, Journal of Computational and Applied Mathematics, v.157 n.2, p.383-405, 15 August 2003
	Lin Xu, CAD and Graphics: Parametric curve interpolation by combination of two conic sections, Computers and Graphics, v.32 n.6, p.655-659, December, 2008
	Gerald Farin, Geometric Hermite interpolation with circular precision, Computer-Aided Design, v.40 n.4, p.476-479, April, 2008
	A. G. Chao , S. T. Tseng , D. S. H. Wong , S. S. Jang , S. P. Lee, Systematic applications of multivariate analysis to monitoring of equipment health in semiconductor manufacturing, Proceedings of the 40th Conference on Winter Simulation, December 07-10, 2008, Miami, Florida
	Tetsuzo Kuragano , Kazuhiro Kasono, Curve generation and modification based on radius of curvature smoothing, Proceedings of the 10th WSEAS international conference on Mathematical and computational methods in science and engineering, p.80-87, November 07-09, 2008, Bucharest, Romania
	Nuttapong Chentanez , Ron Alterovitz , Daniel Ritchie , Lita Cho , Kris K. Hauser , Ken Goldberg , Jonathan R. Shewchuk , James F. O'Brien, Interactive simulation of surgical needle insertion and steering, ACM Transactions on Graphics (TOG), v.28 n.3, August 2009