曲线重合判定及多项式求根问题的重新参数化方法研究

摘要

曲线的重合检测及多项式的求根问题是计算机辅助几何设计(CAGD)与计算机图形学(CG)领域中的两个基本问题，有着许多应用，如碰撞检测，曲线曲面求交运算、中轴线计算及点投影等。
　　本论文主要针对Bézier曲线的重合判定及多项式的求根两个问题，研究了基于重新参数化的方法，主要包括如下两点：
　　(1)提出了两条任意次数Bézier曲线的重合判定方法。
　　研究了两条任意次数Bézier曲线的重合条件。重合判定问题的难点包括：(1)完全重合情形，有些曲线的次数可以经过重新参数化后降低的，这种情况下现有基于原始控制多边形的方法将失效；(2)部分重合情形，需要计算对应的重合参数区间。本文给出了将可重新参数化曲线转化为不可重新参数化曲线的方法，将原始的曲线重合判定问题转化为两个控制多边形的重合判定问题，显著地提高了判断方法的稳定性和准确率。同时重新给出了部分重合情形对应的参数区间的显式公式，使得计算更为简便。
　　(2)提出了单变量多项式求根问题的重根判定与处理方法。
　　当给定多项式可以重新参数化时，即它可以被转化为更低次数的多项式，从而可降低对应方程的次数及计算复杂度。当多项式本身不可重新参数化时，我们提出了基于R3空间的三次裁剪方法，并在裁剪过程中给出了重根的快速判定与处理方法。通过增加重根判定后，可以获取更高的逼近阶，从而在降低计算复杂度的同时也可以提高迭代计算的收敛速度。数值实例也说明了本文方法具有更好的逼近效果和计算效率。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 计算机辅助几何设计中曲线曲面的发展

1.2 Bézier曲线的定义及其性质[1,12]

1.3 重新参数化方法及其研究进展[1,2]

1.4 本文主要工作及其组织结构

第2章 两条任意次数Bézier曲线的重合条件研究

2.1 相关工作及概述

2.2 两条Bézier曲线的重合条件

2.3 检测曲线可以重新参数化的情形

2.4 小结与展望

第3章 多项式方程区间内重根的快速判定和裁剪方法

3.1 多项式求根问题的研究现状

3.2 基于R3空间逼近的三次裁剪方法

3.3 更多的实例与讨论

3.4 小结与展望

第4章 更多的讨论及其应用

4.1 图形图象检索及相似性检测的应用

4.2 多项式求根问题及其在CAGD/CG中的应用

4.3 小结

第5章 总结与展望

5.1 总结

5.2 展望

致谢

参考文献

附录