一個計(jì)算曲線重新參數(shù)化的軟件包—ImUp+

劉振華 楊靜

摘 要：在曲線重新參數(shù)化過程中，選擇合適的參數(shù)方程可以使重新參數(shù)化的曲線具有良好的幾何性質(zhì)。通過利用分段M？bius變換逼近最優(yōu)重新參數(shù)變換的方法，設(shè)計(jì)計(jì)算曲線重新參數(shù)化的Maple軟件包。實(shí)驗(yàn)表明，使用該軟件包計(jì)算曲線的重新參數(shù)化，比原參數(shù)曲線具有更優(yōu)良的作圖性質(zhì)，具體表現(xiàn)為當(dāng)作圖點(diǎn)數(shù)相同時，重新參數(shù)化后的曲線比原曲線更光滑。

關(guān)鍵詞：參數(shù)曲線;重新參數(shù)化;參數(shù)方程;分段M？bius變換;Maple軟件包

DOI：10. 11907/rjdk. 182926 開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

中圖分類號：TP319文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2019）009-0102-06

ImUp+： A Software Package for Computing the Reparameterization of Curves

LIU Zhen-hua1，YANG Jing1，2

（1. SMS International， Guangxi University for Nationalities;

2. Guangxi Key Laboratory for Hybrid Computation and IC Design， Nanning 530006， China）

Abstract： Reparameterization of a parametric curve is to compute an appropriate parametrization from the given one such that the new parameterization has better geometric properties. The main idea is to use the piecewise M？bius transformation to approximate the optimal parametric transformation. In this paper， a Maple software package named ImUp+ is designed and implemented for reparameterizing a given parametric curve. Experiments show that the obtained reparameterization has a better behavior when used for plotting. In particular， when the number of points is fixed， the plotting generated by the reparameterization computed from the software package is smoother than the original one.

Key Words： parametric curves;reparameterization;parametrization; piecewise M？bius transformation; Maple software package

0 引言

曲線和曲面，特別是參數(shù)曲線和參數(shù)曲面，是計(jì)算機(jī)輔助幾何設(shè)計(jì)中最基本的研究對象。

參數(shù)曲線和曲面在幾何作圖、幾何造型、機(jī)械制造、數(shù)控加工、計(jì)算機(jī)圖形學(xué)等方面應(yīng)用非常廣泛。參數(shù)曲線和曲面的表示有兩種方式，即隱式表示和參數(shù)表示，相關(guān)研究問題主要包括參數(shù)曲線和曲面的參數(shù)化、隱式化以及重新參數(shù)化等。對于參數(shù)化和隱式化的問題，國內(nèi)外學(xué)者已經(jīng)取得一系列成果[1-4]。本文主要關(guān)注參數(shù)曲線的重新參數(shù)化問題。

對于給定的曲線或曲面，其參數(shù)化表示可能有多種不同形式。在給定評價(jià)標(biāo)準(zhǔn)下具有良好性質(zhì)的參數(shù)化稱為“好”的參數(shù)化。重新參數(shù)化問題指將給定的參數(shù)方程轉(zhuǎn)化為另一種具有較好性質(zhì)的參數(shù)方程。評價(jià)參數(shù)化優(yōu)劣標(biāo)準(zhǔn)主要分為兩類：一類是從代數(shù)的角度，涉及的重新參數(shù)化問題包括正則重新參數(shù)化、多項(xiàng)式重新參數(shù)化、正規(guī)重新參數(shù)化、代數(shù)最優(yōu)重新參數(shù)化，從代數(shù)角度出發(fā)的重新參數(shù)化結(jié)果常用于代數(shù)計(jì)算、幾何推理等問題[5-6];另一類從幾何角度涉及的問題主要包括弧長參數(shù)化和弧角參數(shù)化，該類參數(shù)化問題往往更關(guān)注參數(shù)化的幾何性質(zhì)，可以用于幾何作圖和數(shù)控機(jī)床等問題，對提高計(jì)算機(jī)輔助幾何設(shè)計(jì)的質(zhì)量或研究參數(shù)曲線曲面的幾何性質(zhì)有重要意義。弧長參數(shù)化是以弧長為參數(shù)的矢量函數(shù)，其中弧長稱為自然參數(shù)，因此曲線方程又被稱為自然參數(shù)方程。利用弧長參數(shù)化繪制曲線時，如果參數(shù)均勻取值，則繪制的曲線段弧長是等長的。Gerald Farin、Rida Farouki、Bert Jüttler等著名學(xué)者[7-9]對弧長重新參數(shù)化問題進(jìn)行了深入研究，取得了一系列重要研究成果。弧角重新參數(shù)化問題首先由Patterson等在文獻(xiàn)[10]中提出，又稱為曲率自適應(yīng)參數(shù)化。在弧角參數(shù)化中，參數(shù)步長隨著曲率變化動態(tài)改變，但步長與曲率的乘積（即角速度）恒定。弧角參數(shù)化具有良好的作圖性質(zhì)，具體表現(xiàn)為：當(dāng)追蹤曲線時，在曲率變化大的地方，線速度較慢;反之，線速度較快。即利用弧角參數(shù)化作圖時，點(diǎn)的分布由局部曲率決定。因而在作圖點(diǎn)數(shù)目相同的情況下，弧角參數(shù)化往往能夠生成質(zhì)量更高的圖形;楊靜等[11-13]對弧角參數(shù)化的問題進(jìn)行了系統(tǒng)研究，提出了一系列較為實(shí)用的計(jì)算弧角重新參數(shù)化算法，并實(shí)現(xiàn)了一個用于計(jì)算平面曲線弧角參數(shù)化的初級版本的軟件包ImUp[14]。此外，弧長和弧角重新參數(shù)化理論模型還被推廣到計(jì)算任意曲線均勻擬速度重新參數(shù)化的情形[15]。

本文以擬速度重新參數(shù)化的算法框架為理論基礎(chǔ)，在ImUp的基礎(chǔ)上開發(fā)了一個能夠計(jì)算曲線、由多種重新參數(shù)化表示的軟件包——ImUp+。與早期版本相比，該軟件包功能更加完善、適用性更廣、計(jì)算效率更高， 不僅可以計(jì)算平面參數(shù)曲線的重新參數(shù)化，還可用于計(jì)算空間曲線的重新參數(shù)化。此外，該軟件還可以針對不同的優(yōu)化標(biāo)準(zhǔn)計(jì)算得到多種不同的最優(yōu)參數(shù)表示。

1 均勻擬速度重新參數(shù)化算法框架

1.1 參數(shù)曲線擬速度均勻度

設(shè)[p∈Pk]為由[？p（t）]定義的任意[Ck]連續(xù)的參數(shù)方程， 其中[t]為參數(shù)， 而[θ]為[Pk]上非負(fù)幾何不變量，則[p]在時刻[t]關(guān)于[θ]的擬速度定義為：

1.2 均勻擬速度重新參數(shù)化算法

由定義1可知，[uθ，p1]。當(dāng)[uθ，p=1]時，稱[p]為均勻擬速度參數(shù)化。均勻擬速度參數(shù)化具備良好的幾何性質(zhì)，在作圖中點(diǎn)的分布可以隨著幾何不變量[θ]的變化而變化。重新參數(shù)化的目標(biāo)是當(dāng)[uθ，p<1]時，尋找[p]的重新參數(shù)化[q]，使得[uθ，q=1]，即尋找[0，1]上的參數(shù)變換[r]，使得[uθ，p°r=1]。對任意有理曲線[p]，使得[uθ，p°r=1]的參數(shù)變換[r]總是存在，這樣的[r]稱為均勻擬速度參數(shù)變換，記為[rθ，p]。可以證明[rθ，p]滿足[（rθ，p）-1=1λθ，p0tλθ，p（γ）dγ]，但是這樣構(gòu)造的[rθ，p]往往不是有理函數(shù)，即[p°rθ，p]往往不是有理參數(shù)表示。因此考慮均勻擬速度參數(shù)化的有理近似。該問題等價(jià)于尋找[rθ，p]的有理近似[r]，使得[uθ，p°r≈1]。有理近似的方法通常可分為兩類：一類是利用次數(shù)較高的光滑有理函數(shù)逼近，如Weierstrass 逼近;另一類是采用分段的低次有理函數(shù)逼近，如分段M？bius變換。本文采用第二類方法構(gòu)造不同情形下均勻擬速度參數(shù)化的有理近似，即均勻擬速度參數(shù)變換的有理近似。

由定義可知[C1]分段M？bius變換由參數(shù)[T、S、α]的取值唯一決定。因此，計(jì)算均勻擬速度參數(shù)變換的最優(yōu)分段M？bius變換近似等價(jià)于尋找一組最優(yōu)參數(shù)值[T*、S*、α*]，使得[p°mT*，S*，α*]具有最大的角速度均勻度。ImUp+軟件包可以求解如下問題：①當(dāng)給定分段數(shù)[N]時，如何計(jì)算參數(shù)曲線[p]的最優(yōu)[C0]分段M？bius變換;②當(dāng)給定分段數(shù)[N]時，如何計(jì)算參數(shù)曲線[p]的最優(yōu)[C1]分段M？bius變換;③給定改進(jìn)因子[δ>1]（一般取接近于[1]的數(shù)）時，如何計(jì)算在參數(shù)曲線[p]的近似最優(yōu)[C1]分段M？bius變換。

首先考慮當(dāng)分段數(shù)[N]預(yù)先給定的情形。此時根據(jù)[m]的連續(xù)性，[T]、[S]和[α]的最優(yōu)值可以通過以下方式確定。

（1）若[m]為[C0]連續(xù)，則[T]的最優(yōu)值可以通過求解[Φθ，p=k=0N-1Mθ，k]在一組線性約束[0=t0

若分段數(shù)未預(yù)先給定，則可以根據(jù)擬速度函數(shù)的單調(diào)性確定分段數(shù)，即將[0，1]劃分為若干子區(qū)間，使在各個子區(qū)間上擬速度函數(shù)單調(diào)，并由此求得各個子區(qū)間上[αi]的最優(yōu)值。具體算法如下：①令[tθ，0=0]，[tθ，N=1]，[tθ，i？（1][i

從而得到在該子區(qū)間上的一個加細(xì)劃分，并計(jì)算出相應(yīng)[S]和[α]（近似）最優(yōu)值。

2 軟件包設(shè)計(jì)與實(shí)現(xiàn)

本文主要工作是設(shè)計(jì)并實(shí)現(xiàn)一個計(jì)算曲線均勻擬速度重新參數(shù)化的Maple軟件包 ImUp+。本部分主要對實(shí)現(xiàn)過程中的一些技術(shù)問題進(jìn)行討論。

2.1 數(shù)據(jù)結(jié)構(gòu)

如上所述，在重新參數(shù)化算法中，本文采用分段M？bius變換逼近均勻擬速度參數(shù)變換。作為重新參數(shù)化算法的核心概念，分段M？bius變換的表示可以在很大程度上影響算法效率。由定義2可知，分段M？bius變換是由參數(shù)[T]、[S]和[α]決定的。因此在ImUp+中，采用如下數(shù)據(jù)結(jié)構(gòu)表示一個分段M？bius變換：

與分段有理線性函數(shù)表示相比，這種數(shù)據(jù)結(jié)構(gòu)表示形式簡單，并且可以直接提取計(jì)算所需的參數(shù)序列。由于這些參數(shù)在計(jì)算時被頻繁使用，直接提取參數(shù)值能夠有效降低計(jì)算量，從而節(jié)省計(jì)算時間。

2.2 ImUp+軟件包體系架構(gòu)

ImUp+軟件包主要包含4個模塊：基本函數(shù)模塊、M？bius變換模塊、重新參數(shù)化模塊及作圖模塊，其中M？bius變換是核心模塊。圖[1]為ImUp+軟件包體系架構(gòu)。

在基本函數(shù)模塊中，本文提供3個基本函數(shù)，其名稱和功能分別為：①Composition：計(jì)算[p]在M？bius變換[m]下的重新參數(shù)化[p°m];②QuasiSpeed：計(jì)算參數(shù)表示[p]及其重新參數(shù)化[p°m]的擬速度;③Uniformity：計(jì)算參數(shù)表示[p]及其重新參數(shù)化[p°m]的擬速度均勻度。

在M？bius變換模塊中，根據(jù)具體計(jì)算要求選擇相應(yīng)重新參數(shù)化算法，首先計(jì)算得到最優(yōu)或近似最優(yōu)的分段M？bius變換，然后利用重新參數(shù)化模塊構(gòu)造基于該變換的重新參數(shù)化，最后通過作圖模塊繪制重新參數(shù)化后的曲線圖形。

2.3 相關(guān)技術(shù)問題及解決方案

在均勻擬速度的重新參數(shù)化算法框架中，最主要的計(jì)算主要是積分運(yùn)算和非線性優(yōu)化問題求解。為提高算法計(jì)算效率，本文采用數(shù)值方法計(jì)算在給定區(qū)間上某給定函數(shù)的積分。

在計(jì)算[C0]或[C1]擬速度重新參數(shù)化時，一個主要步驟是求解參數(shù)序列[T]（[C0]的情形）或[T]和[S]（[C1]的情形）的最優(yōu)值。這是一個典型非線性優(yōu)化問題。注意到其約束為線性約束，因此考慮采用經(jīng)典Zoutendijk可行方向法計(jì)算其局部最優(yōu)解。但是本文非線性優(yōu)化問題中可行域?yàn)殚_集，而Zoutendijk方法中要求可行域?yàn)殚]集，如果直接調(diào)用Zentendijk可行方向法，則在可行域的邊界目標(biāo)函數(shù)值將趨于[+∞]，從而在計(jì)算時發(fā)生內(nèi)存溢出。因此需要修正Zoutendijk方法。本文采用的修正策略是將Zoutendijk方法中的一維搜索替換為基于枚舉法的搜索。

Zoutendijk方法的另一個問題是需要多次計(jì)算目標(biāo)函數(shù)關(guān)于其自變量的偏導(dǎo)數(shù)。由于重新參數(shù)化算法涉及的目標(biāo)函數(shù)高度非線性依賴于自變量，而Maple并未提供計(jì)算此類函數(shù)對其所含自變量的偏導(dǎo)數(shù)函數(shù)，因此需要針對本文目標(biāo)函數(shù)給出其偏導(dǎo)數(shù)的顯式表達(dá)。

在[C1]近似最優(yōu)均勻擬速度重新參數(shù)化算法中，為了對區(qū)間[0，1]進(jìn)行加細(xì)劃分，需要在區(qū)間[[ti，ti+1]]上求解方程的全部實(shí)解。

3 ImUp+函數(shù)庫

本部分對ImUp+軟件包提供的函數(shù)及其用法作簡要介紹，其中[p]為有理參數(shù)曲線，可以為平面曲線或空間曲線。

4 示例與實(shí)驗(yàn)

4.1 算例測試

圖2是在Maple環(huán)境下調(diào)用ImUp+計(jì)算參數(shù)曲線擬速度、擬速度均勻度和重新參數(shù)化的示例（以角速度為例，即取[c=2]）。

參數(shù)序列m[1]和m[2]分別表示空間參數(shù)曲線[p]的[C0]和[C1]分段最優(yōu)M？bius變換，其中分段數(shù)為2;參數(shù)序列m[3]表示空間參數(shù)曲線[p]的[C1]分段近似最優(yōu)M？bius變換，由結(jié)果可知其分段數(shù)為8。C0OptimalReparameterization（[p]，[2]，[2]）返回的結(jié)果是空間參數(shù)曲線[p]的[C0]最優(yōu)重新參數(shù)化。從圖2可以看出，由優(yōu)化的分段M？bius變換構(gòu)造的重新參數(shù)化其擬速度均勻度均顯著高于原參數(shù)曲線的擬速度均勻度。

4.2 實(shí)驗(yàn)結(jié)果

本文在Maple 17中通過大量參數(shù)曲線在個人電腦上對該軟件包進(jìn)行測試，測試環(huán)境如下：處理器為Intel（R） Core（TM） i7-7500U CPU @2.70GHz 2.90GHz，內(nèi)存為8GB。本節(jié)測試算例分別來自文獻(xiàn)[16]以及由Maple隨機(jī)生成、具有確定次數(shù)的空間參數(shù)曲線。

表1為分段數(shù)相同時[C0]和[C1]最優(yōu)均勻擬速度重新參數(shù)化的計(jì)算結(jié)果，其中[p]表示原曲線的參數(shù)方程，[d]表示參數(shù)方程次數(shù)，[up]表示參數(shù)方程擬速度均勻度，[N]表示重新參數(shù)化分段數(shù)，[up°m]表示參數(shù)曲線[p]經(jīng)由M？bius變化m重新參數(shù)化之后曲線的擬速度均勻度，[t]表示重新參數(shù)化算法運(yùn)行時間。從表中可以看出，與原參數(shù)方程相比，[C0]和[C1]最優(yōu)重新參數(shù)化均具有較高的擬速度均勻度。可見，優(yōu)化的分段M？bius變換可以有效提高參數(shù)曲線的擬速度均勻度。而當(dāng)分段數(shù)相同時，[C0]分段M？bius變換可以更顯著地提升擬速度均勻度，這是因?yàn)樵赱C0]分段M？bius變換可以優(yōu)化的參數(shù)較[C1]分段M？bius變換更多。此外，[C0]和[C1]最優(yōu)重新參數(shù)化對擬速度均勻度的提升效果在一定程度上取決于給定的分段數(shù)[N]，該分段數(shù)可以用[C1]近似最優(yōu)重新參數(shù)化選取[T]的策略確定。

5 結(jié)語

本文主要展示了一個用于計(jì)算曲線重新參數(shù)化的軟件包ImUp+，介紹了其算法框架、功能與特點(diǎn)，闡述了在實(shí)現(xiàn)過程中技術(shù)問題的解決方案，最后對軟件包性能進(jìn)行了測試。ImUp+軟件包能夠處理的曲線需要滿足一定條件，即擬速度函數(shù)在區(qū)間 [0，1]沒有零點(diǎn)。當(dāng)擬速度函數(shù)在[0，1]上存在零點(diǎn)時，需根據(jù)問題特點(diǎn)設(shè)計(jì)專門的算法計(jì)算曲線重新參數(shù)化，這是下一步研究內(nèi)容。

參考文獻(xiàn)：

[1] 厲玉蓉，李丹. 有理參數(shù)曲線的最優(yōu)參數(shù)化[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2015，10（2）：1988-1992.

[2] RUEDA S L， SENDRA J， RAFAEL S J. Rational Hausdorff divisors： a new approach to the approximate parametrization of curves[J]. Journal of Computational and Applied Mathematics，2014，263：445-465.

[3] 陳發(fā)來. 曲面隱式化新進(jìn)展[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報(bào)， 2014， 44（5）：345-361.

[4] JIA X H， SHI X R， CHEN F L. Survey on the theory and applications of μ -bases for rational curves and surfaces[J]. Journal of Computational and Applied Mathematics， 2018， 329： 2-23.

[5] 李超，王源昌，孫銳. 最優(yōu)控制問題參數(shù)化研究——基于勒讓德正交多項(xiàng)式逼近[J]. 數(shù)學(xué)的實(shí)踐與認(rèn)識，2014， 44（4）：251-260.

[6] SHEN L Y，PéREZ D S. Numerical proper reparametrization of parametric plane curves[J]. Journal of Computational and Applied Mathematics， 2015，1（277）：138-161.

[7] FARIN G. Rational quadratic circles are parameterized by chord length[J]. Computer Aided Geometric Design， 2006， 23（9）： 722-724.

[8] JüTTLER B. A vegetarian approach to optimal parameterizations[J]. Computer Aided Geometric Design， 1997，14（9）： 887-890.

[9] Lü W. Curves with chord length parameterization[J]. Computer Aided Geometric Design， 2009， 26（3）： 342-350.

[10] PATTERSON R，BAJAJ C. Curvature adjusted parameterization of curves[R]. USA： Purdue University， Computer Science Technical Report， CSD-TR-907， 1989.

[11] YANG J， WANG D， HONG H. Improving angular speed uniformity by optimal C0 piecewise reparameterization[C]. International Workshop on Computer Algebra in Scientific Computing， 2012： 349-360.

[12] YANG J， WANG D， HONG H. Improving angular speed uniformity by reparameterization[J]. Computer Aided Geometric Design，2013，30（7）： 636-652.

[13] YANG J， WANG D， HONG H. Improving angular speed uniformity by C1 piecewise reparameterization[C]. International Workshop on Automated Deduction in Geometry， 2013： 33-47.

[14] YANG J， WANG D， HONG H. ImUp： a Maple package for uniformity-improved reparameterization of plane curves[C]. International Workshop on Asian Symposium on Computer Mathematics， 2014： 437-451.

[15] HONG H， WANG D， YANG J. A framework for improving uniformity of parameterizations of curves[J]. Science China Information Sciences， 2013， 56（10）： 1-22.

[16] 吳文俊. 數(shù)學(xué)機(jī)械化[M]. 北京：科學(xué)出版社，2003.

（責(zé)任編輯：江 艷）