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

壽華好， 江 瑜， 繆永偉

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

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

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

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

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

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

其中，σ(t)是一個多項式。

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

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

圖1 三次PH曲線

定義 2 PH曲線等距線

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

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

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

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

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

2.2 控制多邊形的確定

圖2 給定曲線兩端點的位置及其曲線在端點處的切線方向

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

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

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

2.3 等距線生成

3 分段逼近誤差

3.1 逼近誤差

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

3.2 算法的基本步驟

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

2）計算曲線段A兩端點處的切線及其與弦長的夾角；

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

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

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

4 實 例

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

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

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

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

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

圖7 處理后的圖形

5 結(jié) 論

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

[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]鄭志浩, 汪國昭. 用三次PH曲線構(gòu)造平面Bézier曲線的等距線算法[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報，2004, 16(3): 324-330.

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

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

[6]黃群賓, 鄧 鵬. 一種求代數(shù)曲線的切線與漸近線的初等方法[J]. 四川師范學(xué)院學(xué)報, 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.