A Hash Approach to Refine CNC Computation of Arc Length and Parameter of NURBS with High Efficiency and Precision

A hash method is proposed to compute bi-directionally the arc length and the parameter of the NURBS curve in curve interpolation. By using a hash table that adopts a doubly linked circular list and a red-black tree, the method first computes the arc lengths corresponding to each initial knot value and stores the computed results in the hash table by means of an ingenious searching-and-computing technique. With the fast search capability of the hash algorithm, the stored data can be rapidly located to form a tiny interval for computing either the arc length or the parameter, greatly shortening the computation period and highly improving the computational precision. Experiments show that the proposed method is tens or even thousands of times more rapid and precise than the classical ones and is helpful to develop high-performance interpolators.