浙江大学硕士论文模板_4198.pdf

分类号 单位代码 密 级 学 号 21006094 硕士学位论文 中文论文题目中文论文题目 多项式求根的多项式求根的 Hybrid 裁剪算法研究裁剪算法研究 英文论文题目 英文论文题目 Study on Hybrid clipping method for solving polynomial roots 申请人姓名 袁 泉 指导教师 刘利刚教授 专业名称 应用数学 专业学位领域 计算机辅助几何设计 所在学院 数学系 论文提交日期论文提交日期 年年 月月 日日 多项式求根的多项式求根的 Hybrid 裁剪算法研究裁剪算法研究 论文作者签名论文作者签名 指导教师签名指导教师签名 论文评阅人 1 评阅人 2 评阅人 3 评阅人 4 评阅人 5 答辩委员会主席 委员 1 委员 2 委员 3 委员 4 委员 5 答辩日期 Study on Hybrid clipping method for solving polynomial roots Author s signature Supervisor s signature Thesis reviewer 1 Thesis reviewer 2 Thesis reviewer 3 Thesis reviewer 4 Thesis reviewer 5 Chair Committee of oral defence Committeeman 1 Committeeman 2 Committeeman 3 Committeeman 4 Committeeman 5 Date of oral defence 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发 表或撰写过的研究成果 也不包含为获得 浙江大学浙江大学 或其他教育机构的学位或 证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文作者签名 签字日期 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解 浙江大学浙江大学 有权保留并向国家有关部门或机构 送交本论文的复印件和磁盘 允许论文被查阅和借阅 本人授权 浙江大学浙江大学 可 以将学位论文的全部或部分内容编入有关数据库进行检索和传播 可以采用影印 缩印或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 导师签名 签字日期 年 月 日 签字日期 年 月 日 浙江大学硕士学位论文 Abstract iv 摘要摘要 随着计算机技术的飞速发展 计算机图形学 图像处理方面需要存储和计算 的数据量越来越大 高效 快速 简便的数据处理算法也越来越被需求 针对目前这种问题 本文提出了用于多项式求根的三次 Hybrid 裁剪方法 这 是一种算法简单 易于编程实现 在计算重根时快速 高效的新方法 该方法将 任意一条 n 阶 n 3 B zier 曲线等效于一条三次 Hybrid 曲线 该 Hybrid 曲线有一 个移动控制顶点 而其余控制顶点固定 通过比较求出离坐标轴最近和最远的移 动控制顶点 和其余固定控制顶点一起可以得到两条三次 B zier 曲线 这两条 B zier 曲线完全包围住原曲线 通过这两条曲线可以求出一个包含所求根的区间 将原曲线离散化仅保留所求得的区间内的部分 发重复上述过程 反复进行迭代 计算 直到得到的区间长度小于给定允许误差值 针对 Hybrid 裁剪方法 本文继 续推广出四次 Hybrid 裁剪方法 本文通过数值试验证明了提出的三次 Hybrid 裁 剪方法和四次 Hybrid 裁剪方法用于多项式求根时都能得出正确的结果 本文将已有的二次 Hybrid 裁剪方法和本文提出的三次 Hybrid 裁剪方法作数 值试验对比 可以看出在计算多项式重根时 三次 Hybrid 裁剪方法明显要好于二 次 Hybrid 裁剪方法 本文并将 Hybrid 裁剪方法同多项式裁剪方法做了详细的数 值试验比较 虽然试验结果显示 Hybrid 裁剪方法并不占优势 但是在算法逻辑 编程实现的简便性和占用存储空间等方面 Hybrid 裁剪方法明显都要好于多项式 裁剪方法 关键词 关键词 Hybrid 裁剪 多项式裁剪 多项式求根 B zier 曲线 Hybrid 曲线 浙江大学硕士学位论文 Abstract v Abstract With the rapid development of computer technology the storage capacity and amount of data calculation needed in computer graphics and image processing are lager and lager Efficient fast and simple data processing algorithm is highly needed In response to this situation this paper proposes a method of cubic Hybrid clipping for solving polynomial roots It s a new method which has simple algorithm and easily to be programmed especially quick and efficient in solving the double roots of polynomials This method needs to take several steps First it changes a degree n n 3 B zier curve to a cubic Hybrid curve which is equivalent to the original curve The cubic Hybrid curve has a moving control point and three fixed points Find the point which is the farthest away from the coordinate axis and the one nearest to the coordinate axis among the moving control points Using these two points we can get two degree four B zier curves with other fixed control points Then the two new B zier curves can envelop the original curve To compute the roots of these two four order curves we get an interval which contains the root of the original curve Discrete the original curve and reserve the part that contained by the interval Repeat this process by iteration until the length of the interval is smaller than a given value This paper even proposes a quartic Hybrid clipping bases on the methods of Hybrid clipping By doing numerical experiments this paper proves that we can get correct roots with cubic Hybrid clipping and quartic Hybrid clipping The quadratic Hybrid clipping is compared with our cubic Hybrid clipping in this paper Compared with quadratic Hybrid clipping we find that cubic Hybrid clipping is better in solving the double roots of polynomials Hybrid clipping is compared with polynomial clipping in detail in this paper by doing numerical experiments Although the experimental result shows that Hybrid Clipping is not better than polynomial clipping it is much simpler in the logic algorithm to implement by programming and the storage space needed is much smaller than polynomial clipping Key Words Hybrid clipping polynomial clipping root finding B zier curve Hybrid curve 浙江大学硕士学位论文 目录 I 目录目录 摘要 iv Abstract v 第 1 章 绪论 1 1 1 问题引入 1 1 2 相关工作 1 1 3 本文工作 3 1 4 本文章节安排 3 第 2 章 预备知识 4 2 1 Bernstein 基表示的 B zier 曲线 4 2 2 Hybrid 曲线 4 2 3 幂基与 Bernstein 基的相互转化 4 2 4 卡丹公式 5 2 5 费拉里公式 5 2 6 B zier 凸包裁剪方法和多项式裁剪方法 7 2 7 二次 Hybrid 裁剪方法 8 2 8 本章小结 8 第 3 章 高次 Hybrid 裁剪方法 9 3 1 将 B zier 曲线等价为三次 Hybrid 曲线 9 3 2 三次 Hybrid 裁剪方法 11 3 3 关于三次 Hybrid 裁剪方法的控制顶点设定的讨论 13 3 4 三次 Hybrid 裁剪方法的求根算法 17 3 5 三次 Hybrid 裁剪方法的数值试验 18 3 6 二次 Hybrid 裁剪与三次 Hybrid 裁剪方法的数值试验比较 20 3 7 将 B zier 曲线等价为四次 Hybrid 曲线 23 3 8 四次 Hybrid 裁剪方法 25 3 9 四次 Hybrid 裁剪方法的数值试验 25 3 10 本章小结 26 第 4 章 Hybrid 裁剪方法与多项式裁剪方法的比较 27 4 1 算法比较 27 4 2 数值试验比较 27 4 3 本章小结 30 第 5 章 总结和展望 31 参考文献参考文献 32 致谢致谢 34 浙江大学硕士学位论文 第 1 章 绪论 1 第第1章章 绪论绪论 1 1 问题引入问题引入 近年来 随着计算机科学技术的不断进步 计算机图形学 计算机图像处理 方面需要处理的数据量和计算量也越来越大 在由分段有理参数曲面表示的三维 模型建模 图像处理和可视化自由曲面等领域对多项式求根有了更多要求 高效 稳定的多项式求根算法显得越来越重要 例如 在寻找一条曲线或曲面上离给定 点最近的点这个问题上 归根到底也还是多项式求根问题 在各种各样的几何问题 上 比如曲面与曲面求交 中轴线或者平分轴 凸包的计算等 归根也还是分段代数曲线 在这种情况下 有效的分析和 表示这些曲线的方法是很重要的 在这些问题上寻求多项式的根同样是很重 要的 多项式求根可以被用来去确定那些重要或者是适当的点以此来追踪曲线 同样 在曲面与曲线求交 通过光线追踪来进行曲面渲染 碰撞检测 等问题上都要用到多项式求根 随着计算量的增加 高效 稳定的多项式求根算 法显得迫切需要 1 2 相关工作相关工作 多项式求根问题是一个古老的经典问题 7 从一元一次方程一直到一元四次 方程 我们都可以找到固定的求根公式来进行求解 对于更高次的一元方程的求 值问题 Abel 于 1824 年给了我们答案 一般的五次或者更高次的一元多项式方 程没有解析根 即方程的根不能通过对多项式系数进行有限次加 减 乘 除和 根号运算得到 因此 对于一般的含五次以上的一元方程 只能使用数值方法求解 即用迭代方法求出一个收敛区间 通过反复进行迭代运算 最终得到包含所求根 在内的长度小于给定值的区间 关于多项式求根的数值计算方法 首先很容易让人想到的就是牛顿迭代法 Newton s method 6 又称为牛顿 拉夫逊方法 Newton Raphson method 它是牛 顿在 17 世纪提出的一种在实数域和复数域上近似求解方程的方法 牛顿迭代法 是求方程根的重要方法之一 它利用在有效区间的端点取值异号来进行迭代以得 到更精确的有效区间 Sederberg 等提出了一种称为 B zier 凸包裁剪的方法来求多项式的根 10 这种 方法利用 B zier 曲线及其控制顶点的凸包性来确定包含根的有效区间 结合 B zier 曲线的离散化方法 该方法可以快速地缩小包含根的区间 并保证算法的 稳定性 我们利用图 1 1 说明了该种方法的求根方式 11 12 13 14 15 16 10 13 19 20 21 22 17 18 浙江大学硕士学位论文 第 1 章 绪论 2 图 1 1 B zier 凸包裁剪的求根方法 Barto 等提出了二次多项式裁剪的方法来计算多项式的根 1 该方法通 过降阶的方法用一个二次多项式逼近原来的多项式 然后通过计算得到两个 二次多项式来夹逼原来的多项式 由这两个夹逼多项式所求得的根 再结合 B zier 曲线的离散化方法 通过反复迭代计算就可求得包含根的长度很小的 区间 如图 1 2 显示了该种方法的求根方式 图 1 2 多项式裁剪的求根方法 刘等提出了三次多项式裁剪方法 这是对二次多项式方法的推广和改 进 该方法同样利用降阶逼近 用三次多项式来逼近原来的多项式 然后通 过计算得到两个三次多项式来夹逼原来的多项式 由这两个夹逼多项式所求 的根 再结合 B zier 曲线的离散化方法 通过反复迭代可求得包含根的长度 很小的区间 该方法在求重根时的收敛速度明显要快于二次多项式裁剪方法 North 提出了二次 Hybrid 裁剪的方法 该方法将高次多项式转换二次 Hybrid 曲线的形式 其中中间的控制顶点为移动控制顶点 通过计算找出二 次 Hybrid 曲线离坐标轴最近和最远控制顶点 和首末控制顶点组成两条二次 B zier 曲线 利用这两条二次 B zier 曲线夹逼原来曲线求得的根 再结合 B zier 曲线的离散化方法 通过反复迭代可以计算出包含根的有效区间 如 3 2 浙江大学硕士学位论文 第 1 章 绪论 3 图 1 3 显示了该种方法 图 1 3 二次 Hybrid 裁剪的求根方法 1 3 本文工作本文工作 本文工作的想法是从由二次多项式裁剪方法推广到三次多项式裁剪方法的 做法得到的 因为二次 Hybrid 方法在求多项式的重根时 计算速度还有待提高 本文设法将二次 Hybrid 裁剪方法推广到三次 Hybrid 裁剪方法 并由二次 Hybrid 裁剪和三次 Hybrid 裁剪方法继续推广得到四次 Hybrid 裁剪方法 本文将三次 Hybrid 裁剪方法和四次 Hybrid 裁剪方法做了数值试验来检测这两种方法的正确 性 将二次 Hybrid 裁剪方法和三次 Hybrid 裁剪方法作了试验比较 最后又将 Hybrid 裁剪方法和已有的多项式裁剪方法做了数值试验比较 并从理论上对多项 式裁剪方法和 Hybrid 裁剪方法的算法作了比较 1 4 本文章节安排本文章节安排 本文第二章介绍了一下本文的预备知识 Bernstein 基表示的 B zier 曲线 Hybrid 曲线 幂基与 Bernstein 基的转化 一元三次方程 一元四次方程的求根公 式等 详细地介绍了 B zier 凸包裁剪方法和二次 三次多项式裁剪方法 最后详 细介绍了二次 Hybrid 裁剪方法 第三章详细介绍了三次 Hybrid 裁剪方法 并对三次 Hybrid 裁剪方法的控制 顶点设置作了详细的讨论 将三次 Hybrid 裁剪方法的求根算法列出来 列出了三 次 Hybrid 裁剪方法的数值试验结果 将三次 Hybrid 裁剪方法和二次 Hybrid 裁剪 方法做了数值试验比较 最后介绍了四次 Hybrid 裁剪方法 并列出了四次 Hybrid 裁剪方法的数值试验 第四章主要将 Hybrid 裁剪方法和多项式裁剪方法分别在算法和数值试验上 作了详细比较 第五章则是对全文提纲挈领的总结和对以后工作的展望 浙江大学硕士学位论文 第 2 章预备知识 4 第第2章章 预备知识预备知识 2 1 Bernstein 基表示的基表示的 B zier 曲线曲线 通常 一条 n 阶 B zier 曲线 4 可以表示为如下形式 0 n n ii i p tBtp t 2 1 其中 in i n i n n tt B t i 为 n 维 Bernstein 基的一般形式 i p为 B zier 曲线的控制顶点坐标 其中0 1 in 通常情况下取 0 1 1 nnin i ii n BtB tttt i 0 1 2 2 Hybrid 曲线曲线 对于一条已知的 m 次有理 B zier 曲线 4 00 01 0 mm mm kkkkkk kk R tP ttBtRBtt 我们称与之等价的曲线 0 01 rp r prprprpr p iii ii r HtR tBt HBt Htt 2 2 为 r p 次的 Hybrid 曲线 这里 00 mm r pmr pm kkkkk kk HtBtMBt 称为曲线 r p Ht的移动控制顶点 2 3 幂基与幂基与 Bernstein 基的相互转化基的相互转化 幂基 1 n tt 形式表示的 Ferguson 曲线与 Bernstein 基形式表示的 B zier 曲 线的相互转化 4 可以通过下面的公式进行 0101 1 1 01 1 nnnTnFT nnijnnn B tB tB tpppttbppp 2 3 0101 1 1 01 1 nTnnnBT nnijnnn ttpppB tB tB tfppp 2 4 浙江大学硕士学位论文 第 2 章预备知识 5 其中 0 1 F ijij ij bni ij ij 0 B ij ij fnjn ij iji 因此对于后面给出的因式乘积形式的多项式 可以先将其展开为幂基形式 然后转化成为 Bernstein 基形式 再进行本文中提到的算法操作 2 4 卡丹公式卡丹公式 对于如何求一元三次方程的根 则使用卡丹公式 8 来求解 对于给定的用 Bernstein 基表示有效区间为 的三次多项式 其 Bernstein 基为 4 44 ii ii n tt B t 三次多项式可表示为 3333 00112233 g tB tdB tdB tdB td 则由卡丹公式可以得到它的三个根 1 iii t 1 2 3 i 其中 33 1 223 vva 2 33 2 223 vva 2 33 3 223 vva 这里 2 3 i e 为复数 222 0203121312 3 ud dd dd dd dddD 22 0120130231230203 222333 12121312 33336 33622 vd d dd d dd d dd d dd dd d d dd dd dddD 232232234 030212130123 2 3 4346 4vud dd dd dd dd d d dD 012 363 adddD 0123 33Ddddd 三个根当中 1 t为实数 当0 1 t和 2 t为实数 当0 时 1 t和 2 t为共轭复数 2 5 费拉里公式费拉里公式 对于一元四次方程的根的求根问题 则可以利用费拉里提出一元四次方程求 浙江大学硕士学位论文 第 2 章预备知识 6 根公式 来解决 对于给定的用 Bernstein 基表示有效区间为 的四次次多项式 44444 0011223344 g tB tdB tdB tdB tdB td 则由费拉里公式可以得出它的四个根分别为 1 iii t 1 2 3 4 i 我们首先设 001 Ddd 1012 2Dddd 20123 33Ddddd 301234 464Dddddd 2 132 48 DD DD 22342264 912244 ED Dd DDD D DD D D 23 032123 32 23 FD DDD D D 2 3ADE 9BDEF 2 3CEDF 2 4BAC 1 当0DEF 时 原方程有四重根 2 1234 3 D D 2 当0 0 0 0ABCDEF 时 原方程有一个三重根 2 1 33 4 DF DD D 2 234 33 3 4 DF DD D 3 当 0 D0E F 时 原方程有两个重根 2 12 3 4 4 DD D 2 34 3 4 4 DD D 4 当 2 40 0 0 0BACABC 时 原方程有一个重根 2 1 3 4 2 4 DDB ABA D 2 2 3 4 2 4 DDB ABA D 2 34 3 4 4 DDB A D 5 当 2 40BAC 时 原方程有四个单根 3 23 arccos 2 ADB A 1 2cos 3 3 DA M 9 浙江大学硕士学位论文 第 2 章预备知识 7 2 2cos 32 3 3 DA M 3 2cos 32 3 3 DA M 2123 1 3 4 4 DMMM D 2123 2 3 4 4 DMMM D 2123 3 3 4 4 DMMM D 2123 4 3 4 4 DMMM D 6 当 2 40BAC 时 原方程有四个单根 2 1 3 4 2 YADBBAC 2 2 3 4 2 YADBBAC 33 12 1 2 6 DYY Z 33 12 2 3 6 YY Z 33 12 3 DYY Z 22 1112 2 WZZZ 22 2112 2 WZZZ 21 1 3 42 4 DZW D 21 2 3 42 4 DZW D 22 3 3 42 4 DZW i D 22 4 3 42 4 DZW i D 2 6 B zier 凸包裁剪方法和凸包裁剪方法和多项式裁剪方法多项式裁剪方法 绪论中已经提到了 B zier 凸包裁剪方法和多项式裁剪方法 我们在这里以求 单根为例 将对这两种方法做更详细的说明 B zier 凸包裁剪方法 10 利用了 B zier 曲线的控制顶点所组成的凸多边形 将 原曲线包围在其中 可以很容易的计算出凸多边形和坐标轴的两个交点 很显然 我们所要求的根也在以这两个交点为端点的区间内 将以这两个交点为端点的区 间设为有效区间 离散化原曲线仅保留有效区间内的曲线部分 将有效区间内的 曲线作为新的 B zier 曲线重复上述操作 直到求得的区间长度小于某值为止 B zier 凸包裁剪方法如图 1 1 所示 多项式裁剪方法 1 2 则将 B zier 凸包裁剪方法中的凸多边形改为低阶多项式 曲线来包围原曲线 多项式裁剪方法利用 Bernstein 基的对偶基将原 n 阶 B zier 曲线降阶为低阶多项式曲线 然后再利用 Bernstein 基的对偶基将该低阶多项式曲 线升阶为 n 阶 B zier 曲线 求出这两条 n 阶 B zier 曲线的最大误差 将低阶多 项式曲线左右平移 得到一个带状区域包围原 B zier 曲线 且该带状区域的边 浙江大学硕士学位论文 第 2 章预备知识 8 界是两条同阶的低阶多项式曲线 求出这两条低阶多项式曲线与坐标轴的交点 则所要求的根就在以这两个交点为端点的区间内 将以这两个交点为端点的区间 设为有效区间 离散化原曲线仅保留有效区间内的曲线部分 将有效区间内的 B zier 曲线作为新的 B zier 曲线重复上述操作 直到求得的区间长度小于某值为 止 多项式裁剪方法如图 1 2 所示 多项式裁剪方法中将原曲线降阶为低阶曲线 当降为二阶曲线时就是二次多 项式裁剪方法 而当降阶为三阶曲线时就是三次多项式裁剪方法 2 7 二二次次 Hybrid 裁剪裁剪方法方法 二次 Hybrid 裁剪方法 3 是这样的 对于任意一条给定的给 n n 2 阶 B zier 曲线 0 n n ii i P tB t P 可以将其看作一条二次 Hybrid 曲线 P t 则 P t的控制顶 点 00 PP 2 n PP 移动控制顶点 2 2 11 0 n n ii i P tBt P 为一条 n 2 阶 B zier 曲线 01 1 1 2 1 1 2 1 1 in i niin Pn nPi iP P ini 选取 1 i P中坐标轴最近和最远的点分别记为 1 min P和 1 max P 可以得到两条 2 阶 B zier 曲线 222 10011 min22 P tB t PB t PB t P 222 20011 max22 P tB t PB t PB t P 分别计算出 1 P t和 2 P t与坐标轴的交点 则所要求的根就在以这两个交点为端点 的区间内 将以这两个交点为端点的区间设为有效区间 离散化原曲线仅保留有 效区间内的曲线部分 将有效区间内的 B zier 曲线作为新的 B zier 曲线重复上述 操作 直到求得的区间长度小于某值为止 二次 Hybrid 裁剪方法如图 1 3 所示 对于二次 Hybrid 方法 我们自然会问能否像多项式裁剪方法一样由二阶推广 到三阶 甚至是更高阶 下一章将给出肯定的答案 2 8 本章本章小结小结 本章先对本文的预备知识作了简单的介绍 介绍了 Bernstein 基表示的 B zier 曲线 Hybrid 曲线 幂基与 Bernstein 基的转化 一元三次方程 一元四次方程的 求根公式 接着介绍了 B zier 凸包裁剪方法和二次 三次多项式裁剪方法 最后 又详细介绍了二次 Hybrid 裁剪方法 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 9 第第3章章 高高次次 Hybrid 裁剪裁剪方法方法 3 1 将将 B zier 曲线等价为三次曲线等价为三次 Hybrid 曲线曲线 三次多项式裁剪方法是由二次多项式裁剪方法推广得来 而且三次多项式裁 剪方法比二次多项式裁剪方法在求重根时效果要好 这是因为所用阶数越高的多 项式来夹逼原曲线时会夹逼的更紧更接近 收敛的速度也会相应的提高 很自然 使人想到能否将二次 Hybrid 裁剪方法推广到三次 Hybrid 裁剪方法 定理定理1 对于任意一条给定的阶数n 3 控制顶点为 0 1 i P in 的B zier曲线P t 存 在 一 条 等 价 的 三 次 Hybrid 曲 线 P t P t控 制 顶 点 为 00 PP 101 3 3Pn PnP 3 n PP 和一个移动控制顶点 2 P t 移动控制顶点本身是一 条 n 2 阶的 B zier 曲线 其控制顶点为 001 2 2 3 iiiiin i iiii a Pbn PnPc Pd P P abcd 3 1 其中 1 2 i an i n iin 1 i bi n i in 1 2 i cn nn 2 1 i diii 2 3 in 证明 对于任意一条m d 阶 B zier 曲面 Q s t 它的对角线 P t Q t t 是一条 m d 阶 B zier 曲线 其控制顶点为 md ijkj k m d j k i i i PQ 设定 m 3 则 0 1 2 3 j 0 1 1 2 2 3 3 j kiiii 所以我们可 以得到 33333 00 111 1222 2333 3 ddddd iiiiiiiiii PQQQQ 3 2 假设 n d 3 阶对角线 P t 的控制顶点已知 我们可以设 0 0i QP 3 3in QP 将 i 1 代入 3 2 可得 1 001 3 3Qn PnP 我们可以设 1 001 3 3Qn PnP 则可得 3333 010122 23 3 3 33 nnnnn iiiiiiin PPn PnPQP 333 2 201013 3 2 1 3 3 nnnn iiiiiin n i QPPn PnPP 001 1 2 1 3 3 1 3 1 in ninini nii Pn PnP i inii ini 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 10 1 2 1 2 3 1 3 1 in n nniii PP i inii ini 我们设 1 2 i an i n iin 1 i bi n i in 1 2 i cn nn 2 1 i diii 则3 1 iiii abcdi ini 其中 2 3 in 由此可 以得到如下式子 001 2 2 3 iiiiin i iiii a Pbn PnPc Pd P Q abcd 因为我们已经设定了 0 0i QP 3 3in QP 和 1 101 3 3Qn PnP 这样 我们 令 s t 来求得 Q s t的对角线为 3223 01 02 3 1 3 1 3 1 3 n n PnP Q t ttPtttt P tt P 3 3 其中 2 P t为 n 3 阶 B zier 曲线 它的控制顶点为 2 22 2 ii PQ 2 3 in 这是一条三次 Hybrid 的 B zier 曲线 以 0 P 01 3 3n PnP 和 n P固定控制顶 点 以 2 P t为移动控制顶点 证毕 从定理 1 的证明过程我们可以看出 可将 B zier 曲线 P t 看作对应的 B zier 曲面 Q s t 的对角线 如图 3 1 所示 利用 Q s t 和其控制顶点可以得到一条 Hybrid 曲线 P t 而 P t就是等价于 Q s t 的对角线 P t Q t t 因此我们完全可以把 B zier 曲线 P t 看作 Q s t 的对角线 图 3 2 显示了 Hybrid 曲线在移动控制顶点取 值 t 0 05 时的曲线形状 图 3 1 Q s t 覆盖其对角线 P t Q t t 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 11 图 3 2 Hybrid 曲线 P t在其移动控制顶点取值 t 0 05 3 2 三次三次 Hybrid 裁剪方法裁剪方法 通过定理 1 我们很容易可以得到三次 Hybrid 的方法 首先利用定理 1 将 一条在给定区间 0 1 内有效的 n阶 4 n B zier 曲线改写为三次 Hybrid 曲线形式 3 3 0 ii i P tB t P t 3 4 其中 00 P tP 记为 0 P 101 3 3P tn PnP 记为 1 P 3 n P tP 记为 3 P 2 22 2 n n ii i P tBt P 通过 3 1 我们知道 001 2 2 3 iiiiin i iiii a Pbn PnPc Pd P P abcd 其中 1 2 i an i n iin 1 i bi n i in 1 2 i cn nn 2 1 i diii 这里 2 3 in 取离 x 坐标轴 同样取 y 坐标轴亦可 最近和最远的点 2 i Pt分别记为 2 max P和 2 min P 则两条三次 B zier 曲线分别为 3333 1001122 max33 P tB t PB t PB t PB t P 3 5 3333 2001122 min33 P tB t PB t PB t PB t P 3 6 如图 3 4 所示 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 12 图 3 3 一条任意 5 阶 B zier 曲线 图 3 4 原曲线与得到的两条三阶 B zier 曲线 1 P t和 2 P t 图 3 5 1 P t和 2 P t可以得到两个有效根 和 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 13 图 3 6 在 和 两点离散化原 B zier 曲线得到同阶数的 B zier 曲线 1 p t 将 1 P t和 2 P t对应的y坐标值设为0 可以得到两个关于t的一元三次方程 利用前面 2 5 节所给出的三次多项式求根公式 我们可以在 0 1 区间内求得两个 有效解 和 如图 3 5 所示 和 则可以组成有效区间 将 B zier 曲线分别在 和 两点离散化 仅仅保留 区间内的部分作为 B zier 曲线 1 p t 如图 3 6 所示 对区间 内的 B zier 曲线 1 p t采取和原曲线相同的做法 进行迭代计算 下去 知道求得的有效区间长度小于给定的误差范围 为止 图 3 3 至图 3 6 正好 显示了三次 Hybrid 裁剪方法的一个完整的迭代过程 3 3 关于三次关于三次 Hybrid 裁剪方法裁剪方法的的控制顶点设控制顶点设定的定的讨论讨论 对于三次 Hybrid 裁剪方法 为什么一定要设定 1 01 3 3 i Qn PnP 在定 理 1 的证明过程中 我们会发现只要满足 1 001 3 3Qn PnP 可以任意设定 1 i Q 如果将 1 i Q设为移动控制顶点 则 P t将有两个移动控制顶点 这样会有怎 样的效果呢 0 1 2 3in 任意设定 1 i Q 则 2 i Q也将随之改变 因为 2 i Q的取值与 1 i Q有关 33333 2 2200 111 1333 3 2 1 dddd iiiiiiiii d i QPQQQ 随之三次 Hybrid 裁剪方法的算法也将需要改变 1 i Q和 2 i Q都要单独选择离坐标 轴最近和最远的点 不能再像之前所作的那样固定 1 i Q 而仅仅选择离坐标轴最 近和最远的的 2 i Q了 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 14 设想设定 1 01 3 3 i Qni Pni P 1 1 3 3 iii Qn PnP 或者是 1 1 3 3 iii Qni Pni P 这三种情况都满足 1 0 Q 01 3 3n PnP 我们 将该三种方法和原始固定点方法 1 01 3 3 i Qn PnP 进行实验比较 以在有效区间内取值为单根的各阶多项式为例 2 4 3 2 5 4 fttt 2 5 2 3 3 6 3 ftttt 22 6 1 3 5 3 3 f ttttt 3 7 1 4 2 4 6 2 fttttt 223 8 1 2 6 4 4 ftttt 233 9 1 3 6 2 3 ftttt 2223 10 2 5 6 10 10 5 fttttt 36 11 1 10 5 7 5 ftttt 38 12 3 10 5 5 fttt 误差范围为 12 10 我们得到如表格 3 1 所示的数据 其中表格 3 1 中的数据分别 表示运行时间 单位 ms 和迭代次数 将表格 3 1 中的运行时间和迭代次数绘 制出如图 3 3 1 和图 3 3 2 所示结果 其中图 3 7 中 横坐标代表多项式阶数 纵 坐标代表运行所用时间 单位 ms 图 3 8 中横坐标代表多项式阶数 纵坐标代 表运行迭代次数 我们可以看出第一种方法 在多项式求单根的时候在运行时间 和迭代次数上都要要快于另外三种方法 表 3 1 四种控制顶点对各阶多项式求根所用迭代次数和运行时间 多项式阶数 4 5 6 7 8 9 10 11 12 01 3 3 n PnP 0 00966 3 0 004 3 0 005 3 0 0064 3 0 0084 3 0 014936 4 0 023926 5 0 027236 5 0 030205 5 01 3 3 ni Pni P 0 00366 3 0 015 8 0 010 5 0 0326 11 0 0437 12 0 057344 13 0 079754 15 0 087159 14 0 117449 16 1 3 3 ii n PnP 0 00313 3 0 008 5 0 021 9 0 0124 5 0 0157 5 0 024584 6 0 068320 6 0 06789 7 0 06980 9 1 3 3 ii ni Pni P 0 003622 3 0 013 7 0 016 7 0 0261 9 0 0321 9 0 043407 10 0 052766 10 0 067129 11 0 078686 11 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 15 图 3 7 四种控制顶点方法求各阶多项式单根时运行所用时间的比较 图 3 8 四种控制顶点方法求各阶多项式单根时运行所用迭代次数的比较 我们又以在有效区间内取值为重根的各阶多项式为例 2 4 1 3 5 2 fttt 22 5 1 3 3 3 fttt 222 6 1 5 2 4 f tttt 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 16 222 7 1 3 4 8 3 ftttt 2222 8 1 4 6 8 2 ftttt 22222 10 2 3 3 6 9 3 fttttt 误差范围为 12 10 得到如表 3 2 图 3 9 和图 3 10 所示结果 其中表格 3 2 中的数 据分别表示运行时间 单位 ms 和迭代次数 而图 3 9 是由表格 3 2 中各阶多 项式求根时运行时间绘制出来的曲线图 图 3 10 则表示表格 3 3 2 中各阶多项式 求根时的迭代次数的对比的曲线图 其中横坐标代表多项式阶数 纵坐标代表运 行迭代次数 表 3 2 四种控制顶点方法求各阶多项式重根时运行所用时间和迭代次数的比较 多项式阶数 4 5 6 7 8 10 01 3 3 n PnP 0 005061 4 0 006545 4 0 008159 4 0 010017 4 0 012166 4 0 017384 4 01 3 3 ni Pni P 0 015056 10 0 014088 8 0 020280 9 0 025650 9 0 035112 10 0 056889 11 1 3 3 ii n PnP 0 005064 4 0 014053 8 0 020402 9 0 028414 10 0 039677 11 0 057240 11 1 3 3 ii ni Pni P 0 008085 5 0 010246 6 0 017922 8 0 022344 9 0 030942 9 0 045493 9 图 3 9 四种控制顶点方法求各阶多项式重根时运行所用时间的比较 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 17 图 3 10 四种控制顶点方法求各阶多项式重根时运行所用迭代次数的比较 从数值试验结果可以看出 在求重根时 第一种方法无论是在所用运行时间 还是迭代次数上都要明显要好于另外的三种方法 和单根情况下的数值试验结果 相同 而第一种方法正是本文中三次 Hybird 裁剪方法所用的固定控制顶点方法 3 4 三次三次 Hybrid 裁剪方法的求根算法裁剪方法的求根算法 我们可以利用 2 1 3 节中幂基和 Bernstein 基的转换公式 将一般多项式转换 Bernstein 基形式 B zier 曲线 因此这里只将三次 Hybrid 的方法用于求 B zier 曲 线与坐标轴交点的算法叙述如下 输入 自变量在区间 上取值以 01 n ppp为控制顶点的 n 阶 B zier 曲 线 Step1 如果区间 的长度 则执行 step2 否则执行 step12 Step2 利用三次 Hybrid 裁剪方法求出固定控制顶点和移动控制顶点 Step3 取距离 x 轴最近的移动控制顶点记为 max q Step4 取距离 x 轴最远的移动控制顶点记为 min q Step5 M 以固定控制顶点和 max q组成控制顶点 自变量取值范围为 得到一条低阶 B zier 曲线 Step6 m 以固定控制顶点和 min q控成控制顶点 自变量取值范围为 得到一条三阶 B zier 曲线 Step7 如果 M m 围成的带状区域与 t 轴在 无交点 则返回 否则 执行 step8 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 18 Step8 通过计算 M m 与 t 轴交点求出相交区间 1 2 ii il Step9 如果 1 2 1 max 2 ilii 则将曲线p从点 2 离散化为两 段 分别将每段从 step1 重新执行 否则 执行 step10 Step10 对于每个区间 ii 求出对应的由原曲线离散得到的曲线段 i p Step11 对于每段 ii 上的 i p 分别执行 step1 Step12 输出求得的区间 注 在 step2 可以采用三次 Hybrid 裁剪方法 同样可以采用二次 Hybrid 裁剪方 法或者是后面将要讨论到的四次 Hybrid 裁剪方法求得控制顶点 因此在 step5 和 step6 当采用二次 Hybrid 裁剪方法或者是四次 Hybrid 裁剪方法时对应求得的低阶 B zier 曲线为二阶和四阶 在 step8 里求根则利用相应的求根公式 依据三阶多 项式求出根的个数不同 可能求出多个有效区间 三次 Hybrid 裁剪方法最多求出 三个有效区间 而如果采用二次 Hybrid 裁剪方法最多求出两个有效区间 四次 Hybrid 裁剪方法最多求出四个有效区间 为了防止多根和重根的情况 固必须执 行 step9 的判断 同 B zier 凸包裁剪 多项式裁剪类似 三次 Hybrid 裁剪方法在 曲线被离散化到非常短的情况下也可能会产生不包含根的错误区间 3 5 三次三次 Hybrid 裁剪方法的裁剪方法的数值数值试验试验 三次 Hybrid 裁剪方法 作为一种新的多项式求根方法 为了它的正确性 我 们做了数值试验来对其进行检测 文中依次显示了单根 多根情况下各种形状 B zier 曲线的求根结果 曲线为任意选取的但保证其与坐标轴有交点 求根的误 差范围为 8 10 为了检测结果的正确性 我们同时将多项式求根方法求得的结果 一并列出来 将它们进行对比 图 3 11 控制顶点为 1 10 3 7 5 6 6 5 8 2 10 1 13 0 14 2 16 5 的具有 单根的 B zier 曲线 浙江大学硕士学位论文 第 3 章高次 Hybrid 裁剪方法 19 对于图 3 5 1 所示的 B zier 曲线 四种方法所求单根分别为 二次多项式裁剪 0 288731815341418