一類(lèi)參數(shù)曲線(xiàn)的積累平均弧長(zhǎng)參數(shù)化方法*

賀詩(shī)濤,申立勇

(中國(guó)科學(xué)院大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,北京 100049)

*“第23屆計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)術(shù)會(huì)議(CAD&CG 2020)”推薦論文.

計(jì)算機(jī)輔助幾何設(shè)計(jì)(簡(jiǎn)稱(chēng)CAGD)[1]利用計(jì)算機(jī)強(qiáng)大的計(jì)算能力解決幾何設(shè)計(jì)問(wèn)題,研究自由型曲線(xiàn)曲面. 而找到既適合計(jì)算機(jī)處理,又能有效滿(mǎn)足形狀表示與幾何設(shè)計(jì)要求,且便于形狀信息傳遞和產(chǎn)品數(shù)據(jù)交換形狀描述的數(shù)學(xué)方法,是CAGD的核心問(wèn)題. 為清楚表達(dá)自由型曲線(xiàn)曲面,Ferguson[2]率先將參數(shù)多項(xiàng)式引入了CAGD. Schoenberg[3]提出了樣條函數(shù)[4-5]用以解決連接問(wèn)題,但曲線(xiàn)曲面形狀控制的難題仍待解決. Bézier方法[6]更強(qiáng)調(diào)幾何直觀,并在解決整體形狀控制方面有重大突破,但仍存在連接問(wèn)題和局部修改問(wèn)題. B樣條方法[7-15]在保留Bézier方法優(yōu)點(diǎn)的基礎(chǔ)上成功解決了局部控制問(wèn)題和參數(shù)連續(xù)性的連接問(wèn)題,但在處理圓錐曲線(xiàn)和初等解析曲面時(shí)只能給出通常不合要求的近似表示. 為解決該問(wèn)題,Forrest[16]先給出了有理Bézier形式的圓錐曲線(xiàn),之后Versprille[17]提出了有理B樣條方法. 非均勻有理B樣條(簡(jiǎn)稱(chēng)NURBS)方法將有理與非有理Bézier曲線(xiàn)曲面、有理與非有理B樣條相統(tǒng)一,不僅保留了非有理B樣條的優(yōu)點(diǎn),還具有精確表達(dá)二次曲線(xiàn)曲面的功能. Sederberg等[18-19]提出了T樣條方法,對(duì)B樣條曲面進(jìn)行了改進(jìn).

參數(shù)化在CAGD中具有重要作用. 設(shè)計(jì)者希望使用的參數(shù)化方法能盡量反應(yīng)被插曲線(xiàn)或用數(shù)據(jù)點(diǎn)所構(gòu)造曲線(xiàn)的性質(zhì). 此外,當(dāng)給定控制頂點(diǎn)生成一條k次非均勻B樣條曲線(xiàn)時(shí),由于通常節(jié)點(diǎn)矢量未知,因此還需確定節(jié)點(diǎn)矢量中具體的節(jié)點(diǎn)值,同樣要求參數(shù)化方法. 目前常用的參數(shù)化方法有均勻參數(shù)化、弦長(zhǎng)參數(shù)化、向心參數(shù)化[20]和福利參數(shù)化. 本文提出積累平均弧長(zhǎng)參數(shù)化法的一般框架,基于局部參數(shù)二次多項(xiàng)式插值和光順性的約束準(zhǔn)則,給出3種具體的積累平均弧長(zhǎng)參數(shù)化法,并通過(guò)實(shí)例說(shuō)明在給定約束準(zhǔn)則進(jìn)行局部插值后,其所賦予局部插值曲線(xiàn)的性質(zhì)可從局部傳遞到整體,使得全局插值曲線(xiàn)在同一約束準(zhǔn)則下的目標(biāo)函數(shù)值小于弦長(zhǎng)參數(shù)化和向心參數(shù)化的目標(biāo)函數(shù)值.

1 理論框架

積累平均弧長(zhǎng)參數(shù)化法可視為對(duì)弦長(zhǎng)參數(shù)化的一個(gè)改進(jìn),將以直代曲的方法改進(jìn)為以曲代曲,從而增加了一定的自由度,需要約束條件確定局部參數(shù)值. 約束條件不同使得積累平均弧長(zhǎng)參數(shù)化法也不同. 這一特點(diǎn)使積累平均弧長(zhǎng)參數(shù)化法靈活性較強(qiáng),可根據(jù)實(shí)際需求自主選擇相鄰兩點(diǎn)間曲線(xiàn)弧的構(gòu)造方法,而目前已有的4種參數(shù)化方法都沒(méi)有該特性. 一般地,對(duì)于平面上n個(gè)互異數(shù)據(jù)點(diǎn)Pi(xi,yi)(i=0,1,2,…,n),積累平均弧長(zhǎng)參數(shù)化方法步驟如下:

1) 確定局部參數(shù)多項(xiàng)式插值曲線(xiàn)的次數(shù)m;

2) 選取合適的約束條件,以l個(gè)點(diǎn)為一組計(jì)算出數(shù)據(jù)點(diǎn)的局部參數(shù)和局部插值曲線(xiàn)在相鄰兩點(diǎn)間的弧長(zhǎng),即按P0,P1,…,Pl-1;P1,P2,…,Pl; …;Pn-l+1,Pn-l+2,…,Pn的順序討論,l由m和約束條件確定;

3) 根據(jù)局部插值曲線(xiàn)在相鄰兩點(diǎn)間弧長(zhǎng)的平均值計(jì)算全局參數(shù).

由上述步驟可知,當(dāng)插值點(diǎn)較多時(shí),該理論框架對(duì)應(yīng)的問(wèn)題是一個(gè)多參數(shù)非線(xiàn)性?xún)?yōu)化問(wèn)題,一般方法求解該類(lèi)問(wèn)題的效率較低. 因此本文應(yīng)用局部傳遞到整體的思路,給出一種基于局部求解,然后逐步積累弧長(zhǎng)均值的方法. 先不斷利用局部插值求出局部最優(yōu)解,得到局部參數(shù),然后將相鄰兩點(diǎn)間全部弧長(zhǎng)的均值進(jìn)行累積以求得全局參數(shù),將此作為全局最優(yōu)解的一個(gè)近似. 由實(shí)例計(jì)算可見(jiàn),該近似解能使得全局插值曲線(xiàn)由約束條件決定的目標(biāo)函數(shù)值小于傳統(tǒng)參數(shù)化方法,如弦長(zhǎng)參數(shù)化和向心參數(shù)化所對(duì)應(yīng)的目標(biāo)函數(shù)值,表明本文算法有效. 由于參數(shù)二次多項(xiàng)式曲線(xiàn)非常簡(jiǎn)單,因此本文給出的3種具體的積累平均弧長(zhǎng)參數(shù)化法都基于局部參數(shù)二次多項(xiàng)式插值,區(qū)別在于約束條件的選取.

1.1 三點(diǎn)二次插值長(zhǎng)度最短約束

設(shè)平面上有3個(gè)互異數(shù)據(jù)點(diǎn)Pi(xi,yi)(i=0,1,2),過(guò)上述3點(diǎn)構(gòu)造參數(shù)二次多項(xiàng)式插值曲線(xiàn)P,設(shè)其局部參數(shù)分別為0,u1,1,其中0

(1)

將式(1)寫(xiě)成分量形式為

(2)

(3)

記

則可將式(2)和式(3)簡(jiǎn)化為

x=Au2+Bu+x0,

(4)

y=Cu2+Du+y0.

(5)

由于u1是變量,當(dāng)其取值在0～1區(qū)間變化時(shí),二次參數(shù)多項(xiàng)式插值曲線(xiàn)P也會(huì)發(fā)生變化,因此為確定取值,需要一個(gè)約束. 在實(shí)際應(yīng)用中,通常會(huì)遇到符合要求的曲線(xiàn)不唯一的情形. 為找到一條最符合要求的曲線(xiàn),需給出一些約束準(zhǔn)則. 考慮到波動(dòng)劇烈的曲線(xiàn)通常相對(duì)較長(zhǎng),因此為選擇波動(dòng)小、更平直的曲線(xiàn),可從曲線(xiàn)長(zhǎng)度最短出發(fā)構(gòu)造約束準(zhǔn)則. 基于此,可令u1的取值使參數(shù)二次多項(xiàng)式插值曲線(xiàn)的目標(biāo)函數(shù)值最小,目標(biāo)函數(shù)為

為討論方便,記被積函數(shù)為

(6)

Q1=(2Au+B)2+(2Cu+D)2.

易見(jiàn)E1是以u(píng)1為自變量的一元函數(shù). 求使E1達(dá)到最小的u1值,即為求E1的最小值點(diǎn). 根據(jù)給定的約束準(zhǔn)則,對(duì)Pi,Pi+1,Pi+2三點(diǎn)作局部參數(shù)二次插值并求出目標(biāo)函數(shù)E后,可用如下算法計(jì)算:

步驟1) 在(0,1)上使用遺傳算法(GA),求出最小值Emin;

步驟4) 若Eval1=Emin,Eval2>Emin,則ui+1=ua,并輸出ui+1; 若Eval1>Emin,Eval2=Emin,則ui+1=ub,并輸出ui+1; 若Eval1=Emin,Eval2=Emin,則:

最小值點(diǎn)的存在性可由物理背景說(shuō)明,當(dāng)最小值點(diǎn)不唯一時(shí),可選取離估計(jì)值最近的一定精度的最小值點(diǎn). 從而求得給定精度的最小值點(diǎn),即u1的局部參數(shù). 根據(jù)局部參數(shù)利用積累平均弧長(zhǎng)參數(shù)化法求出其全局參數(shù). 設(shè)Pi的全局參數(shù)為ti(i=0,1,2),則

t0=0,t1=t0+l1,t2=t1+l2,

其中l(wèi)1,l2分別表示參數(shù)二次多項(xiàng)式插值曲線(xiàn)P在點(diǎn)P0與P1、P1與P2間的弧長(zhǎng),即

下面考慮平面上有4個(gè)數(shù)據(jù)點(diǎn)的情形. 設(shè)平面上有4個(gè)互異數(shù)據(jù)點(diǎn)Pi(xi,yi)(i=0,1,2,3),過(guò)點(diǎn)P0,P1,P2做參數(shù)二次多項(xiàng)式插值曲線(xiàn)Pa,記為Pa(xa,ya). 設(shè)P0,P1,P2的局部參數(shù)分別為0,u1,1,其中0

(7)

仿照三點(diǎn)情形求u1的值. 根據(jù)弧長(zhǎng)公式分別計(jì)算Pa夾在P0和P1間的弧長(zhǎng)l1及P1和P2間的弧長(zhǎng)l21.

對(duì)于后三點(diǎn),仿照前面的討論重復(fù)操作. 過(guò)點(diǎn)P1,P2,P3做參數(shù)二次多項(xiàng)式插值曲線(xiàn)Pb,記為Pb(xb,yb). 設(shè)P1,P2,P3的局部參數(shù)分別為0,u2,1,其中0

(8)

易求出u2的值,從而Pb唯一確定. 根據(jù)弧長(zhǎng)公式分別計(jì)算Pb夾在P1和P2間的弧長(zhǎng)l22及P2和P3間的弧長(zhǎng)l3.

下面根據(jù)數(shù)據(jù)點(diǎn)的局部參數(shù)求全局參數(shù). 注意與三點(diǎn)情形相比的不同: 在數(shù)據(jù)點(diǎn)P1和P2間有兩段參數(shù)二次曲線(xiàn)弧,它們通常并不重合,也不會(huì)有相等的弧長(zhǎng). 一種方法是舍去其中一段弧,只保留另一段弧,然后完全按照三點(diǎn)的情形計(jì)算全局參數(shù),但這兩段弧是用不全相同的3個(gè)數(shù)據(jù)點(diǎn)生成的,它們包含的數(shù)據(jù)點(diǎn)信息不全相同,如果舍去其中一段弧的弧長(zhǎng),則會(huì)浪費(fèi)一個(gè)數(shù)據(jù)點(diǎn)的信息. 另一種方法是在局部插值過(guò)程中,避免相鄰兩點(diǎn)間出現(xiàn)兩段弧,如假設(shè)平面上有5個(gè)數(shù)據(jù)點(diǎn),令Pa插值于數(shù)據(jù)點(diǎn)P0,P1,P2,而Pb插值于數(shù)據(jù)點(diǎn)P2,P3,P4,這樣相鄰兩點(diǎn)間總只有一段參數(shù)二次曲線(xiàn)弧,但這種方法對(duì)數(shù)據(jù)點(diǎn)的數(shù)量有一定要求,只有在數(shù)據(jù)點(diǎn)個(gè)數(shù)可表達(dá)成2n+3的形式時(shí)才能使用,使得該方法有較大的局限性. 因此,需找到一種更合適的方法能同時(shí)使用l21和l22,從而不會(huì)發(fā)生信息丟失的問(wèn)題,也不會(huì)因?yàn)閿?shù)據(jù)點(diǎn)的個(gè)數(shù)問(wèn)題產(chǎn)生局限性. 最簡(jiǎn)單的方法是用l21和l22的算術(shù)平均值代替其中某一段弧的長(zhǎng)度,從而可得計(jì)算數(shù)據(jù)點(diǎn)全局參數(shù)的公式為

(9)

最后考慮平面上(n+1)個(gè)數(shù)據(jù)點(diǎn)的情形,其中n>3,這種情形的做法和四點(diǎn)情形完全相同. 設(shè)平面上有(n+1)個(gè)互異數(shù)據(jù)點(diǎn)Pi(xi,yi)(i=0,1,2,…,n). 首先仿照上述方法,利用長(zhǎng)度最短的約束準(zhǔn)則計(jì)算插值于P0,P1,P2的參數(shù)二次多項(xiàng)式曲線(xiàn),并分別計(jì)算夾在P0和P1間的弧長(zhǎng)l1及P1和P2間的弧長(zhǎng)l21；然后對(duì)下面的3個(gè)相鄰數(shù)據(jù)點(diǎn)進(jìn)行相同操作,分別計(jì)算夾在P1和P2間的弧長(zhǎng)l22及P2和P3間的弧長(zhǎng)l3. 以此類(lèi)推,以相鄰3個(gè)數(shù)據(jù)點(diǎn)為一組,利用長(zhǎng)度最短的約束準(zhǔn)則計(jì)算插值于Pi,Pi+1,Pi+2的參數(shù)二次多項(xiàng)式曲線(xiàn),并分別計(jì)算夾在Pi和Pi+1間的弧長(zhǎng)li+1,2及Pi+1和Pi+2間的弧長(zhǎng)li+2,1,其中i=2,3,…,n-1. 最后利用積累平均弧長(zhǎng)的方法計(jì)算數(shù)據(jù)點(diǎn)的全局參數(shù),公式為

(10)

1.2 三點(diǎn)二次插值能量最小約束

下面給出以能量最小作為約束準(zhǔn)則的方法,其來(lái)源于樣條的應(yīng)變能. 在僅改變約束準(zhǔn)則的條件下,積累平均弧長(zhǎng)參數(shù)化法的步驟幾乎與三點(diǎn)二次插值長(zhǎng)度最短約束方法完全一致,因此這里只考慮四點(diǎn)情形. 設(shè)平面上有4個(gè)互異的數(shù)據(jù)點(diǎn)Pi(xi,yi)(i=0,1,2,3),過(guò)點(diǎn)P0,P1,P2做參數(shù)二次多項(xiàng)式插值曲線(xiàn)Pa,記為Pa(xa,ya). 設(shè)P0,P1,P2的局部參數(shù)分別為0,u1,1,其中0

使用能量最小約束準(zhǔn)則,令u1的取值使得插值于P0,P1,P2的參數(shù)二次多項(xiàng)式插值曲線(xiàn)能量最小,從而求得唯一的插值曲線(xiàn)Pa,目標(biāo)函數(shù)為

其中ka是插值曲線(xiàn)Pa的曲率,ds是弧微分. 將目標(biāo)函數(shù)寫(xiě)為

根據(jù)曲率公式和弧微分公式,可計(jì)算得到Q1的表達(dá)式為

采用數(shù)值積分方法計(jì)算E1,然后根據(jù)三點(diǎn)二次插值長(zhǎng)度最短約束算法計(jì)算u1的值. 從而分別計(jì)算出Pa夾在P0和P1間的弧長(zhǎng)l1及P1和P2間的弧長(zhǎng)l21. 對(duì)于P1,P2,P3,可類(lèi)似求出滿(mǎn)足約束準(zhǔn)則的u2值,然后根據(jù)弧長(zhǎng)公式分別計(jì)算出Pb夾在P1和P2間的弧長(zhǎng)l22及P2和P3間的弧長(zhǎng)l3. 于是可得計(jì)算數(shù)據(jù)點(diǎn)全局參數(shù)的公式為式(9).

1.3 四點(diǎn)雙二次插值長(zhǎng)度最短約束

首先考慮四點(diǎn)的情形. 設(shè)平面上有4個(gè)互異數(shù)據(jù)點(diǎn)Pi(xi,yi)(i=0,1,2,3),過(guò)點(diǎn)P0,P1,P2做參數(shù)二次多項(xiàng)式插值曲線(xiàn)Pa. 設(shè)P0,P1,P2的局部參數(shù)分別為0,u1,1,且滿(mǎn)足0

過(guò)點(diǎn)P0,P1,P2做參數(shù)二次多項(xiàng)式插值曲線(xiàn)Pb. 設(shè)P1,P2,P3的局部參數(shù)分別為0,u2,1,且滿(mǎn)足0

(11)

由于式(11)等號(hào)右邊的兩個(gè)積分都是非負(fù)的,因此可知E取最小值時(shí),這兩個(gè)積分分別取最小值. 利用三點(diǎn)二次插值長(zhǎng)度最短約束算法分別求出u1和u2的值,即可根據(jù)積累平均弧長(zhǎng)計(jì)算全局參數(shù).

當(dāng)數(shù)據(jù)點(diǎn)增多時(shí),可以相鄰四點(diǎn)為一組進(jìn)行類(lèi)似討論. 例如,當(dāng)數(shù)據(jù)點(diǎn)數(shù)為5時(shí),可仿照上述方法得到全局參數(shù)的計(jì)算公式為

(12)

針對(duì)6個(gè)及以上互異點(diǎn)的全局參數(shù)計(jì)算公式為

(13)

與三點(diǎn)二次插值方法相比,四點(diǎn)雙二次插值改變了相鄰兩點(diǎn)間局部插值曲線(xiàn)段的數(shù)量,從而在表達(dá)式上呈現(xiàn)出加權(quán)平均的形式,即得到了與三點(diǎn)二次插值方法不同的全局參數(shù).

(A) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,三點(diǎn)二次插值長(zhǎng)度最短約束; (B) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,三點(diǎn)二次插值能量最小約束;(C) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,四點(diǎn)雙二次插值長(zhǎng)度最短約束.圖1 例1中點(diǎn)在不同參數(shù)化和約束條件下的多項(xiàng)式插值曲線(xiàn)Fig.1 Polynomial interpolation curves of points in example 1 under different parameterizations and constraints

2 實(shí)例計(jì)算

下面通過(guò)實(shí)例計(jì)算將上述3種具體的積累平均弧長(zhǎng)參數(shù)化法與弦長(zhǎng)參數(shù)化法、向心參數(shù)化法進(jìn)行比較,以說(shuō)明新參數(shù)化方法的優(yōu)勢(shì).

例1設(shè)平面上有4個(gè)數(shù)據(jù)點(diǎn):P0(1,6),P1(2,4),P2(2.5,3.5),P3(5,8). 做插值于這4個(gè)點(diǎn)的參數(shù)多項(xiàng)式曲線(xiàn),結(jié)果如圖1所示. 由圖1可見(jiàn),長(zhǎng)度最短約束的積累平均弧長(zhǎng)參數(shù)化曲線(xiàn)與弦長(zhǎng)參數(shù)化曲線(xiàn)相近. 長(zhǎng)度最短約束的目標(biāo)函數(shù)并非弧長(zhǎng)公式,從而導(dǎo)致雖然向心參數(shù)化的曲線(xiàn)弧長(zhǎng)最短,但在此約束準(zhǔn)則下目標(biāo)函數(shù)值最大.

在給定約束準(zhǔn)則進(jìn)行局部插值后,其賦予局部插值曲線(xiàn)的性質(zhì)可從局部傳遞到整體,使得全局插值曲線(xiàn)在同一約束準(zhǔn)則下的目標(biāo)函數(shù)值小于弦長(zhǎng)參數(shù)化和向心參數(shù)化的目標(biāo)函數(shù)值,對(duì)比結(jié)果如下：對(duì)例1中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及三點(diǎn)二次插值長(zhǎng)度最短約束下的積累平均弧長(zhǎng)參數(shù)化法所得長(zhǎng)度最短約束目標(biāo)函數(shù)值分別為14.352，20.144，13.997；對(duì)例1中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及三點(diǎn)二次插值能量最小約束下的積累平均弧長(zhǎng)參數(shù)化法所得能量最小約束目標(biāo)函數(shù)值分別為1.738，3.922，1.616；對(duì)例1中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及四點(diǎn)雙二次插值長(zhǎng)度最短約束下的積累平均弧長(zhǎng)參數(shù)化法所得長(zhǎng)度最短約束目標(biāo)函數(shù)值分別為14.352，20.144，13.997. 由上述對(duì)比結(jié)果可見(jiàn),約束準(zhǔn)則所賦予的局部性質(zhì)確實(shí)從局部傳遞到了全局插值曲線(xiàn),在該約束準(zhǔn)則下計(jì)算出的全局插值曲線(xiàn)的目標(biāo)函數(shù)值與弦長(zhǎng)參數(shù)化和向心參數(shù)化相比有明顯降低.

例2根據(jù)如下有序數(shù)據(jù)點(diǎn)集做參數(shù)三次樣條插值曲線(xiàn): {(1,8),(2,6),(3,4),(5,6),(6,7),(8,4)},結(jié)果如圖2所示，圖2中“°”表示數(shù)據(jù)點(diǎn).

(A) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,三點(diǎn)二次插值長(zhǎng)度最短約束; (B) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,三點(diǎn)二次插值能量最小約束;(C) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,四點(diǎn)雙二次插值長(zhǎng)度最短約束.圖2 例2中點(diǎn)在不同參數(shù)化和約束條件下的多項(xiàng)式插值曲線(xiàn)Fig.2 Polynomial interpolation curves of points in example 2 under different parameterizations and constraints

由圖2可見(jiàn),目標(biāo)函數(shù)值小的性質(zhì)仍可由局部傳遞到整體,對(duì)比結(jié)果如下：對(duì)例2中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及三點(diǎn)二次插值長(zhǎng)度最短約束下積累平均弧長(zhǎng)參數(shù)化法所得長(zhǎng)度最短約束目標(biāo)函數(shù)值分別為15.704，23.929，7.821；對(duì)例2中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及三點(diǎn)二次插值能量最小約束下的積累平均弧長(zhǎng)參數(shù)化法所得能量最小約束目標(biāo)函數(shù)值分別為7.085，50.689，5.932；對(duì)例2中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及四點(diǎn)雙二次插值長(zhǎng)度最短約束下積累平均弧長(zhǎng)參數(shù)化法所得長(zhǎng)度最短約束目標(biāo)函數(shù)值分別為15.704，23.929，8.763.

例3根據(jù)如下有序數(shù)據(jù)點(diǎn)集做參數(shù)三次樣條插值曲線(xiàn): {(0,10),(2,10),(3,10),(5,10),(6,10),(8,10),(9,10.5),(11,15),(12,50),(14,60),(15,85)},結(jié)果如圖3所示,圖3中“°”表示數(shù)據(jù)點(diǎn).

(A) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,三點(diǎn)二次插值長(zhǎng)度最短約束; (B) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,三點(diǎn)二次插值能量最小約束;(C) 弦長(zhǎng)參數(shù)化,向心參數(shù)化,四點(diǎn)雙二次插值長(zhǎng)度最短約束.圖3 例3中點(diǎn)在不同參數(shù)化和約束條件下的多項(xiàng)式插值曲線(xiàn)Fig.3 Polynomial interpolation curves of points in example 3 under different parameterizations and constraints

由圖3可見(jiàn),3種積累平均弧長(zhǎng)參數(shù)化法生成的插值曲線(xiàn)都與弦長(zhǎng)參數(shù)化法生成的插值曲線(xiàn)幾乎重合,但目標(biāo)函數(shù)值卻有較大差異,對(duì)比結(jié)果如下：對(duì)例3中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及三點(diǎn)二次插值長(zhǎng)度最短約束下的積累平均弧長(zhǎng)參數(shù)化法所得長(zhǎng)度最短約束目標(biāo)函數(shù)值分別為85.479，419.640，26.606；對(duì)例3中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及三點(diǎn)二次插值能量最小約束下的積累平均弧長(zhǎng)參數(shù)化法所得能量最小約束目標(biāo)函數(shù)值分別為3 915.396，1 166.199，42.341；對(duì)例3中的點(diǎn)分別進(jìn)行弦長(zhǎng)參數(shù)化、向心參數(shù)化及四點(diǎn)雙二次插值長(zhǎng)度最短約束下的積累平均弧長(zhǎng)參數(shù)化法所得長(zhǎng)度最短約束目標(biāo)函數(shù)值分別為的85.479，419.640，26.607.

與傳統(tǒng)的參數(shù)化方法相比,積累平均弧長(zhǎng)參數(shù)化法通過(guò)局部二次插值引入了額外的自由度,可利用約束準(zhǔn)則或其他方法賦予局部插值曲線(xiàn)某種性質(zhì),從而使局部插值曲線(xiàn)的性質(zhì)傳遞到全局插值曲線(xiàn)上. 這種方法可以使設(shè)計(jì)者根據(jù)需求設(shè)計(jì)參數(shù)化方法,并得到具有所需性質(zhì)的全局插值曲線(xiàn). 而無(wú)論是弦長(zhǎng)參數(shù)化還是向心參數(shù)化方法均無(wú)主動(dòng)設(shè)計(jì)的空間,其忽略了不同研究者對(duì)插值曲線(xiàn)的性質(zhì)可能有不同的需求,而自身又無(wú)法保證能生成最優(yōu)的曲線(xiàn). 本文方法給出了一種解決該問(wèn)題的思路,但本文目標(biāo)只把一個(gè)性質(zhì)從局部傳遞到整體而非多個(gè),因此求得的并非全局最優(yōu)解,而為其一個(gè)近似解,該近似解能達(dá)到全局插值曲線(xiàn)的目標(biāo)函數(shù)值小于弦長(zhǎng)參數(shù)化和向心參數(shù)化結(jié)果的目標(biāo).

3 物理解釋

圖4 質(zhì)點(diǎn)從P0到P3路徑示意圖Fig.4 Schematic diagram of particle’sroutes from P0 to P3

設(shè)平面上有4個(gè)數(shù)據(jù)點(diǎn),質(zhì)點(diǎn)從P0出發(fā),依次經(jīng)過(guò)P1,P2,最終到達(dá)P3. 將數(shù)據(jù)點(diǎn)的全局參數(shù)視為質(zhì)點(diǎn)從P0運(yùn)動(dòng)到Pi所經(jīng)過(guò)的路程. 此時(shí)問(wèn)題轉(zhuǎn)化為求質(zhì)點(diǎn)從Pi運(yùn)動(dòng)到Pi+1的路程. 圖4為質(zhì)點(diǎn)從P0到P3路徑示意圖. 由圖4可見(jiàn),平面上存在4個(gè)互異數(shù)據(jù)點(diǎn)及一個(gè)直角坐標(biāo)系. 在具體問(wèn)題中需明確坐標(biāo)系和數(shù)據(jù)點(diǎn)的坐標(biāo),這里為便于說(shuō)明,只給出其示意圖,不考慮點(diǎn)在給定坐標(biāo)系中的具體坐標(biāo).

首先,考慮質(zhì)點(diǎn)從P0運(yùn)動(dòng)到P1的路程. 由于質(zhì)點(diǎn)的實(shí)際運(yùn)動(dòng)路徑未知,所以需構(gòu)造一條連接P0和P1的特殊路徑,并用其長(zhǎng)度對(duì)實(shí)際路程進(jìn)行近似. 弦長(zhǎng)參數(shù)化中用連接P0和P1線(xiàn)段的長(zhǎng)度進(jìn)行近似,該方法簡(jiǎn)單,但實(shí)際上質(zhì)點(diǎn)不能恰好做直線(xiàn)運(yùn)動(dòng),所以誤差相對(duì)較大. 考慮用參數(shù)二次曲線(xiàn)弧的長(zhǎng)度對(duì)實(shí)際路程進(jìn)行近似,這種方法不會(huì)帶來(lái)高次插值的問(wèn)題及過(guò)大的計(jì)算量,同時(shí)也能體現(xiàn)路徑的彎曲. 注意到質(zhì)點(diǎn)在到達(dá)點(diǎn)P1后將會(huì)經(jīng)過(guò)點(diǎn)P2,因此可考慮利用P2構(gòu)造一條從P0到P1的參數(shù)二次多項(xiàng)式曲線(xiàn)弧,并做出某種限制使該弧唯一,即得到了所需的特殊路徑,如圖4中紅色曲線(xiàn)所示. 對(duì)于質(zhì)點(diǎn)從P0運(yùn)動(dòng)到P1,質(zhì)點(diǎn)經(jīng)過(guò)P2這一事件發(fā)生于未來(lái),因此本文用質(zhì)點(diǎn)從P0運(yùn)動(dòng)到P1這一段運(yùn)動(dòng)的未來(lái)信息構(gòu)造質(zhì)點(diǎn)從P0運(yùn)動(dòng)到P1的一條特殊路徑以及相應(yīng)的路程.

考慮質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2的路程. 注意到質(zhì)點(diǎn)在經(jīng)過(guò)P2后將會(huì)到達(dá)P3,從而可利用數(shù)據(jù)點(diǎn)P3,即質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2這段運(yùn)動(dòng)的未來(lái)信息構(gòu)造一條特殊路徑,如圖4中綠色曲線(xiàn)所示. 質(zhì)點(diǎn)在到達(dá)P1前曾經(jīng)過(guò)P0,可利用數(shù)據(jù)點(diǎn)P0,即質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2的這段運(yùn)動(dòng)的過(guò)去信息構(gòu)造一條特殊路徑,如圖4中紅色曲線(xiàn)所示. 本文可進(jìn)一步認(rèn)為局部參數(shù)值之間有關(guān)聯(lián),即質(zhì)點(diǎn)的過(guò)去運(yùn)動(dòng)狀態(tài)和未來(lái)運(yùn)動(dòng)狀態(tài)有關(guān)聯(lián). 這種思路可用于四點(diǎn)雙二次插值的積累平均弧長(zhǎng)參數(shù)化法. 于是得到了從P1到P2的兩條特殊路徑. 本文可要求質(zhì)點(diǎn)沿紅色或綠色的曲線(xiàn)運(yùn)動(dòng),用這段曲線(xiàn)的弧長(zhǎng)對(duì)P1到P2的實(shí)際路程進(jìn)行近似. 該方法會(huì)丟失一個(gè)數(shù)據(jù)點(diǎn)的信息. 從物理角度看,這樣做會(huì)丟失質(zhì)點(diǎn)運(yùn)動(dòng)狀態(tài)的信息. 為對(duì)質(zhì)點(diǎn)的實(shí)際運(yùn)動(dòng)路程做更精確的近似,需要更多質(zhì)點(diǎn)運(yùn)動(dòng)狀態(tài)的信息.

考慮如下問(wèn)題: 假設(shè)有大量質(zhì)點(diǎn)從P0出發(fā)運(yùn)動(dòng)到P1,則有些質(zhì)點(diǎn)可能會(huì)沿紅色路徑運(yùn)動(dòng)到P2,而其他質(zhì)點(diǎn)會(huì)沿綠色路徑運(yùn)動(dòng)到P2. 即質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2所選擇的路徑是一個(gè)隨機(jī)現(xiàn)象,其樣本空間元素個(gè)數(shù)為2. 而質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2的路程可視為一個(gè)隨機(jī)變量,該變量為離散隨機(jī)變量,因此可從概率論的角度考慮問(wèn)題. 當(dāng)質(zhì)點(diǎn)選擇紅色、綠色路徑的概率已知時(shí),則可根據(jù)兩種顏色的曲線(xiàn)夾在P1,P2間的弧長(zhǎng)計(jì)算出質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2的路程的期望,將其作為質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2的實(shí)際路程的近似值. 上述分析表明,這兩條路徑的重要程度對(duì)質(zhì)點(diǎn)是相同的,質(zhì)點(diǎn)選擇兩條路徑中任意一條的概率均為1/2. 于是可計(jì)算出質(zhì)點(diǎn)從P1運(yùn)動(dòng)到P2的路程的期望等于兩段弧長(zhǎng)的算術(shù)平均值. 若質(zhì)點(diǎn)選擇兩條路徑中任意一條的概率不相等,例如,質(zhì)點(diǎn)沿路程長(zhǎng)的路徑運(yùn)動(dòng)的概率小,或質(zhì)點(diǎn)沿能量大的路徑運(yùn)動(dòng)的概率小. 則此時(shí)從表達(dá)式上看,應(yīng)對(duì)相鄰兩點(diǎn)間的全體曲線(xiàn)弧的長(zhǎng)度計(jì)算加權(quán)平均,而非算術(shù)平均.

質(zhì)點(diǎn)從P2運(yùn)動(dòng)到P3的討論類(lèi)似于從P0運(yùn)動(dòng)到P1,差異在于后者以P0為起點(diǎn),在其之前并無(wú)數(shù)據(jù)點(diǎn),即無(wú)法使用質(zhì)點(diǎn)過(guò)去運(yùn)動(dòng)狀態(tài)的信息; 前者以P3為終點(diǎn),在其后無(wú)數(shù)據(jù)點(diǎn),即無(wú)法使用質(zhì)點(diǎn)未來(lái)運(yùn)動(dòng)狀態(tài)的信息.

從物理的角度看,這3種方法在思想上沒(méi)有本質(zhì)區(qū)別,針對(duì)于不同的需求提出不同的約束需求,例如,數(shù)控機(jī)床(CNC)軌跡規(guī)劃中在本文的能量最小約束下可具有更好的加工進(jìn)給速度. 此外,對(duì)于其他數(shù)據(jù)點(diǎn)個(gè)數(shù)的情形,物理解釋也相同. 對(duì)于計(jì)算不位于兩端的數(shù)據(jù)點(diǎn)的全局參數(shù),關(guān)鍵是首先構(gòu)造多條特殊路徑,然后計(jì)算弧長(zhǎng)平均值或路程期望,用其對(duì)實(shí)際弧長(zhǎng)或路程進(jìn)行近似.

綜上所述,本文給出的3種積累平均弧長(zhǎng)參數(shù)化方法都按積累平均弧長(zhǎng)參數(shù)化法的一般框架給出,無(wú)論是參數(shù)多項(xiàng)式插值還是參數(shù)三次樣條插值,均可得到在所選約束準(zhǔn)則下比弦長(zhǎng)參數(shù)化和向心參數(shù)化目標(biāo)函數(shù)值更小的結(jié)果. 本文只對(duì)低次參數(shù)多項(xiàng)式插值和參數(shù)三次樣條插值在不同參數(shù)化方法下求得的目標(biāo)函數(shù)值進(jìn)行了對(duì)比. 本文給出的參數(shù)化方法雖在算例中可使目標(biāo)函數(shù)值小于弦長(zhǎng)參數(shù)化和向心參數(shù)化的結(jié)果,但也存在一些示例使得積累平均弧長(zhǎng)參數(shù)化法計(jì)算得到的目標(biāo)函數(shù)值大于弦長(zhǎng)參數(shù)化或向心參數(shù)化的結(jié)果. 對(duì)這些示例進(jìn)行計(jì)算表明,積累平均弧長(zhǎng)參數(shù)化給出的全局參數(shù)較接近弦長(zhǎng)參數(shù)化給出的參數(shù),并且由于前者給出的全局參數(shù)總不小于后者在對(duì)應(yīng)點(diǎn)給出的參數(shù),使得前者得到的全局參數(shù)可被視為對(duì)后者的一個(gè)參數(shù)增加的擾動(dòng). 若積累平均弧長(zhǎng)參數(shù)化給出的目標(biāo)函數(shù)值與幾種方法中目標(biāo)函數(shù)最小值相差較小,則可從數(shù)值誤差方面進(jìn)行分析.