刘振华 杨静

摘 要：在曲线重新参数化过程中，选择合适的参数方程可以使重新参数化的曲线具有良好的几何性质。通过利用分段M？bius变换逼近最优重新参数变换的方法，设计计算曲线重新参数化的Maple软件包。实验表明，使用该软件包计算曲线的重新参数化，比原参数曲线具有更优良的作图性质，具体表现为当作图点数相同时，重新参数化后的曲线比原曲线更光滑。

关键词：参数曲线;重新参数化;参数方程;分段M？bius变换;Maple软件包

DOI：10. 11907/rjdk. 182926 开放科学（资源服务）标识码（OSID）：

中图分类号：TP319文献标识码：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 引言

曲线和曲面，特别是参数曲线和参数曲面，是计算机辅助几何设计中最基本的研究对象。

参数曲线和曲面在几何作图、几何造型、机械制造、数控加工、计算机图形学等方面应用非常广泛。参数曲线和曲面的表示有两种方式，即隐式表示和参数表示，相关研究问题主要包括参数曲线和曲面的参数化、隐式化以及重新参数化等。对于参数化和隐式化的问题，国内外学者已经取得一系列成果[1-4]。本文主要關注参数曲线的重新参数化问题。

对于给定的曲线或曲面，其参数化表示可能有多种不同形式。在给定评价标准下具有良好性质的参数化称为“好”的参数化。重新参数化问题指将给定的参数方程转化为另一种具有较好性质的参数方程。评价参数化优劣标准主要分为两类：一类是从代数的角度，涉及的重新参数化问题包括正则重新参数化、多项式重新参数化、正规重新参数化、代数最优重新参数化，从代数角度出发的重新参数化结果常用于代数计算、几何推理等问题[5-6];另一类从几何角度涉及的问题主要包括弧长参数化和弧角参数化，该类参数化问题往往更关注参数化的几何性质，可以用于几何作图和数控机床等问题，对提高计算机辅助几何设计的质量或研究参数曲线曲面的几何性质有重要意义。弧长参数化是以弧长为参数的矢量函数，其中弧长称为自然参数，因此曲线方程又被称为自然参数方程。利用弧长参数化绘制曲线时，如果参数均匀取值，则绘制的曲线段弧长是等长的。Gerald Farin、Rida Farouki、Bert Jüttler等著名学者[7-9]对弧长重新参数化问题进行了深入研究，取得了一系列重要研究成果。弧角重新参数化问题首先由Patterson等在文献[10]中提出，又称为曲率自适应参数化。在弧角参数化中，参数步长随着曲率变化动态改变，但步长与曲率的乘积（即角速度）恒定。弧角参数化具有良好的作图性质，具体表现为：当追踪曲线时，在曲率变化大的地方，线速度较慢;反之，线速度较快。即利用弧角参数化作图时，点的分布由局部曲率决定。因而在作图点数目相同的情况下，弧角参数化往往能够生成质量更高的图形;杨静等[11-13]对弧角参数化的问题进行了系统研究，提出了一系列较为实用的计算弧角重新参数化算法，并实现了一个用于计算平面曲线弧角参数化的初级版本的软件包ImUp[14]。此外，弧长和弧角重新参数化理论模型还被推广到计算任意曲线均匀拟速度重新参数化的情形[15]。

本文以拟速度重新参数化的算法框架为理论基础，在ImUp的基础上开发了一个能够计算曲线、由多种重新参数化表示的软件包——ImUp+。与早期版本相比，该软件包功能更加完善、适用性更广、计算效率更高， 不仅可以计算平面参数曲线的重新参数化，还可用于计算空间曲线的重新参数化。此外，该软件还可以针对不同的优化标准计算得到多种不同的最优参数表示。

1 均匀拟速度重新参数化算法框架

1.1 参数曲线拟速度均匀度

设[p∈Pk]为由[？p（t）]定义的任意[Ck]连续的参数方程， 其中[t]为参数， 而[θ]为[Pk]上非负几何不变量，则[p]在时刻[t]关于[θ]的拟速度定义为：

1.2 均匀拟速度重新参数化算法

由定义1可知，[uθ，p1]。当[uθ，p=1]时，称[p]为均匀拟速度参数化。均匀拟速度参数化具备良好的几何性质，在作图中点的分布可以随着几何不变量[θ]的变化而变化。重新参数化的目标是当[uθ，p<1]时，寻找[p]的重新参数化[q]，使得[uθ，q=1]，即寻找[0，1]上的参数变换[r]，使得[uθ，p°r=1]。对任意有理曲线[p]，使得[uθ，p°r=1]的参数变换[r]总是存在，这样的[r]称为均匀拟速度参数变换，记为[rθ，p]。可以证明[rθ，p]满足[（rθ，p）-1=1λθ，p0tλθ，p（γ）dγ]，但是这样构造的[rθ，p]往往不是有理函数，即[p°rθ，p]往往不是有理参数表示。因此考虑均匀拟速度参数化的有理近似。该问题等价于寻找[rθ，p]的有理近似[r]，使得[uθ，p°r≈1]。有理近似的方法通常可分为两类：一类是利用次数较高的光滑有理函数逼近，如Weierstrass 逼近;另一类是采用分段的低次有理函数逼近，如分段M？bius变换。本文采用第二类方法构造不同情形下均匀拟速度参数化的有理近似，即均匀拟速度参数变换的有理近似。

由定义可知[C1]分段M？bius变换由参数[T、S、α]的取值唯一决定。因此，计算均匀拟速度参数变换的最优分段M？bius变换近似等价于寻找一组最优参数值[T*、S*、α*]，使得[p°mT*，S*，α*]具有最大的角速度均匀度。ImUp+软件包可以求解如下问题：①当给定分段数[N]时，如何计算参数曲线[p]的最优[C0]分段M？bius变换;②当给定分段数[N]时，如何计算参数曲线[p]的最优[C1]分段M？bius变换;③给定改进因子[δ>1]（一般取接近于[1]的数）时，如何计算在参数曲线[p]的近似最优[C1]分段M？bius变换。

首先考虑当分段数[N]预先给定的情形。此时根据[m]的连续性，[T]、[S]和[α]的最优值可以通过以下方式确定。

（1）若[m]为[C0]连续，则[T]的最优值可以通过求解[Φθ，p=k=0N-1Mθ，k]在一组线性约束[0=t0

若分段数未预先给定，则可以根据拟速度函数的单调性确定分段数，即将[0，1]划分为若干子区间，使在各个子区间上拟速度函数单调，并由此求得各个子区间上[αi]的最优值。具体算法如下：①令[tθ，0=0]，[tθ，N=1]，[tθ，i？（1][i

从而得到在该子区间上的一个加细划分，并计算出相应[S]和[α]（近似）最优值。

2 软件包设计与实现

本文主要工作是设计并实现一个计算曲线均匀拟速度重新参数化的Maple软件包 ImUp+。本部分主要对实现过程中的一些技术问题进行讨论。

2.1 数据结构

如上所述，在重新参数化算法中，本文采用分段M？bius变换逼近均匀拟速度参数变换。作为重新参数化算法的核心概念，分段M？bius变换的表示可以在很大程度上影响算法效率。由定义2可知，分段M？bius变换是由参数[T]、[S]和[α]决定的。因此在ImUp+中，采用如下数据结构表示一个分段M？bius变换：

与分段有理线性函数表示相比，这种数据结构表示形式简单，并且可以直接提取计算所需的参数序列。由于这些参数在计算时被频繁使用，直接提取参数值能够有效降低计算量，从而节省计算时间。

2.2 ImUp+软件包体系架构

ImUp+软件包主要包含4个模块：基本函数模块、M？bius变换模块、重新参数化模块及作图模块，其中M？bius变换是核心模块。图[1]为ImUp+软件包体系架构。

在基本函数模块中，本文提供3个基本函数，其名称和功能分别为：①Composition：计算[p]在M？bius变换[m]下的重新参数化[p°m];②QuasiSpeed：计算參数表示[p]及其重新参数化[p°m]的拟速度;③Uniformity：计算参数表示[p]及其重新参数化[p°m]的拟速度均匀度。

在M？bius变换模块中，根据具体计算要求选择相应重新参数化算法，首先计算得到最优或近似最优的分段M？bius变换，然后利用重新参数化模块构造基于该变换的重新参数化，最后通过作图模块绘制重新参数化后的曲线图形。

2.3 相关技术问题及解决方案

在均匀拟速度的重新参数化算法框架中，最主要的计算主要是积分运算和非线性优化问题求解。为提高算法计算效率，本文采用数值方法计算在给定区间上某给定函数的积分。

在计算[C0]或[C1]拟速度重新参数化时，一个主要步骤是求解参数序列[T]（[C0]的情形）或[T]和[S]（[C1]的情形）的最优值。这是一个典型非线性优化问题。注意到其约束为线性约束，因此考虑采用经典Zoutendijk可行方向法计算其局部最优解。但是本文非线性优化问题中可行域为开集，而Zoutendijk方法中要求可行域为闭集，如果直接调用Zentendijk可行方向法，则在可行域的边界目标函数值将趋于[+∞]，从而在计算时发生内存溢出。因此需要修正Zoutendijk方法。本文采用的修正策略是将Zoutendijk方法中的一维搜索替换为基于枚举法的搜索。

Zoutendijk方法的另一個问题是需要多次计算目标函数关于其自变量的偏导数。由于重新参数化算法涉及的目标函数高度非线性依赖于自变量，而Maple并未提供计算此类函数对其所含自变量的偏导数函数，因此需要针对本文目标函数给出其偏导数的显式表达。

在[C1]近似最优均匀拟速度重新参数化算法中，为了对区间[0，1]进行加细划分，需要在区间[[ti，ti+1]]上求解方程的全部实解。

3 ImUp+函数库

本部分对ImUp+软件包提供的函数及其用法作简要介绍，其中[p]为有理参数曲线，可以为平面曲线或空间曲线。

4 示例与实验

4.1 算例测试

图2是在Maple环境下调用ImUp+计算参数曲线拟速度、拟速度均匀度和重新参数化的示例（以角速度为例，即取[c=2]）。

参数序列m[1]和m[2]分别表示空间参数曲线[p]的[C0]和[C1]分段最优M？bius变换，其中分段数为2;参数序列m[3]表示空间参数曲线[p]的[C1]分段近似最优M？bius变换，由结果可知其分段数为8。C0OptimalReparameterization（[p]，[2]，[2]）返回的结果是空间参数曲线[p]的[C0]最优重新参数化。从图2可以看出，由优化的分段M？bius变换构造的重新参数化其拟速度均匀度均显著高于原参数曲线的拟速度均匀度。

4.2 实验结果

本文在Maple 17中通过大量参数曲线在个人电脑上对该软件包进行测试，测试环境如下：处理器为Intel（R） Core（TM） i7-7500U CPU @2.70GHz 2.90GHz，内存为8GB。本节测试算例分别来自文献[16]以及由Maple随机生成、具有确定次数的空间参数曲线。

表1为分段数相同时[C0]和[C1]最优均匀拟速度重新参数化的计算结果，其中[p]表示原曲线的参数方程，[d]表示参数方程次数，[up]表示参数方程拟速度均匀度，[N]表示重新参数化分段数，[up°m]表示参数曲线[p]经由M？bius变化m重新参数化之后曲线的拟速度均匀度，[t]表示重新参数化算法运行时间。从表中可以看出，与原参数方程相比，[C0]和[C1]最优重新参数化均具有较高的拟速度均匀度。可见，优化的分段M？bius变换可以有效提高参数曲线的拟速度均匀度。而当分段数相同时，[C0]分段M？bius变换可以更显著地提升拟速度均匀度，这是因为在[C0]分段M？bius变换可以优化的参数较[C1]分段M？bius变换更多。此外，[C0]和[C1]最优重新参数化对拟速度均匀度的提升效果在一定程度上取决于给定的分段数[N]，该分段数可以用[C1]近似最优重新参数化选取[T]的策略确定。

5 结语

本文主要展示了一个用于计算曲线重新参数化的软件包ImUp+，介绍了其算法框架、功能与特点，阐述了在实现过程中技术问题的解决方案，最后对软件包性能进行了测试。ImUp+软件包能够处理的曲线需要满足一定条件，即拟速度函数在区间 [0，1]没有零点。当拟速度函数在[0，1]上存在零点时，需根据问题特点设计专门的算法计算曲线重新参数化，这是下一步研究内容。

参考文献：

[1] 厉玉蓉，李丹. 有理参数曲线的最优参数化[J]. 计算机辅助设计与图形学学报，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] 陈发来. 曲面隐式化新进展[J]. 中国科学技术大学学报， 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] 李超，王源昌，孙锐. 最优控制问题参数化研究——基于勒让德正交多项式逼近[J]. 数学的实践与认识，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] 吳文俊. 数学机械化[M]. 北京：科学出版社，2003.

（责任编辑：江 艳）