陳 青，潘日晶

（福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州350007）

基于漸進(jìn)迭代逼近的平面曲線等距線算法

陳 青，潘日晶

（福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州350007）

針對(duì)傳統(tǒng)平面曲線等距線求解算法在適應(yīng)性、誤差控制等方面存在的問題，基于漸進(jìn)迭代逼近方法提出一種新的平面曲線等距線算法。通過基曲線上點(diǎn)的切矢轉(zhuǎn)角對(duì)基曲線進(jìn)行自適應(yīng)采樣，得到一條逼近等距線的折線，將曲線與曲線的逼近問題轉(zhuǎn)化為折線與曲線的逼近問題。在充分反映基曲線形狀特征的前提下盡可能減少采樣點(diǎn)數(shù)量。選取等距線上的特征點(diǎn)作為主控制點(diǎn)，利用漸進(jìn)迭代逼近方法插值所選取的主控制點(diǎn)，得到逼近折線的B樣條曲線。給出誤差控制方法，同時(shí)利用漸進(jìn)迭代逼近方法的局部性，使所得逼近等距曲線的B樣條曲線達(dá)到預(yù)先給定的精度。實(shí)驗(yàn)結(jié)果表明，該算法直觀簡潔，易于實(shí)現(xiàn)，可應(yīng)用于任意平面參數(shù)曲線及函數(shù)曲線，并且其無需求解線性方程組，運(yùn)算效率較高。

采樣點(diǎn)；切矢；特征點(diǎn)；等距線；B樣條曲線；漸進(jìn)迭代逼近

1 概述

等距操作是計(jì)算機(jī)輔助幾何設(shè)計(jì)系統(tǒng)中一個(gè)重要的幾何運(yùn)算，在CAD/CAM的很多領(lǐng)域中都有廣泛的應(yīng)用，如數(shù)控加工、汽車車身設(shè)計(jì)等。但與此同時(shí)，等距計(jì)算又是一個(gè)十分困難的幾何運(yùn)算，與基曲線相比，往往等距曲線的表達(dá)形式復(fù)雜，不利于實(shí)際應(yīng)用。因此，對(duì)于等距曲線的研究是計(jì)算機(jī)輔助幾何設(shè)計(jì)的一個(gè)重要課題。在工程實(shí)際應(yīng)用中，通常采用逼近方法，即用簡單且適用于CAD/CAM系統(tǒng)的曲線近似地表示等距曲線，如B樣條曲線、多項(xiàng)式曲線等。

等距曲線的逼近方法主要有以下4種類型：（1）基于控制頂點(diǎn)偏移的方法［1-3］，此類方法直接偏移基曲線的控制頂點(diǎn)，再用偏移得到的控制多邊形生成基曲線的等距逼近曲線。雖然其幾何直觀性較強(qiáng)，且不需要求解線性方程組，但曲線的表達(dá)式中需有控制頂點(diǎn)，故此類方法不能應(yīng)用于任意表達(dá)形式的平面曲線，且大部分此類方法易造成最終得到的曲線控制頂點(diǎn)過多。另一方面，往往誤差控制不夠精確。（2）插值擬合的方法［4-6］。此類方法雖然對(duì)曲線的表達(dá)形式無特殊要求，但由于其擬合過程往往需要求解大量的線性方程組，因此造成計(jì)算上耗時(shí)較多。（3）包絡(luò)方法［7］。此類方法得到的逼近曲線次數(shù)過高。（4）其他方法［8-10］。文獻(xiàn)［8-9］的方法最終得到的逼近曲線次數(shù)過高。文獻(xiàn)［10-11］中提出的方法不能直接應(yīng)用于NUBRS曲線。

從實(shí)際工程應(yīng)用的角度來看，在求解平面曲線的等距曲線時(shí)，應(yīng)綜合考慮以下6個(gè)方面的問題：（1）算法簡單；（2）精度高；（3）符合NURBS標(biāo)準(zhǔn)；（4）運(yùn)算速度快；（5）適用任意曲線；（6）生成的控制頂點(diǎn)個(gè)數(shù)較少。本文針以上問題，結(jié)合漸進(jìn)迭代逼近算法［11-12］（Progressive-iteration Approximation，PIA）提出一種新的平面等距曲線算法。

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

本文要解決的問題是：給定一條平面參數(shù)曲線C（t）=（x（t），y（t）），t∈［t0，tn］和等距距離d，要求尋找一條逼近曲線C（t）的等距線Cd（t）的B樣條曲線。其實(shí)，對(duì)于函數(shù)曲線y=y（x），本文的提出的算法也是適用的，即可，下文稱曲線C（t）為基曲線。

本文算法的基本設(shè)計(jì)思想是：先離散化基曲線，得到逼近等距曲線的折線，將曲線與曲線的逼近問題轉(zhuǎn)化為曲線與折線的逼近問題，然后利用PIA算法逼近經(jīng)離散化得到的折線。

本文算法的基本步驟是：利用基曲線C（t）上兩點(diǎn)的切矢轉(zhuǎn)角α的改變量來確定給定平面參數(shù)曲線的采樣點(diǎn)集｛oj，j=0，1，…，m｝，同時(shí)求得相應(yīng)等距線上的采樣點(diǎn)集，并控制采樣誤差，其中，ε是預(yù)設(shè)的全局誤差閾值。將采樣點(diǎn)集｛pj，j=0，1，…，m｝依次連接，得到一條逼近等距線Cd（t）的折線Ld，即將曲線與曲線的逼近問題轉(zhuǎn)化為折線與曲線的逼近問題。對(duì)得到的采樣點(diǎn)集｛pj，j=0，1，…，m｝參數(shù)化，接著構(gòu)造初始B樣條曲線：

其中，｛p（0）i=pji，i=0，1，…，l｝，l＜m，pji是從采樣點(diǎn)集｛pj；j=0，1，…，m｝中選取的主控制點(diǎn)，作為B樣條曲線的初始控制頂點(diǎn)，Bi，p（t）是一組由節(jié)點(diǎn)向量｛tj，j=0，1，…，l+p+1｝確定的p次規(guī)范B樣條基函數(shù)。然后采用PIA算法通過迭代直到逼近誤差時(shí)停止迭代。最終得到的B樣條曲線插值所選的主控制點(diǎn)pji，并逼近由采樣點(diǎn)集｛pj，j=0，1，…，m｝連成的折線Ld。當(dāng)逼近誤差或ea2，則需在不滿足誤差處插入節(jié)點(diǎn)向量，繼續(xù)迭代，直到滿足誤差為止。其中，ea=ea1+ea2，ea1為控制采樣點(diǎn)和逼近曲線的誤差，ea2為控制折線段與對(duì)應(yīng)逼近曲線段的誤差。除了個(gè)別拐點(diǎn)處，該算法最后能保證等距逼近曲線（t）與等距曲線Cd（t）的全局誤差控制在預(yù)設(shè)的誤差閾值ε內(nèi)。以上過程中的采樣過程、采樣點(diǎn)｛pj，j=0，1，…，m｝的參數(shù)化方法、主控制點(diǎn)p（0）i的選取方法、節(jié)點(diǎn)向量｛tj，j=0，1，…，l+p+1｝的構(gòu)造方式、PIA迭代過程、逼近誤差ea的控制方法將分別在下文2.1節(jié)～2.6節(jié)中具體給出。

2.1 采樣算法及采樣點(diǎn)序列的參數(shù)化

采樣的原則之一要保證2個(gè)采樣點(diǎn)之間的曲線段是凸曲線，故必須將曲線的拐點(diǎn)取作采樣點(diǎn)。基曲線的拐點(diǎn)與其等距曲線的拐點(diǎn)存在一一對(duì)應(yīng)的關(guān)系。曲線上其切矢轉(zhuǎn)角符號(hào)發(fā)生改變的位置即為拐點(diǎn)位置。規(guī)定切矢轉(zhuǎn)角逆時(shí)針為正，順時(shí)針為負(fù)，方向是沿著參數(shù)值增大的方向轉(zhuǎn)動(dòng)的。拐點(diǎn)如圖1所示，其中設(shè)點(diǎn)A為拐點(diǎn)。

圖1 拐點(diǎn)取法示意圖

利用正弦函數(shù)的奇偶性，曲線C（t）與C（t+Δt）之間的切矢轉(zhuǎn)角α的計(jì)算公式如下：

α=arcsin（sinα）

采樣的原則之二是保證相鄰兩采樣點(diǎn)之間的切矢轉(zhuǎn)角控制在預(yù)定的閾值范圍內(nèi)，且等距線上相應(yīng)的曲線段與其弦的距離在預(yù)定的誤差范圍內(nèi)。目的是使得等距曲線上的取樣點(diǎn)能充分反映基曲線C（t）形狀特征，且控制由等距曲線上采樣點(diǎn)確定的折線在誤差范圍內(nèi)全局逼近等距曲線，在此前提下盡可能地減少采樣點(diǎn)數(shù)量。下面給出采樣算法：

算法 SAMPLE

輸入 平面參數(shù)曲線C（t）=（x（t），y（t）），t∈［t0，tn］，預(yù)定的參數(shù)步長初值Δt，預(yù)定的角度閾值δ0，δ1，δ2（0＜δ0＜δ1＜δ2），預(yù)定的采樣誤差閾值ec

輸出 滿足采樣誤差的等距曲線Cd（t）采樣點(diǎn)序列集｛pj，j=0，1，…，m｝，取基曲線C（t）的首末點(diǎn)作為采樣點(diǎn)t←t0，tmp←Δt

運(yùn)用本文的采樣算法，可以保證基曲線的特征點(diǎn)被完整保留，且曲線在曲率變化大的地方所取的樣點(diǎn)較密，在曲線曲率變化小的地方所取的樣點(diǎn)較疏，這樣就能達(dá)到用盡可能少但又足以保留曲線原有特征的一系列采樣點(diǎn)。再將這些采樣點(diǎn)集｛pj；j= 0，1，…，m｝順次連接起來，得到逼近等距線的折線Ld，并且Ld與等距曲線的全局誤差嚴(yán)格控制在預(yù)定的誤差范圍內(nèi)。其中，采樣點(diǎn)的數(shù)量可以通過調(diào)整角度閾值δ1，δ2的取值來改變。

等距曲線Cd（t）上的采樣點(diǎn)序列｛pj，j=0，1，…，m｝的參數(shù)取為基曲線C（t）上對(duì)應(yīng)采樣點(diǎn)的參數(shù)。設(shè)其參數(shù)序列為｛tj，j=0，1，…，m｝且滿足tj＜tj+1。

2.2 初始控制頂點(diǎn)的選取

等距曲線Cd（t）上的采樣點(diǎn)序列｛pj，j=0，1，…，m｝實(shí)際上顯示了等距線的基本形狀，而曲線C（t）的特征點(diǎn)與其等距線Cd（t）的特征點(diǎn)是一一對(duì)應(yīng)的關(guān)系，如拐點(diǎn)。為了達(dá)到更好的逼近效果，這些特征點(diǎn)都應(yīng)選取為主控制點(diǎn)，其余的主控制點(diǎn)按如下方法進(jìn)行選取：

計(jì)算各個(gè)采樣點(diǎn)的離散曲率：

其中，Δpj和Δ2pj分別是采樣點(diǎn)pj的向前一階差分和二階差分，進(jìn)而生成了離散的采樣點(diǎn)的曲率序列：

選取K=｛kj，j=0，1，…，m｝中局部曲率極大值點(diǎn)，即滿足kj-1＜kj，kj+1＜kj以及采樣點(diǎn)的首、末點(diǎn)。再與特征點(diǎn)一起構(gòu)成采樣點(diǎn)序列｛pj，j=0，1，…，m｝的主控制點(diǎn)序列｛pj0，pj1，pj02，…，pjl｝，并將主控制點(diǎn)作為迭代的初始控制頂點(diǎn)，表示為：

2.3 節(jié)點(diǎn)向量的構(gòu)造

本文節(jié)點(diǎn)向量的構(gòu)造采用平均的方法。初始B樣條曲線的初始控制頂點(diǎn)序列｛p（0）i=pji，i= 0，1，…，l｝的參數(shù)序列如下：

則p次（p+1階）初始B樣條曲線的節(jié)點(diǎn)向量序列構(gòu)造如下：

2.4 漸進(jìn)迭代逼近插值采樣點(diǎn)

采用PIA算法插值這些主控制點(diǎn)｛pji，i=0，1，…，l｝，PIA算法是通過不斷調(diào)整控制頂點(diǎn)來最終插值所取的型值點(diǎn)集。將｛pji，i=0，1，…，l｝作為初始控制頂點(diǎn)，構(gòu)造初始B樣條曲線r（0）（t）=（t），其中Bi，p（t），i=1，2，…，l是一組由節(jié)點(diǎn)向量｛tj，j=0，1，…，l+p+1｝定義的p次規(guī)范B樣條基函數(shù)，其組成一個(gè)標(biāo)準(zhǔn)全正基［14］。PIA算法迭代過程如下：第i個(gè)控制頂點(diǎn)的第一次調(diào)整差向量取為，把作為新的控制頂點(diǎn)，得到第一次迭代后的B樣條曲線：

假設(shè)通過k次迭代后，產(chǎn)生曲線r（k）（t），則控制頂點(diǎn)的調(diào)整差向量為，控制頂點(diǎn)沿相應(yīng)的調(diào)整差向量的方向移動(dòng)，即，從而得到第k+1條曲線，即：

迭代過程如圖2所示。

圖2 迭代非均勻B樣條曲線（r（k）（t）→r（k+1）（t））

2.5 逼近誤差控制

由于本文的思想是將基曲線離散化，得到逼近等距線的折線，將曲線與曲線的逼近問題轉(zhuǎn)化為曲線與折線的逼近問題，為保證在全局上控制曲線的逼近誤差，需考慮2個(gè)方面的逼近誤差：

（1）等距線Cd（t）與離散化折線Ld的全局誤差，在2.1節(jié)給出的采樣算法SAMPLE中，只要取采樣誤差閾值ec=ε/2，就可將等距線Cd（t）與折線Ld的全局誤差控制在范圍內(nèi)。

（2）折線Ld與逼近的B樣條曲線的誤差，可分如下2個(gè)部分將該誤差控制在范圍內(nèi)：

1）點(diǎn)與點(diǎn)的逼近誤差控制：利用PIA算法得到逼近等距曲線的B樣條曲線r（k）（t），t∈［t0，tn］插值于所選取的主控制點(diǎn)｛pji，i=0，1，…，l｝（這里設(shè)迭代插值產(chǎn)生的誤差忽略不計(jì)），而在每兩個(gè)主控制點(diǎn)pji-1，pjl之間還存在一些采樣點(diǎn)ps=pji-1，ps+1，ps+2，…，pe= pji，利用參數(shù)的對(duì)應(yīng)關(guān)系，分別控制這些采樣點(diǎn)和逼近曲線上對(duì)應(yīng)點(diǎn)的距離，當(dāng)時(shí)，則說明該處已達(dá)到逼近的誤差精度，其中， k表示逼近曲線的迭代次數(shù)，ea1=ε/4，ε是預(yù)設(shè)的擬合誤差閾值。若，則說明該處未達(dá)到精度要求，需要在最大處插入節(jié)點(diǎn)，B樣條曲線節(jié)點(diǎn)插入可采用伯姆算法［15］，將該采樣點(diǎn)對(duì)應(yīng)的參數(shù)值作為新節(jié)點(diǎn)插入到節(jié)點(diǎn)向量中，則相應(yīng)的使B樣條曲線r（k）（t）增加一個(gè)控制頂點(diǎn)。當(dāng)然，對(duì)多個(gè)誤差較大的點(diǎn)，可以同時(shí)對(duì)其進(jìn)行插入節(jié)點(diǎn)，以提高算法效率。

2）B樣條曲線段與折線段的逼近誤差控制：計(jì)算采樣折線和逼近曲線的逼近程度來估計(jì)誤差。如圖3所示，pi和pi+1是等距線上的采樣點(diǎn)，對(duì)應(yīng)的參數(shù)值分別為ti和ti+1，Qi和Qi+1是逼近等距曲線r（k）（t）上的參數(shù)對(duì)應(yīng)點(diǎn)，r（k）′（ti）和r（k）′（ti+1）分別是Qi和Qi+1的切矢向量，設(shè)兩切矢向量交于點(diǎn)B，點(diǎn)B到線段QiQi+1的距離為h（k）i上面一步保證了點(diǎn)Qi和pi，Qi+1和pi+1的充分接近，就有線段QiQi+1和線段pipi+1充分接近，只要控制逼近曲線段r（k）（t），其中，t∈［ti，ti+1］充分接近線段QiQi+1即可，即保證。若不滿足該條件，則在最大誤差點(diǎn)處插入新的節(jié)點(diǎn)向量。直到滿足誤差精度。同樣，對(duì)多個(gè)誤差較大的處，可以同時(shí)對(duì)其進(jìn)行插入節(jié)點(diǎn)，以提高算法效率。需要指出用高h(yuǎn)控制誤差，對(duì)個(gè)別含有拐點(diǎn)的局部有可能不能完全控制。

圖3 誤差控制示意圖

2.6 算法過程

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

輸入 任意表達(dá)形式的平面參數(shù)曲線C（t），t∈［t0，tn］，等距距離d，精度ε，步長初值Δt，角度閾值δ0，δ1，δ2。

Step1 對(duì)平面參數(shù)曲線C（t）進(jìn)行采樣操作。得到基曲線上的采樣點(diǎn)集

Step2 由等距公式Cd（t）=C（t）+d·N（t）計(jì)算相應(yīng)等距曲線上的采樣點(diǎn)｛pj，j=0，1，…，m｝后，并將采樣點(diǎn)依次用線段連接起來，得到折線Ld。

Step3 選出等距曲線的特征點(diǎn)、首末點(diǎn)和局部曲率極大值點(diǎn)作為PIA算法的主控制點(diǎn)序列。

Step4 運(yùn)用PIA算法插值主控制點(diǎn)序列，得到逼近等距曲線的B樣條曲線。

Step5 計(jì)算各個(gè)等距線上的采樣點(diǎn)和逼近曲線上對(duì)應(yīng)點(diǎn)的距離，若不滿足精度要求，在處插入節(jié)點(diǎn)，轉(zhuǎn)Step4。

若Step5和Step6已達(dá)到，則終止。

注：本文算法的Step5和Step6可以同時(shí)插入多個(gè)節(jié)點(diǎn)。

3 實(shí)驗(yàn)與結(jié)果分析

應(yīng)用本文提出的針對(duì)任意平面曲線等距線逼近算法，本節(jié)給出3個(gè)實(shí)例，其分別從不同角度驗(yàn)證本算法的有效性。其中，例1從誤差控制角度說明本文算法能有效控制逼近等距線的誤差；例2從最終得到的逼近曲線的控制頂點(diǎn)數(shù)量上和其他方法比較。例3是將該算法應(yīng)用于一般的函數(shù)曲線。

例1 基曲線是一條五次Bezier曲線，其6個(gè)控制頂點(diǎn)為：

曲線的等距距離為d=1。先對(duì)基曲線進(jìn)行采樣，取參數(shù)步長初值為Δt=0.02，角度閾值δ0=，分別選取38個(gè)采樣點(diǎn)中的8個(gè)，16個(gè)，20個(gè)主控制頂點(diǎn)，再用PIA算法生成等距曲線實(shí)驗(yàn)結(jié)果如圖4所示。

圖4 五次Bezier曲線采樣圖及其等距線的生成

圖4（a）是運(yùn)用本文的采樣方法得到的38個(gè)采樣點(diǎn)。可以看出采樣結(jié)果在曲線走勢(shì)平緩處取點(diǎn)較少，反之取點(diǎn)較密，能充分反映基曲線的特征。圖4（b）中的逼近曲線達(dá)到預(yù)定誤差ε=10-2。圖4（c）中的逼近曲線達(dá)到預(yù)定誤差ε=10-3，圖4（d）中的逼近曲線達(dá)到預(yù)定誤差ε=10-4，可以看出隨著主控制頂點(diǎn)的增多，等距曲線的逼近程度越精確。

圖5 三次Bezier曲線采樣圖及其等距線的生成

圖5 （b）中的逼近曲線達(dá)到預(yù)給誤差ε=0.01，需要10個(gè)控制頂點(diǎn)。圖5（c）中的逼近曲線達(dá)到預(yù)給誤差ε=0.000 1，需要15個(gè)控制頂點(diǎn)，圖5（d）中的逼近曲線達(dá)到ε=0.000 01，需要21個(gè)控制頂點(diǎn)。以上都是在算法迭代20次情況下的結(jié)果。表1為在不同精度要求下應(yīng)用不同方法求本例三次Bezier曲線等距線所需的控制頂點(diǎn)數(shù)的比較。

表1 逼近三次Bezier曲線等距線所需的控制頂點(diǎn)數(shù)

可以看出，在同樣的精度下，應(yīng)用本文方法得到的控制頂點(diǎn)數(shù)較少。

例3 對(duì)于函數(shù)y=sin x+2cos x+x，x∈［-3.14，3.14］，可將其表示為參數(shù)曲線形式：

取曲線的等距距離d=1，采樣的參數(shù)步長初值，Δt=0.01，角度閾值δ0=0.01/π，δ1=1/π，δ2=1/π，運(yùn)用本文算法所得到的等距曲線的B樣條逼近曲線的結(jié)果如圖6所示。

圖6（b）中的逼近曲線達(dá)到預(yù)給誤差ε=0.01，圖6（c）中的逼近曲線達(dá)到預(yù)給誤差ε=0.001，圖6（d）中的逼近曲線達(dá)到預(yù)給誤差ε=0.000 1，可以看出，隨著主控制頂點(diǎn)的增多，等距曲線的逼近程度越精確，誤差也越來越小。

圖6 一般函數(shù)曲線采樣圖及其等距線的生成

4 結(jié)束語

本文算法在對(duì)等距曲線進(jìn)行采樣的過程為自適應(yīng)的，可保證在曲線曲率變化大的地方取較多的采樣點(diǎn)，在曲線曲率變化小的地方取較少的采樣點(diǎn)，這樣既保持了曲線的幾何性質(zhì)，又減少了采樣點(diǎn)的數(shù)目，使算法更加快速。再應(yīng)用漸進(jìn)迭代方法插值所取的等距線上的主控制點(diǎn)，較之前應(yīng)用最小二乘方法來逼近等距曲線，使算法效率得到提高。同時(shí)，由于漸進(jìn)迭代算法具有局部性，因此在誤差大的地方可以局部地進(jìn)行迭代。本文算法可應(yīng)用于任意的平面參數(shù)曲線及函數(shù)曲線，能對(duì)逼近曲線進(jìn)行全局誤差控制，且得到的B樣條逼近曲線的控制頂點(diǎn)數(shù)較少。下一步將在以下3個(gè)方面對(duì)本文算法進(jìn)行改進(jìn)：（1）在迭代過程中，考慮曲線的幾何特性以更好地控制等距逼近曲線的形狀。（2）進(jìn)一步控制等距逼近曲線的誤差。（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］ 劉利剛，王國瑾.基于控制頂點(diǎn)偏移的等距曲線最優(yōu)逼近［J］.軟件學(xué)報(bào)，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］ 施法中.計(jì)算機(jī)輔助幾何設(shè)計(jì)與非均勻有理B樣條［M］.1版.北京：北京航空航天大學(xué)社，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］ 嚴(yán)蘭蘭，宋來忠.正則Bezier曲線的等距線及其計(jì)算機(jī)實(shí)現(xiàn)［J］.計(jì)算機(jī)與數(shù)字工程，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，F(xiàn)ujian Normal University，F(xiàn)uzhou 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ìn)迭代逼近的平面曲線等距線算法［J］.計(jì)算機(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

福建省自然科學(xué)基金資助項(xiàng)目（2010J01318）。

陳 青（1989-），女，碩士研究生，主研方向：圖像處理，計(jì)算幾何；潘日晶，教授。

2014-10-09

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