鄧重陽(yáng)

（杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018）

用細(xì)分螺線插值容許G2Hermite數(shù)據(jù)

鄧重陽(yáng)

（杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018）

為使幾何細(xì)分方法生成的平面螺線段插值平面容許G2Hermite數(shù)據(jù)，基于平面雙圓弧插值理論提出了該方法首末端點(diǎn)處新的細(xì)分規(guī)則。理論分析表明，修改后的細(xì)分方法所得極限曲線是曲率單調(diào)、不變號(hào)的螺線段，且插值首末端點(diǎn)處的點(diǎn)、切向、曲率。數(shù)值算例表明，修改后的細(xì)分方法收斂速度較快，極限曲線具有較好的形狀。

平面螺線；容許G2Hermite數(shù)據(jù)；Hermite插值

螺線段是曲率單調(diào)上升或下降且不變號(hào)的曲線。因?yàn)椴缓蕵O值點(diǎn)和尖點(diǎn)，螺線段被認(rèn)為是光順曲線[1]。螺線設(shè)計(jì)在數(shù)學(xué)上的重要性體現(xiàn)于它在工程設(shè)計(jì)領(lǐng)域[2]及美學(xué)領(lǐng)域[3]中的重要應(yīng)用上。

為了使兩段螺線段在連接點(diǎn)處達(dá)到G2連續(xù)，設(shè)計(jì)螺線時(shí)要求螺線段能插值兩端點(diǎn)及兩端點(diǎn)處的切向、曲率，即要插值兩點(diǎn)G2Hermite數(shù)據(jù)。螺線段只能插值特定的兩點(diǎn)G2Hermite數(shù)據(jù)，稱為容許G2Hermite數(shù)據(jù)。Meek和Walton用回旋螺線和一段圓弧[4]、一段指定的螺線和一段圓弧[5]插值容許 G2Hermite數(shù)據(jù)。Ait Haddou和Biard[6]用一對(duì)畢達(dá)哥拉斯曲線（Pythagorean Hodograph 曲線，簡(jiǎn)稱PH曲線）的漸開(kāi)線所形成的螺線來(lái)插值容許G2Hermite數(shù)據(jù)。Kuroda和Mukai[7]則用圓弧段的漸開(kāi)線所形成的螺線來(lái)插值 G2Hermite數(shù)據(jù)。近年來(lái)，用（有理）Bezier曲線[8-9]和 PH 曲線[10-13]構(gòu)造螺線來(lái)插值容許G2Hermite數(shù)據(jù)成為一個(gè)研究熱點(diǎn)。但據(jù)我們所知，還沒(méi)有文獻(xiàn)涉及用細(xì)分方法所得螺線段插值容許G2Hermite數(shù)據(jù)的問(wèn)題。

用插值型細(xì)分方法構(gòu)造插值曲線曲面是計(jì)算機(jī)輔助幾何設(shè)計(jì)中一種重要的造型方法。它具有算法簡(jiǎn)單、適用于多分辨率造型等諸多優(yōu)點(diǎn)。但與參數(shù)曲線曲面插值方法、隱式曲線曲面插值方法等造型方法相比，插值型細(xì)分方法所得插值曲線曲面的質(zhì)量難以保證，且形狀難以控制。例如，以四點(diǎn)插值細(xì)分法[14]為代表的線性細(xì)分方法受人為痕跡、多余拐點(diǎn)等不良現(xiàn)象所困擾，而以基于幾何特征為代表的非線性插值型細(xì)分方法[15-16]則連續(xù)階不高，且其收斂性的證明較為復(fù)雜。最近，我們提出了生成螺線段的幾何細(xì)分方法[17]，但該方法只能匹配G1Hermite數(shù)據(jù)。本文在該方法的基礎(chǔ)上，基于雙圓弧插值的理論修改其端點(diǎn)處的細(xì)分規(guī)則，使該方法生成的螺線能插值給定容許G2Hermite數(shù)據(jù)。

1 記號(hào)及背景知識(shí)

1.1 記號(hào)及初始假設(shè)

本文中，逆時(shí)針?lè)较蛐D(zhuǎn)的角為正角，順時(shí)針?lè)较蛐D(zhuǎn)的角為負(fù)角。點(diǎn) pk與 pk之間的距離ii+1記為或

因?yàn)楸疚乃貌逯登€為曲率不變號(hào)的螺線，不失一般性，我們假定所有初始給定的角都是正角。

1.2 容許G2Hermite 數(shù)據(jù)

G2Hermite數(shù)據(jù)記為(A, T ,κ ;B,T ,κ )，也

AA BB可記為(A, TA,OA;B, TB,OB)，其中TA,TB為 A,B兩點(diǎn)處的單位切向量， κA,κB分別為 A,B兩點(diǎn)處的曲率， OA,OB分別為 A,B兩點(diǎn)處曲率圓的圓心。若記 rA= 1/κA,rB= 1/κBA,B兩點(diǎn)處曲率圓的半徑，則不失一般性，我們可以假定 κA＞ κB≥ 0。

給定G2Hermite數(shù)據(jù){A, TA,κA;B,TB,κB}，記αA,αB分別為從 TA到AB 和從AB到 TB的角。若κA＞ κB≥ 0，則{A ,TA,κA;B,TB,κB}為容許G2Hermite數(shù)據(jù)，即存在螺線插值它的充要條件[12]（如圖1所示）。

1） αA＞ αB＞0

2） 圓 OA（以 OA為圓心，為半徑）內(nèi)含于圓 OB（以 OB為圓心，為半徑）。

圖1 容許G2Hermite數(shù)據(jù)

1.3 雙圓弧

設(shè)A，B為相異兩點(diǎn)，TA，TB為A，B 兩點(diǎn)處的單位切向。記從TA到AB的角為 αA，從AB到TB的角為 αB。令O為插值 A,B兩點(diǎn)且對(duì)弦AB的張角為 π? (αA+ αB)/2的圓弧段，如圖2中的虛線所示圓弧段，則雙圓弧的連接點(diǎn)在且只在圓弧段O上[18]。令J為雙圓弧的連接點(diǎn)，T為J點(diǎn)處兩圓的公共切向量，θ為從TA到T 的角，為了控制雙圓弧的形狀，一般取θ為控制雙圓弧曲線的自由參數(shù)。

如果 αA,αB同號(hào)，則插值A(chǔ)，B兩點(diǎn)，TA，TB兩切向的雙圓弧為C形，否則為S形。由于本文考慮螺線插值，所以只討論C形雙圓弧。對(duì)于自由參數(shù)θ，在大部分情況下，θ = α是一個(gè)比較合適的選擇[19]，如圖2所示。

圖2 平面C形雙圓弧

由以上兩式易知， rL,rR都是關(guān)于θ的減函數(shù)[18]。所以我們有

引理 1 對(duì)于G1Hermite數(shù)據(jù){A, TA;B,TB}，TA到AB的角記為α，AB到 TB的角記為β，且α ＞ β，插值{A, TA;B,TB}的雙圓弧連接點(diǎn)所在圓弧段為O。 P1,P2為圓弧段O上的兩點(diǎn)。若∠ AOP1＜∠ AOP2，則rR(P1) ＜rR(P2),rL(P1) ＜ rL(P2)。

引理 2 容許G2Hermite 數(shù)據(jù)

(A, TA,κA;B,TB,κB)中，若 κA＞ κB≥ 0，則在插值(A, TA;B,TB)的雙圓弧中，存在以P為連接點(diǎn)的雙圓 弧 使 得 rB＞ rL(P )＞ rR(P )＞rA。 這 里rA= 1/κA,rB=1/κB。

證 明 令圓 OA，圓 OB(圓心分別為 OA,OB)是 A,B兩點(diǎn)處的曲率圓。

容許G2Hemite 數(shù)據(jù)(A, TA,κA;B,TB,κB)，由κA＞ κB≥0得0 ＜ αB＜ αA。

記O為插值A(chǔ)，B兩點(diǎn)且對(duì)線段AB的夾角為 π? (αA+ αB)/2的圓弧（圖3中虛線所示圓弧段）。記O在點(diǎn)A處的切向量為 TCA，則從 TCA到AB的角為(αA+ αB)/2。所以圓O與圓 OA有兩個(gè)交點(diǎn)。顯然A為圓C與圓 OA的一個(gè)交點(diǎn)。記圓O與 OA的另外一個(gè)交點(diǎn)為 A'，由(αA+αB)/2＜αA可知， A'在 A, TA,AB所確定區(qū)域內(nèi)。同理，圓O與 OB除了交點(diǎn)B之外，還有一個(gè)交點(diǎn) B'，且 B'在B, ?TB,BA所確定的區(qū)域內(nèi)，如圖3所示。

圖3 滿足半徑單調(diào)條件的雙圓弧

由κA＞ κB≥ 0知 OB內(nèi)含于 OA，所以 B' 介于 A',B之間。設(shè)P為圓弧段O上介于 A'B'的一點(diǎn)，以P為連接點(diǎn)且插值(A, TA;B,TB)的雙圓弧的半徑分別為 rR(P),rL(P )，由引理 1可得rB＞ rL(P ) ＞ rR(P )＞rA。證畢。

2 細(xì)分方法

給定初始的容許G2Hermite數(shù)據(jù) {p00,T00,O00; p0,T0,O0}，在第 k個(gè)細(xì)分步驟中，我們保持老11 1頂點(diǎn)不變，但老頂點(diǎn)重新標(biāo)記為 pk+1= pk，在每?jī)蓚€(gè)老頂點(diǎn) pik,pik+1之間根據(jù)兩點(diǎn) pik,pik+1及其切向(在端點(diǎn)處還要用到曲率信息)插入一個(gè)新點(diǎn)，并對(duì)新點(diǎn)列的每一個(gè)點(diǎn)定義一個(gè)切向使細(xì)分進(jìn)行下去。下面我們分別闡述加入新點(diǎn)的規(guī)則及確定切向的規(guī)則。

2.1 加入新點(diǎn)的規(guī)則

我們把加入新點(diǎn)的規(guī)則按相鄰兩點(diǎn)是否為端點(diǎn)分為3類(lèi)：相鄰兩點(diǎn)都是端點(diǎn)；相鄰兩點(diǎn)都不是端點(diǎn)；相鄰兩點(diǎn)有一個(gè)是端點(diǎn)。下面分別介紹這3類(lèi)確定新點(diǎn)的規(guī)則。

2.1.1 相鄰兩點(diǎn)都是端點(diǎn)

實(shí)際上，這種情況只在第1步細(xì)分的時(shí)候出現(xiàn)。此時(shí)，對(duì)于初始的容許 G2Hermite數(shù)據(jù)確定點(diǎn) p1的方法是：1

設(shè)插值 p00,p10兩點(diǎn)且對(duì)線段 p00p10張角為π? (α + β)/2的圓弧段為O，其圓心記為O（圖4中虛線所示圓弧段），圓 O00(圓心為 O00，半徑為與圓弧段O的交點(diǎn)為 A'; 圓 O0(圓心為1 O10，半徑為與圓O的交點(diǎn)為 B'?！?A'OB'的平分線與圓弧段O的交點(diǎn)即為 p11。

圖4 相鄰兩點(diǎn)都是端點(diǎn)時(shí)的加入新點(diǎn)規(guī)則

2.1.2 相鄰兩點(diǎn)都不是端點(diǎn)

2.1.3 相鄰兩點(diǎn)有一個(gè)是端點(diǎn)

這種情形實(shí)際上還可以分成兩種情況：pk,pk為 pk,pk或 pk,pk。這兩種情況下的規(guī)ii+1012k?12k則是完全類(lèi)似的。

1） pik,pik+1為 p0k,p1k

否則，令 p1k+1為插值的雙圓弧的連接圓弧上滿足以下條件的點(diǎn)

2.2 確定切向的規(guī)則

其中

3 光滑性分析

文獻(xiàn)[17]已經(jīng)證明了生成平面螺線的幾何細(xì)分方法的收斂性和光滑性。由于本文算法僅對(duì)端點(diǎn)處的規(guī)則做了修改，所以只要對(duì)端點(diǎn)說(shuō)明其收斂性和光滑性即可。

定 理 第1節(jié)所定義的細(xì)分方法細(xì)分容許G2Hermite數(shù)據(jù)所得極限曲線是插值的平面螺線。

證 明 與文獻(xiàn)[17]相同的方法可以證明極限曲線的收斂性、G1、G2連續(xù)性以及極限曲線是螺線。在這里我們僅證明極限曲線插值容許G2Hermite數(shù)據(jù)的兩個(gè)端曲率即可。

由第3.1節(jié)的加入新點(diǎn)規(guī)則可知，

所以極限曲線插值兩個(gè)端曲率，證畢。

4 數(shù)值算例

我們已在很多實(shí)例中檢驗(yàn)了本文算法，本節(jié)給出 4個(gè)有代表性的數(shù)值算例。所有實(shí)例中，對(duì)于每一個(gè)實(shí)例，我們畫(huà)出了7個(gè)細(xì)分步驟后的離散點(diǎn)列，如圖5中各圖的藍(lán)色實(shí)線及其離散曲率，如圖5中各圖的紅色實(shí)線，每個(gè)離散點(diǎn)列有257個(gè)點(diǎn)。為了更好地了解極限曲線的性質(zhì)，我們?cè)趫D中畫(huà)出每個(gè)點(diǎn)的離散曲率，如圖5中紅線，其長(zhǎng)度為實(shí)際曲率的0.2倍，即此點(diǎn)及附近三點(diǎn)所確定的圓在此點(diǎn)處的曲率。令點(diǎn) pk處的離散曲率為 κk，記ii我們?cè)诒?中給出了每個(gè)細(xì)分步驟后的 Dk及從表1可知，基本上處于0.5至0.8之間，所以相鄰兩點(diǎn)間的離散曲率之差以較快的速度趨向于0。

表1 每個(gè)細(xì)分步驟后 Dk, Dk /Dk?1的變化情況

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

5 結(jié) 論

本文介紹了一種用幾何細(xì)分方法生成的螺線插值容許 G2Hemite數(shù)據(jù)的方法。其方法僅在第一步細(xì)分規(guī)則及兩端點(diǎn)處的細(xì)分規(guī)則做了修改，其余點(diǎn)處的細(xì)分規(guī)則與生成螺線段細(xì)分方法完全相同。理論分析表明，本文所述細(xì)分方法所得點(diǎn)列收斂于一條螺線段，且插值兩端點(diǎn)處的G2Hermite數(shù)據(jù); 數(shù)值算例表明，其算法運(yùn)算穩(wěn)定，收斂速度較快。

[1] Farin G. Curves and surfaces for computer aided geometric design [M]. A Practical Guide, fourth ed., Academic Press, San Diego, 1997: 364.

[2] Gibreel G M, Easa S M, Hassan Y, et al. State of the art of highway geometric design consistency [J]. Journal of Transportation Engineering, 1999, 125(4): 305-313.

[3] Burchard H G, Ayers J A, Frey W H, et al. Approximation with aesthetic constraints [M]. Designing Fair Curves and Surfaces, SIAM, 1994: 3-28.

[4] Meek D S, Walton D J. Clothoid spline transition spirals [J]. Mathematics of Computation, 1992, 59: 117-133.

[5] Meek D S, Walton D J. Planar spirals that match G2hermite data [J]. Computer Aided Geometric Design, 1998, 15: 103-126.

[6] Ait H R, Biard L. G2approximation of an offset curve by Tschirnhausen quartics [C]//Dahlen M, Lyche T, Schumaker LL (Eds), Mathematical Methods for Curves and Surfaces. Vanderbilt University Press, 1995: 1-10.

[7] Kuroda M, Mukai S. Interpolating involute curves[C]// Cohen A, Rabut C, Schumaker LL. Curve and Surface Fitting, Saint Malo, 1999. Vanderbilt University Press, Nashville, 1999: 1-8.

[8] Frey W H, Field D A. Designing Bezier conics segments with monotone curvature [J]. Computer Aided Geometric Design, 2000, 17(6): 457-483.

[9] Dietz D A, Piper B. Interpolation with cubic spirals [J]. Computer Aided Geometric Design, 2004, 21(2): 165-180.

[10] Habib Z, Sakai M. On PH quintic spirals joining two circles with one circle inside the other [J]. Computer Aided Design, 2007, 39(2): 125-132.

[11] Habib Z, Sakai M. G2Pythagorean hodograph quintic transition between two circles with shape control [J]. Computer Aided Geometric Design, 2007, 24(5): 252-266.

[12] Walton D J, Meek D S. G2curve design with a pair of pythagorean hodograph quintic spiral segments [J]. Computer Aided Geometric Design, 2007, 24(5): 267-285.

[13] Goodman T N T, Meek D S, Walton D J. An involute spiral that matches G2Hermite data in the plane [J]. Computer Aided Geometric Design, 2009, 26(9): 733-756.

[14] Dyn N, Levin D, Gregory J A. A 4-point interpolatory subdivision scheme for curve design [J]. Computer Aided Geometric Design, 1987, 4(4): 257-268.

[15] Yang Xunnian. Normal based subdivision scheme for curve design [J]. Computer Aided Geometric Design, 2006, 23(3): 243-260.

[16] 鄧重陽(yáng), 汪國(guó)昭. 曲線插值的一種保凸細(xì)分方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2009, 21(8): 1042-1046.

[17] Deng Chongyang, Wang Guozhao. Generating planar spiral by geometric subdivision scheme [J]. Science of China, Series F, Information Science. 2009, 52(10): 1821-1829.

[18] 蘇步青, 劉鼎元. 計(jì)算幾何[M]. 上海科學(xué)技術(shù)出版社, 1985: 195-204.

Spiral-preserving geo2metric subdivision scheme for admissible G Hermite interpolation

Deng Chongyang
( College of Science, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China )

To interpolate admissible G2Hermite data, this paper proposes a modified geometric subdivision scheme with new subdivision rules near the end points of the curve. The method is based on the theory of planar biarc curve interpolation. Theoretical analysis shows that the limit curves of the modified subdivision scheme are planar spirals, which are curves of one-signed, monotone increasing or decreasing curvature. Numerical examples show that the modified subdivision scheme converge rapidly, and the limit curves are with nice shape.

planar spiral; admissible G2Hermite data; Hermite interpolation

TP 391

A

2095-302X (2012)02-0039-06

2011-09-29

國(guó)家自然科學(xué)基金數(shù)學(xué)天元青年基金資助項(xiàng)目（10926058，11026107）；國(guó)家自然科學(xué)基金青年基金資助項(xiàng)目（61003194）

鄧重陽(yáng)（1976-），男，湖南隆回人，副教授，博士，主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)。