2计算复杂度自适应的NURBS曲线插补算法
2.1算法流程
为了清晰的表示插补算法的复杂度，用函数（1）表示NURBS曲线插补算法的性能。
求导次数最高为一次时，性能测试函数表达式为：
求导次数最高为二次时的性能测试函数表达式为：
在NURBS曲线插补时，deBoor-Cox插补算法与基函数插补算法的性能各有优劣，由公式（1）可知，二者的相对性能在m值确定时，由参数曲线次数k、曲线的控制点个数n确定。相应的插补流程如下:
首先，读取首个插补点对应的参数变量u值，并获取NURBS曲线次数k，控制点个数n，求导的最高阶次m。
其次，依据k、n、m，通过计算f(k,n,m)值比较基函数算法与de-Boor算法的算法性能。如果阶次m=1，则计算f(k,n,1)值，若结果大于0，采用基函数法进行曲线求值求导运算，否则采用deBoor-Cox法进行曲线求值求导运算。同理，如果阶次m=1，则计算f(k,n,2)值，若结果大于0，采用基函数法进行曲线求值求导运算，否则采用deBoor-Cox法进行曲线求值求导运算，直到插补结束。
流程图如下:
图1算法流程图
2.2算法性能分析
当m=1，n∈[3…7]，k∈[3…7]时，按照公式（1）和公式（3），deBoor-Cox算法、基函数算法和本文算法的计算复杂度比较如图：
图2计算效率比较
图中采用计算过程中所需的乘/除法运算次数来表示计算的复杂度，可以看出，当曲线次数k和控制点个数n发生变化时，deBoor-Cox算法或基函数法的计算复杂度均不能始终保持最优。本文算法虽在进行自适应选择时增加了一定计算量，但是算法计算复杂度较最小值仅略有增加，采用本文算法，可使计算复杂度一直处于较低水平。
表1NURBS曲线参数
NURBS曲线
控制点
节点向量
曲线一
{10，0}，{20，20}，{12,
8}，{10,20}，{8,8}，{0,20}，{10,0}
{0,0,0,0,
0.2，0.4,0.8,
1,1,1,1}
(7,5)
曲线二
{10,10}，{0,0}，{0,
20}，{10,10}，{20,0}，{20,20}，{10,10}
{0,0,0,0，
0.5,0.5,0.5,
(7,6)
曲线三
{4,2}，{1,11}，{5,16}，{11,16}，{15,11}，{12,2}，{8,0}
0.3,0,4,0,5,
(7,7)
表2算法计算耗时对比
DeBoor-Cox算法
基函数法
本文算法
从表中可以看到本文算法的平均计算耗时要少于deBoor-Cox算法和基函数法，计算效率比Boor-Cox算法提高约25%，比基函数法提高约9%，而且随着、的调整次数增加以及相应值的增大，算法性能提升更加明显。
可以看出，进行NURBS曲线插补运算时，随着曲线次数以及控制顶点个数等参数的变化，deBoor-Cox法与基函数法的算法性能优劣处在相对变化之中。然而基于计算的复杂度进行插补算法自适应选择的新算法，克服了传统方法中仅采用一种计算算法而引起的性能降低问题，明显提高了NURBS曲线插补的平均效率。