G2連續(xù)的圓弧樣條曲線插值

齊 倩，方美娥

(杭州電子科技大學(xué)計(jì)算機(jī)學(xué)院，浙江杭州310018)

0 引言

用圓弧作為樣條來進(jìn)行造型而得到的樣條曲線稱為圓弧樣條曲線，簡(jiǎn)稱圓弧樣條。人們?cè)趯?duì)圓弧樣條的研究中取得了很多成果，不僅介紹了圓弧樣條，還用分析方法討論了圓弧樣條插值方法［1，2］，并提出了圓弧樣條插值問題［3］和雙圓弧樣條［4］。在圓弧樣條的插值問題中，以前大多采用的是逼近算法，后來在不斷的研究中，又取得了很多新的研究成果，找到了一條由直線和圓弧構(gòu)成的G0圓弧樣條曲線［5］和用最小二乘法來構(gòu)造由圓弧和直線段構(gòu)成的G0或G1曲線的方法［6］，通過解一個(gè)非線性方程組來求得擬合給定型值點(diǎn)的圓弧樣條［7］和采用一些簡(jiǎn)單的公式和比較簡(jiǎn)單的方法來求得G1圓弧樣條曲線［8］，還有的給出了一種用二次曲線段來插值平面有序數(shù)據(jù)點(diǎn)列［9］和所構(gòu)造的三圓弧樣條曲線可以在插值點(diǎn)處按切向和曲率插值的方法［10］。文獻(xiàn)11提出替換平面圓弧樣條曲線的一部分，以增加平面圓弧樣條曲線的光滑度，進(jìn)而產(chǎn)生G2連續(xù)的曲線。本文在已有研究工作的基礎(chǔ)上，提出了一種G2連續(xù)且保凸的圓弧樣條的算法。突破了圓弧段首末端點(diǎn)固定為插值點(diǎn)的限制條件，插值出了整體G2連續(xù)的圓弧樣條曲線，而且構(gòu)造出的差值曲線是唯一可實(shí)現(xiàn)整體細(xì)分生成的圓弧樣條曲線。

1 G2圓弧樣條插值曲線的構(gòu)造

在平面上給定由n個(gè)點(diǎn)P1，P2，…，Pn所組成的點(diǎn)列，及其每一端點(diǎn)處的切向 T1，T2，…，Tn，求一條由若干段圓弧構(gòu)成的G2連續(xù)的曲線，使它依次插值于點(diǎn)列，且在每一端點(diǎn)處的切向?yàn)門1，T2，…，Tn，要得到滿足條件的圓弧樣條曲線。

1.1 初始圓的構(gòu)造

為每個(gè)型值點(diǎn)構(gòu)造唯一的初始圓需首先確定初始圓的半徑及圓心位置，為實(shí)現(xiàn)插值曲線G2連續(xù)，本文構(gòu)造相同半徑的初始圓。半徑的選取可作為自由參數(shù)由用戶確定，但必須保證后續(xù)公切圓的存在。令過兩個(gè)相鄰的型值點(diǎn)P1、P2作半徑為r的圓C1、C2，使得兩圓的半徑同樣為R的公切圓圓心與O1、O23點(diǎn)共線，根據(jù)三角形的性質(zhì)得:

如圖1所示，每相鄰兩型值點(diǎn)對(duì)應(yīng)的R可以從式1中求出，令所有R中的最小值為Rmin，則只需選擇初始圓半徑r＞Rmin即可保證G2連續(xù)圓弧樣條存在，且一般選取半徑不超過dmax為相鄰插值點(diǎn)距離最大值)較為合適，盡量避免相鄰圓的包含。

圖1 初始圓半徑確定方法圖

對(duì)于一個(gè)型值點(diǎn)，已知切向和初始圓的半徑，可以作2個(gè)圓，在這里選取外側(cè)的圓作為初始圓。具體方法如下:構(gòu)造一個(gè)坐標(biāo)系，坐標(biāo)原點(diǎn)平移到插值點(diǎn)，坐標(biāo)軸旋轉(zhuǎn)到以切矢為x軸正向的位置，此時(shí)圓心落在縱坐標(biāo)大于O的區(qū)域內(nèi)的插值圓符合要求，即處于曲線外側(cè)。

1.2 公切圓的作法

實(shí)際上，按上述方法確定的公切圓有2個(gè)，按照選取初始圓的類似方法確定坐標(biāo)系后選取圓心縱坐標(biāo)小于O的公切圓，這樣選取的公切圓處于最終得到的插值曲線的內(nèi)側(cè)，可更好地保證插值曲線簡(jiǎn)單光順。

圖2 公切圓圓心選取方法圖示

1.3 圓弧段的選定

初始圓與公切圓確定之后，從第一個(gè)型值點(diǎn)出發(fā)沿切向在初始圓和公切圓上選取合適的圓弧段，形成一條連續(xù)的圓弧樣條曲線。圓弧段的選擇標(biāo)準(zhǔn)滿足兩條原則，一是讓選取的圓弧段依次經(jīng)過各個(gè)型值點(diǎn)，二是盡量選取較短的圓弧段。一般情況都能選取較短的圓弧段，插值點(diǎn)越均勻，效果越好，極不均勻時(shí)有可能取整圓并重復(fù)一段圓弧，但G2的路徑總是存在的。

從以上算法可知，本文方法構(gòu)造出的插值曲線上所有點(diǎn)的曲率均為1/r，因此整條圓弧樣條插值曲線自然滿足G2連續(xù)。如圖3所示，粗線為最終的圓弧樣條曲線，其中圖3中4個(gè)插值點(diǎn)取自同一半徑為r的圓上，可以看到利用本文的方法選取初始圓半徑為r時(shí)，所有公切圓均為型值點(diǎn)所在的圓，此時(shí)插值曲線具有保圓性。

圖3 本文方法舉例

2 G2圓弧樣條曲線細(xì)分

由文獻(xiàn)12中第5節(jié)中圓弧段細(xì)分公式可知，細(xì)分參數(shù)僅與圓弧段的半徑及弧度相關(guān)，本文生成的圓弧樣條插值曲線是由半徑相同的圓弧段連接而成，如果進(jìn)一步將這些圓弧段重新均分為同弧度的圓弧段，則可由文獻(xiàn)12中的細(xì)分方法整體細(xì)分生成，本文方法得到的圓弧樣條插值曲線如圖4(a)所示，凹圓弧是初始圓上選取的圓弧段，凸圓弧是公切圓上選取的圓弧段，半徑相同，弧度分別為 和，為了統(tǒng)一弧度，將這兩類圓弧段分別劃分為弧度為3段及2段圓弧，這樣劃分后的每一段新圓弧段細(xì)分生成的控制多邊形為兩條邊的折線，兩條邊分別以圓弧段的首末端點(diǎn)為中點(diǎn)且與之相切，這樣整條圓弧樣條曲線的細(xì)分控制多邊形由這些折線連接而成，如圖4(b)所示，圓點(diǎn)為相應(yīng)控制頂點(diǎn)，由此確定了控制多邊形、半徑及弧度的圓弧樣條可由文獻(xiàn)12中的方法整體細(xì)分生成，細(xì)分曲線如圖4(b)所示，與原來的圓弧樣條插值曲線重合。這是本文方法與已有圓弧樣條插值方法相比，除具有更高幾何連續(xù)階之外的又一突出優(yōu)勢(shì)，首次實(shí)現(xiàn)了圓弧樣條曲線的整體細(xì)分生成，可為數(shù)控加工中刀軌路徑設(shè)計(jì)等應(yīng)用帶來很大的方便。

圖4 細(xì)分實(shí)例

3 結(jié)束語

根據(jù)以前的研究，構(gòu)造既插值型值點(diǎn)又插值切向的圓弧樣條曲線只能達(dá)到切向連續(xù)，本文提出了一種新的簡(jiǎn)單的圓弧樣條構(gòu)造方法，使得到的圓弧樣條曲線滿足曲率連續(xù)。該方法具有如下特點(diǎn):圓弧段之間的連接點(diǎn)不一定是在給定的插值型值點(diǎn)上，因此，有更多的自由度來控制曲線形狀;圓弧樣條曲線的圓弧段數(shù)不大于型值點(diǎn)數(shù);生成的圓弧樣條曲線具有保凸性;且此種算法不僅適用于開圓弧樣條，對(duì)閉圓弧樣條也同樣適用;最終的插值圓弧樣條可以整體細(xì)分生成。但該方法也有拐點(diǎn)較多的不足，實(shí)際中可以少取一些型值點(diǎn)，或盡量取型值點(diǎn)為所構(gòu)造的圓弧段的中點(diǎn)來加以改善。

［1］孫家昶.局部坐標(biāo)下的樣條函數(shù)與圓弧樣條曲線［J］.數(shù)學(xué)學(xué)報(bào)，1977，20(4):28－40.

［2］孫家昶.樣條函數(shù)與計(jì)算幾何［M］.北京:科學(xué)出版社，1982:271－291.

［3］蘇步青，劉鼎元.計(jì)算幾何［M］.上海:上?？茖W(xué)技術(shù)出版社，1981:176－213.

［4］董光昌，梁友棟，何援軍.樣條曲線擬合和雙圓弧逼近［J］.應(yīng)用數(shù)學(xué)學(xué)報(bào)，1978，1(4):330－340.

［5］Piegl L.Curve fitting algorithm for rough cutting［J］.Computer Aided Design1986，18(2):79 －82.

［6］Albano A.Representation of digitized contours in terms of conic arcs and straight-line segments［J］.Computer Graphics＆Image Processing，1974，3(1):23 －33.

［7］Hoschek J.Circular splines［J］.Computer Aided Design，1992，24(11):611 －618.

［8］Meek D S，Walton D J.Approximation of quadratic Bezier curves by arc splines［J］.Journal of Computational and Applied Mathematics，1994，54(4):107 －120.

［9］張三元.一種G2連續(xù)的二次曲線樣條插值方法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)報(bào)，2000，12(6):419－422.

［10］林杰，潘日晶.數(shù)據(jù)點(diǎn)列的三圓弧樣條插值［J］.福建師范大學(xué)學(xué)報(bào)，2007，23(2):20－24.

［11］Li Z，Meek D S，Smoothing an arc spline［J］.Computer＆ Graphics，2005，29(4):576 －587.

［12］Fang M，Ma W，Wang G.A generalized curve subdivision scheme of arbitrary order with a tension parameter［J］.Computer Aided Geometric Design，2010，27(9):720 －733.