平面二次代數曲線的最優參數化

厲玉蓉， 胡芳剛

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

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

當t∈(0,1)時，表示圓在第1象限的部分，但是，這個有理參數化并不是圓在第1象限的最優參數化結果。

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

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

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

1 本文算法

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

1.1 最優參數化

1.2 算法描述

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

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

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

定理 1 對于一段圓弧，橢圓或雙曲線上的具有對稱性質部分的有理參數化，用本文算法得到的就是按1.1節中評判標準的最優結果。

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

證畢。

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

2 實例分析

2.1 實例 1

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

圖1 1/4圓弧的參數化對比效果圖

2.2 實例 2

用傳統有理參數化方程，即

圖2 橢圓弧的參數化對比效果

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

3 結 論

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

[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曲線的重新參數化[J]. 計算機輔助設計與圖形學學報, 2007,19(12): 1576-1579.

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

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