一个计算曲线重新参数化的软件包—ImUp+

方案

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

在计算[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.

（责任编辑：江 艳）

推荐访问:软件包 曲线 参数 计算 ImUp