Interpolation-based Curve Approximation Method And Its Application

Curve/surface approximation problem has wide applications in computer graphics,computer aided design,and so on.Most of the approximation problems can be finally reduced to solving a system of nonlinear equations.This paper discusses the curve approximation problem,and provides an interpolation-based method.The content includes:(1)Cubic inner-point-interpolation-based method for approximating offset curves under G~1 constraint.The interpolation-based method needs no information of control polygon of the given curve,and can be applied to the approximation of offset curves of non-polynomial curves.Given an offset curve,a formula is provided for computing cubic Bézier curve which interpolates three points and three of their directional tangent vectors,and it can be turned into a univariate cubic equation.The existence of interpolation curves is also discussed.In principle,it can achieve the optimal approximation order 6 and is expected to achieve a much better approximation effect.The method has a good locality of the calculation.In the part where the tolerance is not satisfied,the number of segments of the corresponding parameter interval can be estimated beforehand,and the other segments of the approximating curve can be unchanged and need no recalculation.Numerical examples show that the new method can achieve much better approximation effect than those of previous methods.(2)Approximating some expressions involving trigonometric functions.There are many methods for approximating trigonometric functions,such as the best square approximation,least squares,fast Fourier transform(FFT),and so on.This paper presents a new method for approximating trigonometric functions.It can be applied to many other approximation problems including the Wilker-CusaHuygens inequality.Compared with the error estimation method of Mortic,the method in this paper can not only recover the results of the Mortic’s method,but also provide a new improvement.Numerical results show that this method can achieve better approximation effect and higher computational efficiency.(3)Clipping method combining interpolation technique with reparameterization technique for the root-finding problem of non-linear equations.For a non-polynomial equation,the computational complexity of solving the bounding polynomials of a given function is almost equivalent to that of solving the roots of the given function.Therefore,prevailing methods based on bounding polynomial technique is difficult to be generalized to non-polynomial cases.By using clipping method combining interpolation technique with reparameterization technique,a new method is provided which can be applied to the root-finding problem of non-polynomial equations.It firstly computes a cubic polynomial interpolating the given smooth function f(t)at four points;and then,it searches two reparameterization functions such that the reparameterized functions have the same derivatives,which leads to higher approximation order and better convergence rate.Comparing with prevailing cubic clipping methods,the new method can achieve the convergence rate 9 or higher for single root cases,and also can directly bound the root without computing the bounding polynomials.Numerical examples show that it can converge to the proper solution even in some cases that the Newton’s method fails.