Fitting the polyline machining tool path with parametric curves is one of the key problems in CNC machining. There are many methods for data compression and smooth tool path generation. Algorithms based on time-optimal interpolation with velocity, acceleration, and jerk constraints are utilized widely for trajectory planning. In this paper, we present the certified algorithms using cubic B-splines for spatial planning which has much more applications in CNC. The main contribution of this paper can be shortly summarized. Firstly, we provide an explicit representation of Hausdorff distance between spatial polylines and cubic B-spline curves. Secondly, we present the certified curve fitting algorithm for G01 codes. Finally, we address the certified machining trajectory planning algorithm with time parameter curve.