基于三次PH曲線誤差可控代數(shù)曲線等距線逼近算法

壽華好， 江 瑜， 繆永偉

（1. 浙江工業(yè)大學(xué)理學(xué)院，浙江 杭州 310023；2.浙江工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，浙江 杭州 310023）

等距曲線在工業(yè)設(shè)計(jì)領(lǐng)域有著廣泛的應(yīng)用，例如，數(shù)控加工中車(chē)床的刀具中心軌跡的計(jì)算，機(jī)器人行走路線規(guī)劃，以及汽車(chē)外形的設(shè)計(jì), 碰撞檢測(cè)等與CAD/CAM相關(guān)的領(lǐng)域。但在通常情況下，平面參數(shù)曲線或代數(shù)曲線的等距線并不具有多項(xiàng)式或有理多項(xiàng)式表達(dá)形式，這與CAD/CAM系統(tǒng)不兼容。為此，許多學(xué)者進(jìn)行了大量深入的研究，如Lee等[1]首先在1996年提出了使用單位圓弧段逼近的N次Bézier曲線等距線生成算法。該算法首先使用Bézier曲線逼近單位圓弧段，然后生成該單位圓弧段與原始曲線的卷積曲線，最后利用卷積曲線逼近Bézier曲線等距線。Lee算法的優(yōu)點(diǎn)是具有明確的誤差范圍，但卷積曲線是3N-2階的有理Bézier曲線，當(dāng)待求等距線的Bézier曲線次數(shù)N 比較大時(shí)，計(jì)算量非常大。由于Lee算法使用有理Bézier曲線逼近等距線，與其它求取等距線算法相比沒(méi)有明顯優(yōu)勢(shì)，所以基于單位圓弧段算法沒(méi)有引起研究者注意。直到2004年Ahn等[2]進(jìn)一步將卷積曲線表示為與原曲線等次數(shù)的Bézier曲線，解決了Lee算法在Bézier曲線的次數(shù)N較大時(shí)的計(jì)算量偏大問(wèn)題。但Ahn算法只使用二次Bézier曲線逼近單位圓弧段，精度較低。2004年鄭志浩等[3]提出了用三次PH曲線構(gòu)造平面Bézier曲線的等距線算法。該算法是根據(jù)Bézier曲線的始末端點(diǎn)及其切向量，加入節(jié)點(diǎn)，使其滿足PH曲線的條件，以此構(gòu)造出來(lái)的PH曲線來(lái)逼近原Bézier曲線，并進(jìn)而生成等距線。該算法通過(guò)增加節(jié)點(diǎn)數(shù)可控制逼近誤差在所需的范圍內(nèi)，本文引用文獻(xiàn)[3]中構(gòu)造PH曲線的方法，用PH曲線來(lái)逼近平面代數(shù)曲線，并生成PH曲線的等距線，作為平面代數(shù)曲線等距線的近似表示。

基于逼近算法計(jì)算比較簡(jiǎn)單的考慮，這里給出的代數(shù)曲線的PH曲線逼近有自身的特點(diǎn): 曲線分段時(shí)同時(shí)考慮了拐點(diǎn)和極值點(diǎn)，使得逼近曲線保持原始曲線的凹凸性的同時(shí)保持單調(diào)性和G1連續(xù)性。遞歸調(diào)用逼近算法，可以將誤差控制在指定的范圍之內(nèi)。而用PH曲線的精確等距線逼近原代數(shù)曲線的等距線，無(wú)需采用細(xì)分策略，通過(guò)誤差分析可知采用本算法所獲得逼近精度大大得到了提高。

1 三次PH曲線的定義及性質(zhì)

本文的研究建立在三次PH曲線的基礎(chǔ)上，所以需要先考查三次PH曲線的幾何性質(zhì)。

定義 1[4]PH曲線((),())x ty t 為滿足如下條件的平面參數(shù)曲線

其中，σ(t)是一個(gè)多項(xiàng)式。

引理 1[3]一個(gè)三次Bézier曲線是PH曲線的充要條件是

其中，p0，p1，p2和p3分別是三次PH曲線的控制頂點(diǎn)，L1,L2,L3分別為三次PH曲線的邊長(zhǎng)（如圖1所示）。

圖1 三次PH曲線

定義 2 PH曲線等距線

N次PH曲線p( t)的等距線 pr( t)可以被定義為

其中，r為等距距離，n(t)是p( t)的單位法向量，它可以通過(guò)p( t)的單位切向量旋轉(zhuǎn)π/2得到，具體的計(jì)算公式為

2 用三次PH曲線逼近平面代數(shù)曲線

2.1 對(duì)代數(shù)曲線進(jìn)行分段并計(jì)算每段子曲線兩端點(diǎn)處的切線

首先將代數(shù)曲線進(jìn)行分段[5]使得代數(shù)曲線在每個(gè)分段區(qū)間上具有固定的凹凸性和單調(diào)性。然后計(jì)算每段代數(shù)曲線兩端點(diǎn)處的切線[6]。

2.2 控制多邊形的確定

圖2 給定曲線兩端點(diǎn)的位置及其曲線在端點(diǎn)處的切線方向

圖3 構(gòu)造出的PH曲線的控制多邊形

這是一個(gè)關(guān)于L2的一元二次方程，由此可以解得L2，再由

可以得到L0，由此三次PH曲線的控制多邊形就可以確定了。

2.3 等距線生成

3 分段逼近誤差

3.1 逼近誤差

設(shè)A為代數(shù)曲線段，p( t)為逼近曲線段，在幾何學(xué)中，曲線A和它的逼近曲線之間的誤差經(jīng)常使用Hausdorff距離來(lái)表示，但是這種距離便于理論分析而不便于計(jì)算。下面給出一種易于計(jì)算的誤差概念。

3.2 算法的基本步驟

1）先對(duì)原始代數(shù)曲線進(jìn)行分段（涉及拐點(diǎn)和極值點(diǎn)的計(jì)算，計(jì)算代數(shù)曲線拐點(diǎn)和極值點(diǎn)的算法見(jiàn)參考文獻(xiàn)[7]）；

2）計(jì)算曲線段A兩端點(diǎn)處的切線及其與弦長(zhǎng)的夾角；

3）根據(jù)式(4）～(6)計(jì)算PH曲線的控制多邊形；

4）若逼近誤差 e( A, p( u ) )＜δ，則計(jì)算過(guò)程終止，否則，采用逐步二分分段區(qū)間的方法，遞歸調(diào)用上述分段逼近算法，直至滿足給定的誤差要求。

5）計(jì)算逼近PH曲線的等距線，以它來(lái)逼近原代數(shù)曲線的等距線。

4 實(shí) 例

曲線C的整體逼近效果如圖4所示。圖中虛線表示原曲線，實(shí)線是用分段PH曲線逼近得到的結(jié)果，分段PH曲線的逼近效果非常好。

圖4 曲線C的右四分之一及它的PH逼近曲線

圖5 曲線C的右四分之一的分段誤差函數(shù)圖形（依次為左上段、右上段、右下段、左下段）

根據(jù)定義2計(jì)算出4段PH曲線的等距線如圖6所示。由于等距線不過(guò)是生成曲線在法線方向上平移距離r后得到，從而只要逼近PH曲線和原代數(shù)曲線的誤差小于δ，那么逼近PH曲線的等距線（即逼近等距線）與原代數(shù)曲線的等距線（即精確等距線）的誤差一定也小于δ。

對(duì)于上圖內(nèi)外兩條等距線，外面一條沒(méi)有封閉上的情況，可以原點(diǎn)為圓心，等距距離r為半徑做一段圓弧；而對(duì)于里面一條出現(xiàn)交叉的現(xiàn)象，可求出交點(diǎn)，然后將多余部分裁減掉。圖7是處理后的結(jié)果。

圖7 處理后的圖形

5 結(jié) 論

代數(shù)曲線的分段三次PH逼近算法簡(jiǎn)單有效，逼近曲線保持了原曲線的凹凸性，單調(diào)性，G1連續(xù)性等重要幾何性質(zhì)，通過(guò)算法的遞歸調(diào)用，可以將逼近誤差控制在給定的范圍之內(nèi)。另外，通過(guò)增加曲線的分段可控制逼近誤差與等距誤差，從而生成由同樣低次數(shù)、結(jié)構(gòu)統(tǒng)一、便于數(shù)據(jù)存儲(chǔ)的等距線。

[1]Lee I K, Kim M S, Elber G. Planar curve offset based on circle approximation [J]. Computer-Aided Design,1996, 28(8): 617-630.

[2]Ahn Y J, Kim Y S, Shin Y. Approximation of circular arcs and offset curves by Bézier curves of high degree [J].Journal of Computational and Applied Mathematics,2004, 167(2): 405-416.

[3]鄭志浩, 汪國(guó)昭. 用三次PH曲線構(gòu)造平面Bézier曲線的等距線算法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004, 16(3): 324-330.

[4]雍俊海, 鄭 文. 一類(lèi)五次PH曲線Hermite插值的幾何方法[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2005,17(5): 990-995.

[5]胡 斌, 梁錫坤. 代數(shù)曲線的分段有理二次B樣條插值[J]. 計(jì)算機(jī)工程與應(yīng)用, 2007, 43(24): 55-58.

[6]黃群賓, 鄧 鵬. 一種求代數(shù)曲線的切線與漸近線的初等方法[J]. 四川師范學(xué)院學(xué)報(bào), 2001, 22(4):389-391.

[7]Shou Huahao, Shen Jie, Yoon D. Numerical computation of singular and inflection points on planar algebraic curves[C]//Hamid R A (Ed.),Proceedings of 2007 International Conference on Computer Graphics & Virtual Reality, CSREA Press,USA, 2007: 133-138.