平面二次代數(shù)曲線的最優(yōu)參數(shù)化

厲玉蓉， 胡芳剛

（1. 山東工商學(xué)院計算機科學(xué)與技術(shù)學(xué)院，山東 煙臺 264005；2. 山東師范大學(xué)信息科學(xué)與工程學(xué)院，山東 濟南 250014）

曲線、曲面是計算機圖形學(xué)(CG)和計算機輔助幾何設(shè)計(CAGD)中的基本研究對象。參數(shù)形式和隱式形式是表示曲線、曲面的兩種主要方式。兩種表示形式各有其內(nèi)在的優(yōu)點，有效地實現(xiàn)二者的相互轉(zhuǎn)換一直是 CAGD的一個熱點問題[1-9]。從數(shù)學(xué)意義上講，二次代數(shù)曲線曲面的有理參數(shù)化問題已經(jīng)完全解決了，但遠不能滿足實際應(yīng)用的需求。首先，在幾何造型領(lǐng)域中，通常是對某一曲線上的一部分感興趣，而非整條曲線；其次，工程人員更希望得到最優(yōu)參數(shù)化，即當(dāng)參數(shù)均勻選取時，對應(yīng)點間的弧長也能夠較為均勻。傳統(tǒng)的參數(shù)化方程對目標(biāo)曲線段的效果很難確定，例如，對單位圓的有理參數(shù)化，多用下式來表示

當(dāng)t∈(0,1)時，表示圓在第1象限的部分，但是，這個有理參數(shù)化并不是圓在第1象限的最優(yōu)參數(shù)化結(jié)果。

代數(shù)曲線參數(shù)化后，得到新的曲線方程，參數(shù)化因子不同，則得到的參數(shù)曲線的方程不同。不妨將目標(biāo)曲線段的參數(shù)域定為[0, 1]，若將參數(shù)視為時間，曲線視為物體移動路線，最優(yōu)參數(shù)化實質(zhì)上是尋求物體速率變化最小的參數(shù)化結(jié)果。

對于一般的有理參數(shù)化而言，弧長參數(shù)化基本不可能取到，只能在固定參數(shù)化形式中，尋求最接近弧長的參數(shù)化方程。Farouki[10]提出了最優(yōu)參數(shù)化的標(biāo)準(zhǔn)，并試圖按這個標(biāo)準(zhǔn)對曲線的參數(shù)化進行優(yōu)化。對于代數(shù)曲線的參數(shù)化，無論是評判標(biāo)準(zhǔn)還是計算過程，都過于復(fù)雜。

為此，本文提出以參數(shù)曲線切矢量模的最大和最小值的比與1的接近程度作為衡量參數(shù)化是否為最優(yōu)的評判標(biāo)準(zhǔn)，并在此標(biāo)準(zhǔn)下構(gòu)造出任意一段二次曲線的最優(yōu)或逼近最優(yōu)的有理參數(shù)化方程。大量實例表明，本文方法可以達到或接近于最優(yōu)標(biāo)準(zhǔn)，且計算量小，效率高，具有較強的自適應(yīng)性。

1 本文算法

在 CAGD和 CG中常用到代數(shù)曲線的某一段，而不是整條曲線。本算法基本解決了平面二次代數(shù)曲線上任一段曲線的最優(yōu)參數(shù)化問題。

1.1 最優(yōu)參數(shù)化

1.2 算法描述

算法的基本思想是：過A點構(gòu)造一簇直線，參數(shù)方程P(t)即是這簇直線和代數(shù)曲線f ( x,y)=0的異于A的交點。

由于曲線 C : f( x, y) = 0 過A點，其方程可寫成以下形式

這條直線與曲線 f (x,y) =0有 2個交點，其中之一為點A。從而，由式(1)、(3)可得曲線段AB對應(yīng)于參數(shù)[0,1]的二次有理參數(shù)方程

定理 1 對于一段圓弧，橢圓或雙曲線上的具有對稱性質(zhì)部分的有理參數(shù)化，用本文算法得到的就是按1.1節(jié)中評判標(biāo)準(zhǔn)的最優(yōu)結(jié)果。

證 明 在二次代數(shù)曲線上任取一個異于AB的點E，F(xiàn) =(1-t)A+tB(t∈[0,1])是線段AB上的點，經(jīng)過點E、F的直線與二次曲線必有二個交點，P(t)即是這簇直線和代數(shù)曲線f(x,y)= 0 的異于E的交點。這個過程可以解釋為，以E為視點，弧AB在線段AB上的透視投影。事實上，二次代數(shù)曲線的任意有理參數(shù)化都可以按上述方式解釋。顯然，若弧AB有對稱性，當(dāng)E取為AB的垂直平分線與二次曲線的不在弧AB上的交點時，為最優(yōu)的有理參數(shù)化表示。此最優(yōu)的參數(shù)化表示與將入方程(4)得到的結(jié)果相同。

證畢。

當(dāng)θ＞90°時，即AB曲線段相對彎曲較大時，任意的有理參數(shù)化結(jié)果都不理想，例如，對3/4圓弧，此情況下，可對其分段后再進行有理參數(shù)化。

2 實例分析

2.1 實例 1

t等距選取時計算出的參數(shù)點如圖1中實心較大方點所示, 此時

圖1 1/4圓弧的參數(shù)化對比效果圖

2.2 實例 2

用傳統(tǒng)有理參數(shù)化方程，即

圖2 橢圓弧的參數(shù)化對比效果

t等距選取時計算出的參數(shù)點如圖2實心較大方點所示, 此時Γ(P(t))≈1.23。

3 結(jié) 論

本文提出了新的平面代數(shù)曲線最優(yōu)有理參數(shù)化的評判標(biāo)準(zhǔn)。從理論上講，最優(yōu)有理參數(shù)化方程可求，但是計算量非常巨大。本文構(gòu)造出平面二次代數(shù)曲線上任一段曲線的十分接近于最優(yōu)的有理參數(shù)化方程，所用計算量小，效率高，具有較強的自適應(yīng)性。特別是當(dāng)所求曲線段是一段圓弧，或者是橢圓或雙曲線上的具有對稱性質(zhì)的部分時，得到的就是按1.1節(jié)中評判標(biāo)準(zhǔn)的最優(yōu)有理參數(shù)化。

[1]Abhyakar S S, Bajaj C. Automatic parameterization of rational curves and surfaces III: algebraic plane curves [J].Computer Aided Geometric Design, 1988, 5(4):309-321.

[2]Sendra J R, Winkler F. Symbolic parametrization of curves [J]. Symbolic Computation, 1991, 12(6):607-631.

[3]Hoeij M V. Computing parameterizations of rational algebraic curves [C]//Conf. ISSAC’94, Oxford, 1994:187-190.

[4]Kuznetsov E B. Optimal parametrization in numerical construction of curve [J]. Journal of the Franklin Institute, 2007, 344(5): 658-671.

[5]Sonia P D, Sendra J R, Sonia L R, et al. Approximate parametrization of plane algebraic curves by linear systems of curves [J]. Computer Aided Geometric Design, 2010, 27(2): 212-231.

[6]Sonia P D, Sendra J, Sendra J R. Parametrization of approximate algebraic curves by lines [J]. Theoretical Computer Ccience, 2004, 315(2): 627-650.

[7]Hartmann E. Numerical parameterization of curves and surfaces [J]. Computer Aided Geometric Design,2000, 17(3): 251-266.

[8]白鴻武, 葉正麟, 王樹勛, 等. Bézier曲線的重新參數(shù)化[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2007,19(12): 1576-1579.

[9]郭鳳華. 參數(shù)曲線的最優(yōu)參數(shù)化[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2007, 19(4): 464-467.

[10]Farouki R T. Optimal parameterizations [J]. Computer Aided Geometric Design, 1997, 14(2): 153-16.