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

壽華好，江 瑜，繆永偉

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

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

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

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

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

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

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

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

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

1 PH-C曲線

1.1 C-曲線

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

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

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

1.2 PH-C曲線

定義1 對于平面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ù)曲線的分段

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

2.2 曲線段的三角形凸包

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

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

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

3.1 控制多邊形的確定

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

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

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

在［0，1；0，1］內(nèi)的解，則由p0p1p2p3生成的四階C-Bézier曲線是PH曲線.該方程是以λ，μ為未知數(shù)，由文獻［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）上的對應(yīng)點為（x（ti），y（ti），A 上的對應(yīng)點為（ti）（ti），定義插值誤差為

3.3 算法的基本步驟

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

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

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

3）計算PH曲線的控制多邊形.

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

4 算 例

我們采用文獻［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），兩切線交點O（6／9，6／9），可以算出β＝3π／4，ρ＝0.874 0.由文獻［12］知，當(dāng)α→0時，C-曲線的正規(guī)B基趨近于四次Bézier基.這里我們?nèi)ˇ粒?.001，經(jīng)計算，（λ，μ）＝（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是逼近效果圖.其中：實線代表原曲線，虛線表示用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ì)：端點插值性質(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ù)曲線，算法簡單有效，插值曲線保持了原曲線的凹凸性，單調(diào)性，G1連續(xù)性等重要幾何性質(zhì)，通過算法的遞歸調(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］鄭志浩，汪國昭.用三次PH曲線構(gòu)造平面Bézier曲線的等距線算法［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，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］陳文喻，曹娟，汪國昭.Pythagorean-Hodograph C-曲線［J］.計算機輔助設(shè)計與圖形學(xué)學(xué)報，2007，19（7）：822-827.

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

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

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

應(yīng)用數(shù)學(xué)學(xué)報：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

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

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

（

劉 巖）