基于渐进迭代逼近的平面曲线等距线算法

陈 青，潘日晶

（福建师范大学数学与计算机科学学院，福州350007）

基于渐进迭代逼近的平面曲线等距线算法

陈 青，潘日晶

（福建师范大学数学与计算机科学学院，福州350007）

针对传统平面曲线等距线求解算法在适应性、误差控制等方面存在的问题，基于渐进迭代逼近方法提出一种新的平面曲线等距线算法。通过基曲线上点的切矢转角对基曲线进行自适应采样，得到一条逼近等距线的折线，将曲线与曲线的逼近问题转化为折线与曲线的逼近问题。在充分反映基曲线形状特征的前提下尽可能减少采样点数量。选取等距线上的特征点作为主控制点，利用渐进迭代逼近方法插值所选取的主控制点，得到逼近折线的B样条曲线。给出误差控制方法，同时利用渐进迭代逼近方法的局部性，使所得逼近等距曲线的B样条曲线达到预先给定的精度。实验结果表明，该算法直观简洁，易于实现，可应用于任意平面参数曲线及函数曲线，并且其无需求解线性方程组，运算效率较高。

采样点；切矢；特征点；等距线；B样条曲线；渐进迭代逼近

1 概述

等距操作是计算机辅助几何设计系统中一个重要的几何运算，在CAD/CAM的很多领域中都有广泛的应用，如数控加工、汽车车身设计等。但与此同时，等距计算又是一个十分困难的几何运算，与基曲线相比，往往等距曲线的表达形式复杂，不利于实际应用。因此，对于等距曲线的研究是计算机辅助几何设计的一个重要课题。在工程实际应用中，通常采用逼近方法，即用简单且适用于CAD/CAM系统的曲线近似地表示等距曲线，如B样条曲线、多项式曲线等。

等距曲线的逼近方法主要有以下4种类型：（1）基于控制顶点偏移的方法［1-3］，此类方法直接偏移基曲线的控制顶点，再用偏移得到的控制多边形生成基曲线的等距逼近曲线。虽然其几何直观性较强，且不需要求解线性方程组，但曲线的表达式中需有控制顶点，故此类方法不能应用于任意表达形式的平面曲线，且大部分此类方法易造成最终得到的曲线控制顶点过多。另一方面，往往误差控制不够精确。（2）插值拟合的方法［4-6］。此类方法虽然对曲线的表达形式无特殊要求，但由于其拟合过程往往需要求解大量的线性方程组，因此造成计算上耗时较多。（3）包络方法［7］。此类方法得到的逼近曲线次数过高。（4）其他方法［8-10］。文献［8-9］的方法最终得到的逼近曲线次数过高。文献［10-11］中提出的方法不能直接应用于NUBRS曲线。

从实际工程应用的角度来看，在求解平面曲线的等距曲线时，应综合考虑以下6个方面的问题：（1）算法简单；（2）精度高；（3）符合NURBS标准；（4）运算速度快；（5）适用任意曲线；（6）生成的控制顶点个数较少。本文针以上问题，结合渐进迭代逼近算法［11-12］（Progressive-iteration Approximation，PIA）提出一种新的平面等距曲线算法。

2 基于PIA的平面曲线等距线算法

本文要解决的问题是：给定一条平面参数曲线C（t）=（x（t），y（t）），t∈［t0，tn］和等距距离d，要求寻找一条逼近曲线C（t）的等距线Cd（t）的B样条曲线。其实，对于函数曲线y=y（x），本文的提出的算法也是适用的，即可，下文称曲线C（t）为基曲线。

本文算法的基本设计思想是：先离散化基曲线，得到逼近等距曲线的折线，将曲线与曲线的逼近问题转化为曲线与折线的逼近问题，然后利用PIA算法逼近经离散化得到的折线。

本文算法的基本步骤是：利用基曲线C（t）上两点的切矢转角α的改变量来确定给定平面参数曲线的采样点集｛oj，j=0，1，…，m｝，同时求得相应等距线上的采样点集，并控制采样误差，其中，ε是预设的全局误差阈值。将采样点集｛pj，j=0，1，…，m｝依次连接，得到一条逼近等距线Cd（t）的折线Ld，即将曲线与曲线的逼近问题转化为折线与曲线的逼近问题。对得到的采样点集｛pj，j=0，1，…，m｝参数化，接着构造初始B样条曲线：

其中，｛p（0）i=pji，i=0，1，…，l｝，l＜m，pji是从采样点集｛pj；j=0，1，…，m｝中选取的主控制点，作为B样条曲线的初始控制顶点，Bi，p（t）是一组由节点向量｛tj，j=0，1，…，l+p+1｝确定的p次规范B样条基函数。然后采用PIA算法通过迭代直到逼近误差时停止迭代。最终得到的B样条曲线插值所选的主控制点pji，并逼近由采样点集｛pj，j=0，1，…，m｝连成的折线Ld。当逼近误差或ea2，则需在不满足误差处插入节点向量，继续迭代，直到满足误差为止。其中，ea=ea1+ea2，ea1为控制采样点和逼近曲线的误差，ea2为控制折线段与对应逼近曲线段的误差。除了个别拐点处，该算法最后能保证等距逼近曲线（t）与等距曲线Cd（t）的全局误差控制在预设的误差阈值ε内。以上过程中的采样过程、采样点｛pj，j=0，1，…，m｝的参数化方法、主控制点p（0）i的选取方法、节点向量｛tj，j=0，1，…，l+p+1｝的构造方式、PIA迭代过程、逼近误差ea的控制方法将分别在下文2.1节～2.6节中具体给出。

2.1 采样算法及采样点序列的参数化

采样的原则之一要保证2个采样点之间的曲线段是凸曲线，故必须将曲线的拐点取作采样点。基曲线的拐点与其等距曲线的拐点存在一一对应的关系。曲线上其切矢转角符号发生改变的位置即为拐点位置。规定切矢转角逆时针为正，顺时针为负，方向是沿着参数值增大的方向转动的。拐点如图1所示，其中设点A为拐点。

图1 拐点取法示意图

利用正弦函数的奇偶性，曲线C（t）与C（t+Δt）之间的切矢转角α的计算公式如下：

α=arcsin（sinα）

采样的原则之二是保证相邻两采样点之间的切矢转角控制在预定的阈值范围内，且等距线上相应的曲线段与其弦的距离在预定的误差范围内。目的是使得等距曲线上的取样点能充分反映基曲线C（t）形状特征，且控制由等距曲线上采样点确定的折线在误差范围内全局逼近等距曲线，在此前提下尽可能地减少采样点数量。下面给出采样算法：

算法 SAMPLE

输入 平面参数曲线C（t）=（x（t），y（t）），t∈［t0，tn］，预定的参数步长初值Δt，预定的角度阈值δ0，δ1，δ2（0＜δ0＜δ1＜δ2），预定的采样误差阈值ec

输出 满足采样误差的等距曲线Cd（t）采样点序列集｛pj，j=0，1，…，m｝，取基曲线C（t）的首末点作为采样点t←t0，tmp←Δt

运用本文的采样算法，可以保证基曲线的特征点被完整保留，且曲线在曲率变化大的地方所取的样点较密，在曲线曲率变化小的地方所取的样点较疏，这样就能达到用尽可能少但又足以保留曲线原有特征的一系列采样点。再将这些采样点集｛pj；j= 0，1，…，m｝顺次连接起来，得到逼近等距线的折线Ld，并且Ld与等距曲线的全局误差严格控制在预定的误差范围内。其中，采样点的数量可以通过调整角度阈值δ1，δ2的取值来改变。

等距曲线Cd（t）上的采样点序列｛pj，j=0，1，…，m｝的参数取为基曲线C（t）上对应采样点的参数。设其参数序列为｛tj，j=0，1，…，m｝且满足tj＜tj+1。

2.2 初始控制顶点的选取

等距曲线Cd（t）上的采样点序列｛pj，j=0，1，…，m｝实际上显示了等距线的基本形状，而曲线C（t）的特征点与其等距线Cd（t）的特征点是一一对应的关系，如拐点。为了达到更好的逼近效果，这些特征点都应选取为主控制点，其余的主控制点按如下方法进行选取：

计算各个采样点的离散曲率：

其中，Δpj和Δ2pj分别是采样点pj的向前一阶差分和二阶差分，进而生成了离散的采样点的曲率序列：

选取K=｛kj，j=0，1，…，m｝中局部曲率极大值点，即满足kj-1＜kj，kj+1＜kj以及采样点的首、末点。再与特征点一起构成采样点序列｛pj，j=0，1，…，m｝的主控制点序列｛pj0，pj1，pj02，…，pjl｝，并将主控制点作为迭代的初始控制顶点，表示为：

2.3 节点向量的构造

本文节点向量的构造采用平均的方法。初始B样条曲线的初始控制顶点序列｛p（0）i=pji，i= 0，1，…，l｝的参数序列如下：

则p次（p+1阶）初始B样条曲线的节点向量序列构造如下：

2.4 渐进迭代逼近插值采样点

采用PIA算法插值这些主控制点｛pji，i=0，1，…，l｝，PIA算法是通过不断调整控制顶点来最终插值所取的型值点集。将｛pji，i=0，1，…，l｝作为初始控制顶点，构造初始B样条曲线r（0）（t）=（t），其中Bi，p（t），i=1，2，…，l是一组由节点向量｛tj，j=0，1，…，l+p+1｝定义的p次规范B样条基函数，其组成一个标准全正基［14］。PIA算法迭代过程如下：第i个控制顶点的第一次调整差向量取为，把作为新的控制顶点，得到第一次迭代后的B样条曲线：

假设通过k次迭代后，产生曲线r（k）（t），则控制顶点的调整差向量为，控制顶点沿相应的调整差向量的方向移动，即，从而得到第k+1条曲线，即：

迭代过程如图2所示。

图2 迭代非均匀B样条曲线（r（k）（t）→r（k+1）（t））

2.5 逼近误差控制

由于本文的思想是将基曲线离散化，得到逼近等距线的折线，将曲线与曲线的逼近问题转化为曲线与折线的逼近问题，为保证在全局上控制曲线的逼近误差，需考虑2个方面的逼近误差：

（1）等距线Cd（t）与离散化折线Ld的全局误差，在2.1节给出的采样算法SAMPLE中，只要取采样误差阈值ec=ε/2，就可将等距线Cd（t）与折线Ld的全局误差控制在范围内。

（2）折线Ld与逼近的B样条曲线的误差，可分如下2个部分将该误差控制在范围内：

1）点与点的逼近误差控制：利用PIA算法得到逼近等距曲线的B样条曲线r（k）（t），t∈［t0，tn］插值于所选取的主控制点｛pji，i=0，1，…，l｝（这里设迭代插值产生的误差忽略不计），而在每两个主控制点pji-1，pjl之间还存在一些采样点ps=pji-1，ps+1，ps+2，…，pe= pji，利用参数的对应关系，分别控制这些采样点和逼近曲线上对应点的距离，当时，则说明该处已达到逼近的误差精度，其中， k表示逼近曲线的迭代次数，ea1=ε/4，ε是预设的拟合误差阈值。若，则说明该处未达到精度要求，需要在最大处插入节点，B样条曲线节点插入可采用伯姆算法［15］，将该采样点对应的参数值作为新节点插入到节点向量中，则相应的使B样条曲线r（k）（t）增加一个控制顶点。当然，对多个误差较大的点，可以同时对其进行插入节点，以提高算法效率。

2）B样条曲线段与折线段的逼近误差控制：计算采样折线和逼近曲线的逼近程度来估计误差。如图3所示，pi和pi+1是等距线上的采样点，对应的参数值分别为ti和ti+1，Qi和Qi+1是逼近等距曲线r（k）（t）上的参数对应点，r（k）′（ti）和r（k）′（ti+1）分别是Qi和Qi+1的切矢向量，设两切矢向量交于点B，点B到线段QiQi+1的距离为h（k）i上面一步保证了点Qi和pi，Qi+1和pi+1的充分接近，就有线段QiQi+1和线段pipi+1充分接近，只要控制逼近曲线段r（k）（t），其中，t∈［ti，ti+1］充分接近线段QiQi+1即可，即保证。若不满足该条件，则在最大误差点处插入新的节点向量。直到满足误差精度。同样，对多个误差较大的处，可以同时对其进行插入节点，以提高算法效率。需要指出用高h控制误差，对个别含有拐点的局部有可能不能完全控制。

图3 误差控制示意图

2.6 算法过程

基于PIA的平面等距曲线算法具体描述如下：

输入 任意表达形式的平面参数曲线C（t），t∈［t0，tn］，等距距离d，精度ε，步长初值Δt，角度阈值δ0，δ1，δ2。

Step1 对平面参数曲线C（t）进行采样操作。得到基曲线上的采样点集

Step2 由等距公式Cd（t）=C（t）+d·N（t）计算相应等距曲线上的采样点｛pj，j=0，1，…，m｝后，并将采样点依次用线段连接起来，得到折线Ld。

Step3 选出等距曲线的特征点、首末点和局部曲率极大值点作为PIA算法的主控制点序列。

Step4 运用PIA算法插值主控制点序列，得到逼近等距曲线的B样条曲线。

Step5 计算各个等距线上的采样点和逼近曲线上对应点的距离，若不满足精度要求，在处插入节点，转Step4。

若Step5和Step6已达到，则终止。

注：本文算法的Step5和Step6可以同时插入多个节点。

3 实验与结果分析

应用本文提出的针对任意平面曲线等距线逼近算法，本节给出3个实例，其分别从不同角度验证本算法的有效性。其中，例1从误差控制角度说明本文算法能有效控制逼近等距线的误差；例2从最终得到的逼近曲线的控制顶点数量上和其他方法比较。例3是将该算法应用于一般的函数曲线。

例1 基曲线是一条五次Bezier曲线，其6个控制顶点为：

曲线的等距距离为d=1。先对基曲线进行采样，取参数步长初值为Δt=0.02，角度阈值δ0=，分别选取38个采样点中的8个，16个，20个主控制顶点，再用PIA算法生成等距曲线实验结果如图4所示。

图4 五次Bezier曲线采样图及其等距线的生成

图4（a）是运用本文的采样方法得到的38个采样点。可以看出采样结果在曲线走势平缓处取点较少，反之取点较密，能充分反映基曲线的特征。图4（b）中的逼近曲线达到预定误差ε=10-2。图4（c）中的逼近曲线达到预定误差ε=10-3，图4（d）中的逼近曲线达到预定误差ε=10-4，可以看出随着主控制顶点的增多，等距曲线的逼近程度越精确。

图5 三次Bezier曲线采样图及其等距线的生成

图5 （b）中的逼近曲线达到预给误差ε=0.01，需要10个控制顶点。图5（c）中的逼近曲线达到预给误差ε=0.000 1，需要15个控制顶点，图5（d）中的逼近曲线达到ε=0.000 01，需要21个控制顶点。以上都是在算法迭代20次情况下的结果。表1为在不同精度要求下应用不同方法求本例三次Bezier曲线等距线所需的控制顶点数的比较。

表1 逼近三次Bezier曲线等距线所需的控制顶点数

可以看出，在同样的精度下，应用本文方法得到的控制顶点数较少。

例3 对于函数y=sin x+2cos x+x，x∈［-3.14，3.14］，可将其表示为参数曲线形式：

取曲线的等距距离d=1，采样的参数步长初值，Δt=0.01，角度阈值δ0=0.01/π，δ1=1/π，δ2=1/π，运用本文算法所得到的等距曲线的B样条逼近曲线的结果如图6所示。

图6（b）中的逼近曲线达到预给误差ε=0.01，图6（c）中的逼近曲线达到预给误差ε=0.001，图6（d）中的逼近曲线达到预给误差ε=0.000 1，可以看出，随着主控制顶点的增多，等距曲线的逼近程度越精确，误差也越来越小。

图6 一般函数曲线采样图及其等距线的生成

4 结束语

本文算法在对等距曲线进行采样的过程为自适应的，可保证在曲线曲率变化大的地方取较多的采样点，在曲线曲率变化小的地方取较少的采样点，这样既保持了曲线的几何性质，又减少了采样点的数目，使算法更加快速。再应用渐进迭代方法插值所取的等距线上的主控制点，较之前应用最小二乘方法来逼近等距曲线，使算法效率得到提高。同时，由于渐进迭代算法具有局部性，因此在误差大的地方可以局部地进行迭代。本文算法可应用于任意的平面参数曲线及函数曲线，能对逼近曲线进行全局误差控制，且得到的B样条逼近曲线的控制顶点数较少。下一步将在以下3个方面对本文算法进行改进：（1）在迭代过程中，考虑曲线的几何特性以更好地控制等距逼近曲线的形状。（2）进一步控制等距逼近曲线的误差。（3）将本文算法推广到曲面上。

［1］ Cobb B.Design of Sculptured Surfaces Using the B-spline Representation［D］.Salt Lake City，USA：Univesity of Utah，1984.

［2］ Coquillart S.Computing Offset of B-spline Curves［J］. Computing Aided Design，1987，19（6）：305-309.

［3］ 刘利刚，王国瑾.基于控制顶点偏移的等距曲线最优逼近［J］.软件学报，2002，13（3）：398-403.

［4］ Hoschek J，Wissel N.Optimal Approximate Conversion of Spline Curves and Sp line Approximation of Offset Curves［J］.Computing Aided Design，1988，20（8）：475-483.

［5］ Piegl L A，Tiller W.Computing Offsets of NURBS Curves and Surfaces［J］.Computing Aided Design，1999，31（2）：147-156.

［6］ Khan M A，Chen Z C.Approximation of Planar O ffset Curves w ith Globally Bounded Error for B-spline NC Tool Paths［J］.International Journal of Production Research，2012，50（23）：6811-6825.

［7］ Shih J L，Chuang S H F.One-sided Offset Approximation of Freeform Curves for Interference-free NURBS Machining［J］.Computer Aided Design，2008，40（9）：931-937.

［8］ Zhao Hongyan，Wang Guojin.Error Analysis of Reparametrization Based Approaches for Curve Offsetting［J］. Computer Aided Design，2007，39（2）：142-148.

［9］ Zhao Hongyan，Wang Guojin.Offset Approximation Based on Reparameterizing the Path of a Moving Point A long the Base Circle［J］.Applied Mathematics：A Journal of Chinese Universities，2009，24（4）：431-442.

［10］ Ahn Y J，Hoffmann C，Kim Y S.Curvature Continuous Offset Approximation Based on Circle Approximation Using Quadratic Bezier Biarcs［J］.Computing Aided Design，2011，43（8）：1011-1017.

［11］ Lin Hongwei，Wang Guojin，Dong Chenshi.Constructing Iterative Non-uniform B-spline Curve and Surface to Fit Data Points［J］.Science in China Series F：Information Sciences，2004，47（3）：315-331.

［12］ Lin Hongwei，Zhang Zhiyu.An Extended Iterative Format for the Progressive-iteration Approximation［J］.Computers& Graphics，2011，35（5）：967-975.

［13］ 施法中.计算机辅助几何设计与非均匀有理B样条［M］.1版.北京：北京航空航天大学社，1994.

［14］ Lin Hongwei，Bao Hujun，Wang Guojin.Totally Positive Bases and Progressive Iteration Approximation［J］. Computings and Mathematics with Applications，2005，50（3/4）：575-586.

［15］ Boehm W.Inserting New Knots into B-spline Curves［J］. Computer Aid Design，1980，12（4）：199-201.

［16］ 严兰兰，宋来忠.正则Bezier曲线的等距线及其计算机实现［J］.计算机与数字工程，2006，34（8）：129-131.

［17］ Gu Jiulong，Jung Y.Approximation of Planar Offset Curves Using Quadratic Trigonometric Splines with Shape Parameter［J］.International Journal of Precision Engineering and Manufacturing，2013，14（11）：1881-1890.

编辑 金胡考

Algorithm for Offset of Planar Curve Based on Progressive-iteration Approximation

CHEN Qing，PAN Rijing
（College of Mathematics and Computing Science，Fujian Normal University，Fuzhou 350007，China）

Aiming at the existing problems in the computation of planar offset curves such as adaptability and error control，this paper proposes a new algorithm for generating the approximation offset of planar curves based on the Progressive-iteration Approximation（PIA）.This algorithm generates line segments approximating the exact offset curve by adaptive sampling on the progenitor curve with tangent vector angle that transfers the problem of approximating curve to that of curve approximating line segments.It reduces the number of sample point as possible at the premise of reflecting the shape feature of the progenitor curve.Then the algorithm selects the characteristic points on the offset curve as the dominant points，and interpolates the dominant points by using the PIA to generate a B-spline curve approximating the line segments. The B-spline curve can approximate the offset curve under the given error by utilizing the method of error control proposed in this paper and the locality of PIA.Experimental result shows that this algorithm is of intuition and easy implementation，which can be used directly for arbitrary planar parameter curve and function curve.It can increase the operating efficiency of the algorithm without solving a global linear equation system.

sampling point；tangent vector；characteristic point；offset；B-spline curve；Progressive-iteration Approximation（PIA）

陈 青，潘日晶.基于渐进迭代逼近的平面曲线等距线算法［J］.计算机工程，2015，41（11）：287-293，298.

英文引用格式：Chen Qing，Pan Rijing.Algorithm for Offset of Planar Curve Based on Progressive-iteration Approximation［J］.Computing Engineering，2015，41（11）：287-293，298.

1000-3428（2015）11-0287-07

A

TP391

10.3969/j.issn.1000-3428.2015.11.049

福建省自然科学基金资助项目（2010J01318）。

陈 青（1989-），女，硕士研究生，主研方向：图像处理，计算几何；潘日晶，教授。

2014-10-09

2014-11-06 E-m ail：554506497@qq.com