Optimal Linear Interpolation of Planar Curves for NC Contour Machining

  • Hua Qiu Kyushu Sangyo University
  • Daisuke Matsushita Kyushu Sangyo University, Japan.
  • Tetsurou Yamaguchi Kyushu Sangyo University, Japan.


In NC machining of planar contours, the cutter path is frequently approximated by linear interpolation to a contour curve as target. In this situation, the interpolation error should be measured along the normal direction of the contour curve, and it is desired that only the fewest linear segments are needed with respect to the specified accuracy. However, how to determine the parameters of segment to match these requirements has not been completely solved. This paper presents a new linear interpolation approach for this problem. The approach is named as the optimal linear interpolation method and has three features which include: (1) the interpolation error along the normal direction of object curve satisfies the specified accuracy, and the number of the required segments is the fewest simultaneously; (2) the connection between any two adjacent segments on generated cutter path is natural and smooth, and the generation of extremely short segment is avoided as much as possible; (3) the algorithm is simple and with a high computation efficiency. The effectiveness of the proposed approach has been sufficiently confirmed by applying it to two interpolation examples of planar cam contours. At the same time, the reduction effect of interpolation data has also been verified through comparing the segment number required by the proposed method and Nishioka’s method, which is specially developed to precision machining of planar cam contour, relative to the same interpolation conditions.


A. Cantoni, “Optimal curve fitting with piecewise linear functions”, IEEE Transactions on Computers, Vol.20, No.1, pp.59-67, 1971. DOI: 10.1109/T-C.1971.223082

A. Magnani and S. P. Boyd, “Convex piecewise-linear fitting”, Optimization and Engineering, Vol.10, No.1, pp.1-17, 2009. DOI: 10.1007/s11081-008-9045-3

T. Sasao, S. Nagayama and J. T. Butler, “Numerical function generators using LUT cascades”, IEEE Transactions on Computers, Vol.56, No.6, pp.826-838, 2007. DOI: 10.1109/TC.2007.1033

C. L. Frenzen, T. Sasao and J. T. Butler, “On the number of segments needed in a piecewise linear approximation”, Journal of Computational and Applied Mathematics, Vol.234, No.2, pp.437-446, 2010. DOI: 10.1016/j.cam.2009.12.035

J. T. Butler, C. L. Frenzen, N. Macaria and T. Sasao, “A fast segmentation algorithm for piecewise polynomial numeric function generators”, Journal of Computations and Applied Mathematics, Vol.235, No.14, pp.4076-4082, 2011. DOI: 10.1016/j.cam.2011.02.033

G. Gallego, D. Berjo ́n and N. Garc ́ıa, “Optimal polygonal L1 linearization and fast interpolation of nonlinear systems”, IEEE Transactions on Circuits and Systems I: Regular Papers, Vol.61, No.11, pp.3225-3234, 2014. DOI: 10.1109/TCSI.2014.2327313

D. Berjo ́n, G. Gallego, C. Cuevas, F. Mora ́n and N. Garc ́ia, “Optimal piecewise linear function approximation for GPU-based applications”, IEEE Transactions on Cybernetics, Vol.46, No.11, pp.2584-2595, 2016. DOI: 10.1109/TCYB.2015.2482365

ISO 1101:2017, Geometrical product specifications (GPS)- Geometrical tolerancing-Tolerances of form, orientation, location and run-out.

JIS B 0021:1998, Geometrical product specifications (GPS)- Geometrical tolerancing-Tolerancing of form, orientation, location and run-out.

D. Kiritsis, “High precision interpolation algorithm for 3D parametric curve generation”, Computer-Aided Design, Vol.26, No.11, pp.850-856, 1994. DOI: 10.1016/0010- 4485(94)90100-7

J. G. Dunham, “Optimum uniform piecewise linear approximation of planar curves”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.8, No.1, pp.67-75, 1986. DOI: 10.1109/TPAMI.1986.4767753

H. Qiu, A. Kubo and N. Okamoto, “Errors estimation to linear interpolation cutter path of machining center due to acceleration/deceleration motions between two interpolation segments”, Transactions of the Japan Society of Mechanical Engineers, Series C, Vol.76, No.770, pp.2719-2728, 2010 (In Japanese).

H. Qiu, Y. Yue, A. Kubo, C. Lin, K. Cheng, D. Huo and D. Li, “Performance improvement of the LM device and its application to precise measurement of motion trajectories within a small range with a machining centre”, Modern Mechanical Engineering, Vol.2, No.3, pp.71-85, 2012. DOI: 10.4236/mme.2012.23010

H. Qiu and Y. Zhou, “Influence of NC cutting mode on pro- file contouring of machining center”, Conference Proceedings of the Japan Society of Mechanical Engineers, No.208- 1, H11, 2020-3 (In Japanese).

M. Nishioka, “Contouring of planar cam (1st report, Determination of control points by linear interpolation)”, Transactions of the Japan Society of Mechanical Engineers, Series C, Vol.60, No.571, pp.1047-1052, 1994 (in Japanese).

B. Bhattacharjee, A. Azeem, S. M. Ali and S. K. Paul, “Development of a CNC interpolation scheme for CNC controller based on Runge-Kutta method”, International Journal of Computer Aided Engineering and Technology, Vol.4, No.5, pp.445-464, 2012. DOI: 10.1504/IJ- CAET.2012.048841

Y. Jin, Y. He, J. Fu, Z. Lin and W. Gan, “A fine-interpolation- based parametric interpolation method with a novel real-time look-ahead algorithm”, Computer-Aided Design, Vol.55, pp.37-48, 2014. DOI: 10.1016/j.cad.2014.05.002

T. Taguchi, “Fortran Handbook”, Gijutu-Hyohron, Inc., pp.128-129, 2015 (In Japanese).

T. Taguchi, “Fortran Handbook”, Gijutu-Hyohron, Inc., pp.133-136, 2015 (In Japanese).

H. Qiu, Y. Li, K. Cheng and Y. Li, “A practical evaluation approach towards form deviation for two-dimensional contours based on coordinate measurement data”, International Journal of Machine Tools and Manufacture, Vol.40, No.2, pp.259-275, 2000. DOI: 10.1016/S0890-6955(99)00057-7

H. Makino, “Mechanisms for Automatic Machines”, The Nikkan Kogyo Shimbun, Ltd, pp.28-29, 1976 (in Japanese).

How to Cite
Qiu, H., Matsushita, D., & Yamaguchi, T. (2021). Optimal Linear Interpolation of Planar Curves for NC Contour Machining. Journal of the Institute of Industrial Applications Engineers, 9(3), 66. https://doi.org/10.12792/jiiae.9.66