平面代數(shù)曲線的PH-C曲線逼近

壽華好，江 瑜，繆永偉

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

平面代數(shù)曲線的PH-C曲線逼近

壽華好1，江 瑜1，繆永偉2

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

代數(shù)曲線的近似參數(shù)化問(wèn)題是計(jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)領(lǐng)域的一個(gè)重要問(wèn)題.由于PHC曲線綜合了Bézier曲線，PH曲線以及C曲線的許多優(yōu)良性質(zhì)，從而用PH-C曲線逼近代數(shù)曲線就顯得十分必要.首先根據(jù)曲線的凹凸區(qū)間和單調(diào)區(qū)間對(duì)代數(shù)曲線進(jìn)行合理分割，然后根據(jù)曲線段兩端點(diǎn)的切線確定曲線段的三角形凸包，進(jìn)一步根據(jù)此三角形凸包確定3次PH-C曲線的控制多邊形，這樣得到的PH-C逼近曲線保持了原代數(shù)曲線的一些重要幾何性質(zhì)，如單調(diào)性、凹凸性和G1連續(xù)性，并且通過(guò)算法的遞歸調(diào)用，可以將逼近誤差控制在給定的范圍之內(nèi).數(shù)值實(shí)驗(yàn)表明，該算法提供了平面代數(shù)曲線近似參數(shù)化的一條有效途徑.

代數(shù)曲線；PH-C曲線；曲線逼近

PH曲線由于其各坐標(biāo)分量導(dǎo)數(shù)的平方和恰好為一個(gè)完全平方式，從而與一般的參數(shù)多項(xiàng)式曲線或代數(shù)曲線相比有重要的計(jì)算優(yōu)勢(shì)，例如：PH曲線具有精確的弧長(zhǎng)表示，作為數(shù)控路徑的PH曲線之等距線是有理曲線.對(duì)于離散數(shù)據(jù)的插值，PH曲線往往比普通參數(shù)多項(xiàng)式曲線具有相對(duì)均勻的曲率分布，從而有更光順的軌跡，并且能精確計(jì)算其彎曲能量等等.因此，PH曲線在CAD／CAM等相關(guān)領(lǐng)域得到了廣泛的應(yīng)用.許多學(xué)者已經(jīng)對(duì)PH曲線進(jìn)行了大量深入的研究：歷史上Farouki等首先給出了平面多項(xiàng)式曲線是PH曲線的充要條件及PH曲線的幾何構(gòu)造［1］，之后，F(xiàn)arouki等［2］分別獨(dú)立地得到了類似的空間多項(xiàng)式曲線是PH曲線的條件.Dietz［3］得到的空間多項(xiàng)式曲線是PH曲線的條件與Farouki和Sakkalis得到的平面多項(xiàng)式曲線是PH曲線的條件具有類似的結(jié)構(gòu)，只不過(guò)前者更復(fù)雜.事實(shí)上，文獻(xiàn)［2］可以看作是文獻(xiàn)［3］的特殊情況.在此基礎(chǔ)上，許多關(guān)于PH曲線的研究工作得以展開(kāi)，如用三次PH曲線構(gòu)造平面Bézier曲線的等距線算法［4］.

C-曲線是定義在空間L＝span｛sint，cos t，1，t，t2，…，tn－3｝中的曲線.它最早是由張紀(jì)文［5－7］提出，與多項(xiàng)式曲線相比，C-曲線可以精確地表示圓、橢圓、擺線等，并且求導(dǎo)方便，具有許多與Bézier曲線類似的性質(zhì)，如對(duì)稱性、幾何不變性和保凸性等.此外，C-曲線還是一類形狀可調(diào)的曲線，即在控制多邊形不變的情況下，C-曲線的形狀還可以通過(guò)它內(nèi)在的一個(gè)參數(shù)調(diào)節(jié).因此C-曲線得到了越來(lái)越廣泛的運(yùn)用，如 Morin等［8］提出了CB-樣條的細(xì)分算法，并用它來(lái)構(gòu)造旋轉(zhuǎn)曲面.

由于PH-C曲線［9］同時(shí)具有PH曲線和C曲線的諸多優(yōu)良性質(zhì)，從而用PH-C曲線去逼近代數(shù)曲線就顯得非常必要.筆者給出了代數(shù)曲線的PH-C曲線逼近算法：代數(shù)曲線分段時(shí)同時(shí)考慮了拐點(diǎn)、極值點(diǎn)和奇點(diǎn)，使得逼近曲線保持原始曲線的凹凸性的同時(shí)保持單調(diào)性和G1連續(xù)性.并且逼近曲線具有PH曲線和C-曲線的諸多優(yōu)點(diǎn).遞歸調(diào)用逼近算法，可以將誤差控制在指定的范圍之內(nèi).

1 PH-C曲線

1.1 C-曲線

由于高階PH-C曲線只可能是直線或者是多項(xiàng)式曲線［9］，因此筆者只從四階三次PH-C曲線著手.給定平面上四個(gè)控制頂點(diǎn)pi＝（xi，yi），i＝0，1，2，3，四階C-Bézie曲線定義為

四階C-曲線具有一般形式，即

其中：vi＝（vix，viy），i＝0，1，2，3是控制頂點(diǎn)pi的線性組合.將式（1）所表示的C-Bézier曲線換成它的一般形式（2），可以得到vi與控制點(diǎn)pi，i＝0，1，2，3的關(guān)系為

1.2 PH-C曲線

定義1 對(duì)于平面C-曲線P（t）＝（x（t），y（t））∈Γn，若存在z（t）∈Γn－1，使得曲線導(dǎo)數(shù)P′（t）＝（x′（t），y′（t））滿足x′（t）2＋y′（t）2＝z（t）2，則稱該曲線是PH-C曲線［9］.

2 代數(shù)曲線段的三角形凸包

2.1 代數(shù)曲線的分段

對(duì)于已知代數(shù)曲線，首先根據(jù)文獻(xiàn)［10］將其進(jìn)行分段，使得代數(shù)曲線在每個(gè)分段區(qū)間上具有固定的凹凸性和單調(diào)性，然后計(jì)算每段代數(shù)曲線兩端點(diǎn)處的切線［11］.

2.2 曲線段的三角形凸包

假定分割后的某條代數(shù)曲線段為A∶F（x，y）＝0，x∈［a，b］，設(shè)它的兩個(gè)端點(diǎn)為p0，p3，曲線段在這兩個(gè)端點(diǎn)處的切線記為T0，T3，不妨設(shè)，T0，T3必相交于一點(diǎn)，記交點(diǎn)為O.這樣p0，O，p3形成了曲線段的三角形凸包（見(jiàn)圖1）.

圖1 曲線段A的三角形凸包Fig.1 The convex hull of curve segment A

3 代數(shù)曲線的PH-C曲線逼近

3.1 控制多邊形的確定

由于C曲線具有旋轉(zhuǎn)、平移、伸縮不變性，不妨采用文獻(xiàn)［9］的做法以Δp0Op3的頂點(diǎn)O為原點(diǎn)，Op0為x軸所在直線，且p0＝（1，0）（如圖2），則控制頂點(diǎn)坐標(biāo)為

圖2 曲線段的三角形凸包Δp0 Op3及其控制多邊形p0 p1 p2 p3Fig.2 The triangle convex hullΔp 0 Op 3 of curve segment and its control polygon p0 p1 p2 p 3

將上面的各個(gè)點(diǎn)坐標(biāo)代入（3）式，可以得到

下面的定理給出了當(dāng)λ，μ取何值時(shí)，該控制多邊形確定的C-Bézier曲線是PH曲線.

在［0，1；0，1］內(nèi)的解，則由p0p1p2p3生成的四階C-Bézier曲線是PH曲線.該方程是以λ，μ為未知數(shù)，由文獻(xiàn)［9］知，它在［0，1；0，1］內(nèi)必有一根.

3.2 誤差分析

設(shè)A為代數(shù)曲線段，p（t）為插值曲線段，則給出如下誤差定義.

定義2 在參數(shù)域［0，1］上取ti＝i／n，0≤i≤n，n∈N，記p（t）上的對(duì)應(yīng)點(diǎn)為（x（ti），y（ti），A 上的對(duì)應(yīng)點(diǎn)為（ti）（ti），定義插值誤差為

3.3 算法的基本步驟

輸入代數(shù)曲線A以及誤差限δ，輸出誤差小于δ的分段插值PH-C曲線.

1）對(duì)原始代數(shù)曲線進(jìn)行分段（涉及拐點(diǎn)、奇點(diǎn)和極值點(diǎn)的計(jì)算）.

2）計(jì)算代數(shù)曲線段A兩端點(diǎn)處的切線，兩切線交點(diǎn)的坐標(biāo)以及兩切線的夾角.

3）計(jì)算PH曲線的控制多邊形.

若逼近誤差e（A，p（t））＜δ，則計(jì)算過(guò)程終止，否則，將代數(shù)曲線段一分為二，遞歸調(diào)用上述分段逼近算法，直至滿足給定的誤差要求.

4 算 例

我們采用文獻(xiàn)［10］中的例子，代數(shù)曲線（如圖3

（a））為

圖3 代數(shù)曲線C及其右四分之一分段Fig.3 The algebraic curve C and its right quarter part

我們以左上段為例，其中A（0，0），B（30／9，6／9），兩切線交點(diǎn)O（6／9，6／9），可以算出β＝3π／4，ρ＝0.874 0.由文獻(xiàn)［12］知，當(dāng)α→0時(shí)，C-曲線的正規(guī)B基趨近于四次Bézier基.這里我們?nèi)ˇ粒?.001，經(jīng)計(jì)算，（λ，μ）＝（0.624 85，0.672 12）為方程組F（3π／4，0.874 0）在［0，1；0，1］內(nèi)的解，根據(jù)（4）式可以就算出p1（0.170 1，0.170 1），p2（0.382 5，0.272 2），從而PH-C曲線的控制多邊形也就確定了.圖4是逼近效果圖.其中：實(shí)線代表原曲線，虛線表示用PH-C曲線逼近的結(jié)果.

圖5是誤差函數(shù)曲線圖.圖5中（a—d）分別表示代數(shù)曲線左上段，右上段，左下段和右下段的逼近誤差.

圖4 代數(shù)曲線的PH-C曲線逼近Fig.4 The PH-C curve approximation of algebraic curve

圖5 誤差函數(shù)曲線圖Fig.5 The error function curve

5 結(jié) 論

PH-C曲線具有同Bézier曲線類似的性質(zhì)：端點(diǎn)插值性質(zhì)，導(dǎo)矢性質(zhì)，凸包性，離散性質(zhì)，變差縮減性等.然而PH-C曲線能表示一些Bézier曲線不能精確表示的曲線：如圓弧，橢圓，正弦曲線等.由于PH-C曲線綜合了Bézier曲線，PH曲線以及C曲線的許多優(yōu)良性質(zhì)，從而比Bézier曲線，PH曲線以及C曲線有著更加廣泛的應(yīng)用.我們用三次PH-C曲線逼近代數(shù)曲線，算法簡(jiǎn)單有效，插值曲線保持了原曲線的凹凸性，單調(diào)性，G1連續(xù)性等重要幾何性質(zhì)，通過(guò)算法的遞歸調(diào)用，可以將逼近誤差控制在給定的范圍之內(nèi).

［1］FAROUKI R T，SAKKALIS T.Pythagorean hodographs［J］.IBM Journal of Research and Development，1990，34（5）：736-752.

［2］FAROUKI R T，SAKKALIS T.Pythagorean-hodograph space curves［J］.Advances in Computational Mathematics，1994，2（1）：41-66.

［3］DIETZ R，HOSCHEK J，JUTTLER B.An algebraic approach to curves and surfaces on the sphere and on other quadrics［J］.Computer Aided Geometric Design，1993，10（3／4）：211-229.

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

［5］ZHANG Ji-wen.C-curves：an extension of cubic curves［J］.Computer Aided Geometric Design，1996，13（3）：199-217.

［6］ZHANG Ji-wen.C-Bézier curves and surfaces［J］.Graphical Models and Image Processing.1999，61（1）：2-15.

［7］ZHANG Ji-wen.Two different forms of C-B-splines［J］.Computer Aided Geometric Design.1997，14（1）：31-41.

［8］MORIN G，WARREN J，WEIMER H.A subdivision scheme for surfaces of revolution［J］.Computer Aided Geometric De-

sign，2001，18（5）：483-502.

［9］陳文喻，曹娟，汪國(guó)昭.Pythagorean-Hodograph C-曲線［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2007，19（7）：822-827.

［10］胡斌，梁錫坤.代數(shù)曲線的分段有理二次B樣條插值［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43（24）：55-58.

［11］黃群賓，鄧鵬.一種求代數(shù)曲線的切線與漸近線的初等方法［J］.四川師范學(xué)院學(xué)報(bào)，2001，22（4）：389-391.

［12］陳秦玉，楊勛年，汪國(guó)昭.四次C-曲線的性質(zhì)及應(yīng)用［J］.高校

應(yīng)用數(shù)學(xué)學(xué)報(bào)：A輯，2003，18（1）：45-50.

PH-C curve approximation of planar algebraic curves

SHOU Hua-hao1，JIANG Yu1，MIAO Yong-wei2
（1.College of Science，Zhejiang University of Technology，Hangzhou 310023，China；2.College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China）

Approximate parameterization of algebraic curve is an important topic in computer aided geometric design and graphics.PH-C curve inherits all the good quality from Bézier curve，PH curve and C curve，therefore PH-C curve approximation of algebraic curve is necessary.The algebraic curve is segmented according to convexity and monotonicity，the control polygon is constructed based on angles between two tangent lines and the line connecting two end points.A detailed algorithm is proposed to approximate algebraic curve with piecewise degree 3 PH-C curve.The approximate PH-C curve keeps some important geometric features of the original algebraic curve such as convexity、monotonicity and G1continuity.The approximation error can be controlled by means of recursively use of the algorithm.Numerical experiments show that the algorithm provided an efficient approach to approximate parameterization of algebraic curve.

algebraic curve；PH-C curve；curve approximation

TP391.7

A

1006-4303（2012）01-0111-04

2010-10-15

國(guó)家自然科學(xué)基金資助項(xiàng)目（61070126，61070135）；浙江省自然科學(xué)基金資助項(xiàng)目（Y1100837）

壽華好（1964－），男，浙江諸暨人，教授，博士，研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)與圖形學(xué)，E-mail：shh＠zjut.edu.cn.

（

劉 巖）