（计算数学专业论文）利用三次bezier曲线求解几何约束问题算法的改进研究.pdf

中文摘要 中文摘要 计算机辅助设计( c o m p u t e ra i d e dd e s i g n ，简称c a d ) 技术是一种利用计算机 的硬件和软件来进行产品的建模、修改、分析和优化的技术。它广泛的应用在科 研和生活的各个领域中，现在它的应用水平已经成为衡量一个国家科技现代化和 工业现代化水平的重要标志之一。 c a d 技术的发展经历了四次重大的技术创新，变量化技术是第四次技术创 新。几何约束求解是参数化技术和变量化技术的核心，即一旦给定了设计草图的 若干尺寸和拓扑关系约束，系统就可以自动生成相应的设计图，工程设计领域中 很多问题都可归结为几何约束求解。 目前，几何约束求解的方法主要有四种：基于数值的几何约束求解方法，基 于符号的几何约束求解方法，基于规则的几何约束求解方法和基于图论的几何约 束求解方法。 现有的几何约束求解算法主要是针对构造包括点、直线和圆等几何体在内的 几何图形，而在实际的工程设计中涉及的几何图形常常包括三次曲线或更复杂的 曲线。通过增加三次b e z i e r 曲线作为一个新的几何体，可以扩大几何约束求解算 法的作图范围。本文在文献 1 】的基础上给出了三次b e z i e r 曲线与三次b e z i e r 曲线 之间的几何约束的新的定义与代数表达式，并根据新定义的几何约束给出了包含 三次b e z i e r 曲线在内的几何约束求解问题的构造算法，该算法使得几何约束求解 的作图范围得到了进步的扩大。同时也使得作为参数化技术和变量化技术的核 心问题：几何约束求解的研究更有实际意义。 关键词：几何约束求解；几何体；三次b e z i e r 曲线；构造序列；作图范围 黑龙江大学硕士学位论文 a b s t r a c t c o m p u t e ra i d e dd e s i g nt e c h n o l o g yi sak i n do ft e c h n o l o g yt h a tu s eh a r d w a r ea n d s o f t w a r eo fc o m p u t e rt od om o d e l i n g ，m o d i f y , a n a l y z eo ro p t i m i z ew o r k i tw i d e l y a p p l i e st oa l lk i n d so ff i e l do fs c i e n t i f i cr e s e a r c ha n dl i v i n gl i f e ，t h ea p p l i c a t i o nl e v e lo f c a dt e c h n o l o g yh a sa l r e a d yb e c o m eo n eo ft h em o s ti m p o r t a n ts y m b o l st oe s t i m a t e t h es c i e n c ea n d t e c h n o l o g ya n dt h ei n d u s t r ym o d e r n i z a t i o no fac o u n t r y t h ed e v e l o p m e n to fc a dt e c h n o l o g yh a s g o n et h r o u g hf o u rs i g n i f i c a n t t e c h n o l o g yi n n o v a t i o n s ，t h el a s ti n n o v a t i o ni st h ea p p e a r a n c eo fv a r i a b l et e c h n o l o g y g e o m e t r i cc o n s t r a i n ts o l v i n gi st h ec o r eo fp a l a m e t r i ca n dv a r i a t i o n a ld e s i g n , i tm e a n s t h a to n c et h ed i m e n s i o nc o n s t r a i n t sa n dt o p o l o g i c a lc o n s t r a i n t sa l eg i v e n , t h es y s t e m w i l lp r o d u c et h ed e s i g ng r a p ha u t o m a t i c a l l y m a n yp r o b l e m si ne n g i n e e r i n gc a l lb e t r e a t e da sg e o m e t r i cc o n s t r a i n ts o l v i n g a tp r e s e n l a p p r o a c h e s t o g e o m e t r i cc o n s t r a i n ts o l v i n gc o n t a i nn u m e r i c a l a p p r o a c h ，s y m b o l i ca p p r o a c h ，r u l e b a s e da p p r o a c ha n dg r a p h - b a s e da p p r o a c h t h ea l g o r i t h m so fg e o m e t r i cc o n s t r a i n ts o l v i n gm a i n l yc o n s t r u c tg e o m e t r i cg r a p h ， i n c l u d i n gp o i n t s ，l i n e sa n dc i r c l e s b u tg e o m e t r i cg r a p ho f t e ni n c l u d e sc u b i cc u r v eo r m o r ec o m p l i c a t e dc u r v ei np r a c t i c a le n g i n e e r i n g t h et h e s i se x p a n d st h ed r a w i n g s c o p e o fg e o m e t r i cc o n s t r a i n ts o l v i n gb yi n c r e a s i n gc u b i cb e z i e rc u r v ea san e w g e o m e t r i c p r i m i t i v e t h i st h e s i sg i v e st h en e wg e o m e t r i cc o n s t r a i n t sa n dm a t h e m a t i c sd e s c r i p t i o n b e t w e e nc u b i cb e z i e rc u r v e sb a s e dt h er e f e r e n c e 【1 】，a n dg i v e st h en e w a l g o r i t h m a b o u tt h ec o n s t r u c t i o no fg e o m e t r i cc o n s t r a i n ts o l v i n gp r o b l e m sw h i c hc o n t a i n e dc u b i c b e z i e rc u r v e s t h i sa l g o r i t h mf a r t h e re x p a n d st h e d r a w i n gs c o p eo fg e o m e t r i c c o n s t r a i n ts o l v i n g t h e r ei sm o r ep r a c t i c a ls i g n i f i c a n c ef o rt h er e s e a r c ho fg e o m e t r i c c o n s t r a i n ts o l v i n g ，w h i c hi st h ec o r eo f p a r a m e t r i ct e c h n o l o g ya n dv a r i a b l et e c h n o l o g y u a b s t r a c t k e y w o r d s ：g e o m e t r i c c o n s t r a i n ts o l v i n g ；g e o m e t r i cp r i m i t i v e ；c u b i cb e z i e rc u r v e ； c o n s t r u c t i o ns e q u e n c e ；d r a w i n gs c o p e i 1 1 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得墨蕴逛太堂或其他教育机构的 学位或证书而使用过的材料。 学位论文作者签名：谈心 签字日期：叫年月西日 f 学位论文版权使用授权书 本人完全了解墨蕴婆太堂有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权墨蕉堑盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或其他复制手段保存、汇编本 学位论文作者签名：与定d 迫j 导师签名： 签字日期1 年忑月町e t 学位论文作者毕业后去向： 工作单位： 通讯地址： 签字日期：1 钳月汨 电话： 邮编： 第1 章绪论 1 1c a d 的发展历史 第1 章绪论 2 0 世纪4 0 年代中期，在美国诞生了第一台电子计算机，这是2 0 世纪科技领 域的卓越成就之一。随着计算机的出现，1 9 6 3 年，美国麻省理工学院的2 4 岁研究 生i e s u t h e r l a n d 首次提出了计算机辅助设计( c o m p u t e r a i d e dd e s i g n ) 简称c a d 的概念 2 1 ，它是指利用计算机硬件和软件进行的设计活动，包括使用计算机的数 据库、程序库及通讯等技术来完成设计过程的信息检索、分析、计算、综合、修 改及文件编制工作。c a d 技术从出现到现在经历了四次重大的技术创新：第一次 技术创新是2 0 世纪7 0 年代出现的曲面造型技术，这次技术创新改变了以往只能 借助油泥模型来近似表达曲面的落后工作方式，首次实现了以计算机完整描述产 品零件的主要信息。第二次技术创新是2 0 世纪8 0 年代初期的实体造型技术，这 项技术能够精确表述零部件的全部属性，例如重心、质量和惯性矩等，在理论上 有助于统一c a d 、c a e 、c a m 的模型表达，给设计者带来了惊人的方便。第三次 技术创新是出现在2 0 世纪8 0 年代后期的参数化实体造型技术，该技术首次引入 了约束的概念。参数化实体造型技术将一组参数与控制零部件几何图形的一组结 构尺寸序列相对应，赋予不同的参数值时，就可以产生一系列具有相似几何图形 的零部件。参数化实体造型技术的特点是：基于特征的设计、全尺寸约束、全数 据相关、尺寸驱动设计的修改。p t c 公司研制的p r o e n g i n e e r 是第一个采用这 项新技术的参数化软件。第四次技术创新是2 0 世纪9 0 年代后期出现的变量化技 术，1 9 9 7 年s d r c 公司首次推出变量化技术，这是参数化技术的一次飞跃。变量 化技术将整个设计草图当作个完整的系统来考虑，与构造过程的顺序无关，把 草图中的控制尺寸和拓扑关系都用约束来表示，这使得设计初期的草图可以不是 完全定义的，而将没有完全定义的控制尺寸和拓扑关系用变量存储起来，暂时以 当前的绘制尺寸赋值。设计者可以在任何阶段对草图中的任何尺寸和拓扑关系进 行重新定义，同时这种重新定义也不牵涉草图中所有的几何实体的改动。变量化 黑龙江大学硕士学位论文 技术提供的灵活更改模型的方式，有效地支持了c a d 的概念化设计，可以使设计 者的创造力和想象力得到更充分的发挥。 c a d 技术的引入提高了设计的效率和质量，从根本上改变了过去的手工绘图、 发图、凭图纸组织整个生产过程的技术管理方式，将它变为在图形工作站上交互 设计，用数据文件发送产品定义，在统一的数字化产品的模型下进行产品的设计 打样、分析计算、工艺规划、工装备设计、数控加工、质量控制、编印产品维护 手册、组织备件订货供应等等。缩短了产品的研制周期，在整个生产系统中起着 举足轻重的作用。 今天，c a d 技术已经渗透到工程技术和人类生活的几乎所有领域，主要服务 于机械、电子、宇航、建筑、轻纺、管道铺设等产品的总体设计、外形设计、结 构设计、优化设计、运动机构的模型设计、工艺过程设计、数控加工。它涉及计 算机科学、计算数学、计算几何、计算机图形学、数据结构、数据库、数控技术、 软件工程、仿真技术、机器人学、人工智能等新的学科领域。 1 2 智能c a d 的发展历史 c a d 技术发展的好坏，已经成为衡量一个国家工业发展的重要指标，它推动 了几乎一切领域的设计革命。为此，人们已开始研制具有更高性能的新一代的c a d 系统，即智能c a d 系统。 智能c a d 是人工智能和c a d 技术相结合的一门综合性研究领域，其英文名 为i n t e l l i g e n tc a d ，或简写为i c a d 。它将人工智能的理论和技术用于c a d 之中， 使c a d 系统支持设计师在设计过程中的思维，“真正”实现具有创造性的设计过 程，从而把设计自动化引向深入，这是c a d 技术在学术上的一个重要方向。 美国的卡耐基梅隆大学是国际上最早研究智能c a d 的单位，2 0 世纪7 0 年代 中期著名的人工智能学者h a s i m o n 和c a d 学者e a s t m a n 带领一批博士研究生研 究住宅空间的综合。澳大利亚悉尼大学的j s g e r o 教授从研究工程设计优化方法 着手，在2 0 世纪7 0 年代末开始转向设计中的人工智能技术。日本东京大学在智 能c a d 的研究也开展得较早，y o s h i k a w a 教授在1 9 7 7 年首次提出了属性空间的映 第l 覃绪论 射，引入三个公理，并由此从数学上推导出定理，很好地解释了设计过程。2 0 世 纪8 0 年代，英国爱丁堡大学的人工智能系建立一个能支持人做设计的智能c a d 的环境。在国内，浙江大学人工智能研究所是最早开展智能c a d 理论及应用研究 的院所，目前，国内的许多其它的研究机构，如北京航空航天大学、华中理工大 学、清华大学、中国科学院数学与系统研究院等也开始了这方面的研究。 为了实现智能c a d 的智能交互、智能显示和自动数据获取，人们提出了面向 方案形成过程的i c a d 方法。方案的形成过程可以看成是一个约束满足问题，即 所有的设计要求与限制都被看成对变量的约束，而最终的方案则是满足所有约束 条件后的设计。求解的过程则是一个基于约束进行的。这一设计方法被称为基于 约束满足的设计方法。现在智能c a d 的研究中存在着三个前沿问题：第一个前沿 问题是解决方案的形成：第二个前沿问题是围绕着设计对象、设计知识的表达展 开的研究；第三个前沿问题是围绕智能c a d 系统的自动作图功能，即几何约束求 解。 1 3 几何约束求解技术的引入 工程应用中，大多数机械设计都来源于草图和现有的图形。在设计过程中， 用户一开始并不关心图形的精确尺寸，而只是粗略地勾划零件的大致形状，而且， 用户也可能在现有图形的基础上，作细微的改进。尺寸的调整，是非常普遍的， 因为尺寸可以决定零件的几何形状，尺寸的改变可以生产不同的几何图形。传统 的交互作图方法，图形一旦生产就很难进行尺寸的调整。为了弥补传统c a d 系统 的不足，提高设计效率，2 0 世纪8 0 年代后期，l i n 和g o s s a r d 等人提出了参数化 设计【3 ，4 】。参数化设计的基本原理就是系统在设计过程中自动地捕获用户的设计意 图，从而将用户设计中的各个设计对象以及对象之间的关系记录下来，而当用户 修改图纸中尺寸标注和设计参数时，系统能够自动对图纸进行必要的修改使图纸 中反映用户设计意图的设计对象之间关系依旧得以维持。参数化技术首次引入了 约束的概念，它是一种基于约束的设计方法。而后，1 9 9 7 年s d r c 公司又推出了 变量化技术，这是参数化技术的一次飞跃。基于约束的设计是智能c a d 的一个重 黑龙扛大掌坝士字位论文 要标志，基于约束的参数化和变量化设计系统把问题描述与问题求解技术分离成 相互独立的两个部分，使得该类设计方法较其他方法更具有明显的优势，它有以 下的优点： ( 1 ) 用户可以任意方式组合，以任意顺序定义几何约束和工程约束。基于约束 的设计具有统一处理这些约束的能力，并能适合广泛意义上的工程设计。 ( 2 ) 基于约束的设计，能很快地记录设计者的意图，允许多个不同应用领域的 用户完成同一项设计任务。 ( 3 ) 基于约束的设计，能够求解过强约束或约束不足问题，而且允许用户集中 地考虑某一部分的细节设计。 ( 4 ) 基于约束的设计，能全面给出解的过程，便于用户整体考虑。 ( 5 ) 基于约束的设计，具有很好的人机交互功能，能够充分地利用交互特性， 逐步地确定设计过程，给出全部的设计解。 基于约束的参数化和变量化设计系统，它的主要功能包括： ( 1 ) 从几何参数化模型能自动地导出精确的几何模型。它不要求输入精确图形， 只要求输入一个草图，标注一些几何元素的约束，再通过改变约束条件来自动导 出精确的几何模型。 ( 2 ) 通过修改局部参数来达到自动地修改精确的几何模型的目的，大致形状相 似的一系列零件，只需修改一下参数，便可以生成新的零件，这可大大地提高生 产效率。 参数化技术与变量化技术的核心就是几何约束求解，几何约束求解是指在输 入一个草图以后，用户可以随时在需要的时候，以任意的方式任意的顺序重新输 入几何约束，然后由计算机自动导出精确的满足用户要求的几何图形的过程。除 了在机械设计中应用以外，几何约束求解经常出现在计算机视觉、连杆设计、机 器人、分子结构设计等领域 , t s , 6 j 。 1 4 论文的结构 本论文主要分为四个部分： 第l 苹绪论 第l 章绪论简介c a d 和智能c a d 的发展历史，同时引入几何约束求解。 第2 章几何约束求解概述详细给出了几何约束求解的概括性描述和用于几 何约束求解的主要方法。 第3 章利用三次b e z i e r 曲线求解几何约束问题的改进算法介绍了基本概 念，详细叙述了新增加的几何约束及利用新增加的几何约束给出三次b e z i e r 曲线 的构造，并提出了新的求解算法。 第4 章实例分析用两个具体的例子来验证算法的可行性和有效性。 黑龙江大学硕十学位论文 第2 章几何约束求解概述 本章将给出几何约束求解的一些基本概念，几何约束求解的主要方法。 2 1 几何约束求解基本概念 定义2 1 1 几何体：一个几何图形中最基本最具有特征的几何元素，例如二维中的 点、直线、线段、圆、圆弧和三维中的平面、球面、曲面等等。 定义2 1 2 几何约束：两个或多个几何体之间所具有的几何关系，例如点与点之间 的距离，直线与直线之间的角度，直线与圆相切等等。 通常我们将几何约束做如下分类： ( 1 ) 几何形式的几何约束 尺寸约束：一般是由用户显示输入的。通常包括两点之间的距离、直线与直 线之间的角度、点到直线的距离、半径约束和两条平行线之间的距离等等。 拓扑约束：一般是隐含的，是由系统根据草图自动建立的。通常包括水平约 束、竖直约束、两条直线平行和垂直、三点共线、两个角相等、两个圆共心等等。 另外根据几何约束中所涉及的几何体的个数，还可以将几何形式的几何约束 分成如下三类： 一元约束：只涉及到一个几何体的约束，例如线段的长度就是一个一元约束。 二元约束：涉及到两个几何体的约束，大多数的几何约束均属此类。 多元约束：几何约束中涉及到两个以上的几何体，例如a ，b ，c 三点共线、 线段的长度相等，角度相等。 ( 2 ) 代数形式的几何约束 方程约束：指以方程的形式给出的几何约束。例如三角形a b c 的面积等于圆 o 的面积。 不等式约束：有时为了表示点在几何图形中的构造顺序时用到，例如 a b _ c a 表示点a ，b ，c 是以顺时针的顺序构造的。 基于以上的基本概念，可以给出几何约束求解的准确定义。 定义2 1 3 几何约束问题：给定一个几何体的集合o 和一个关于集合o 中的几何 6 第2 章几何约束求解概述 _i ii i 体之间的几何约束的集合c ，则我们将二元组( o ，c ) 称为几何约束问题。有时，也 将几何约束问题称为几何自动作图问题。 下面是一个几何约束问题的例子： 如图2 1 所示，作三角形a b c ，已知线段a b 的长度d ，线段b c 的长度d ：， 线段a b 与线段a c 间的角度是秒。 a c b 图2 1 一个几何约束问题的例子 f i 9 2 1a ne x a m p l eo f g e o m e t r i cc o n s t r a i n ts o l v i n g 几何体的集合o = 点：a ，b ，c ；线段：a b ，b c ，a c 几何约束的集合c = 线段a b 的长度盔：线段b c 的长度攻；线段a b 与线段 a c 问的角度秒 定义2 1 4 几何约束求解：指对于给定的一个几何约束问题( o ，c ) ，根据一定的算 法作出一个或多个几何图形。其中，这个几何图形是由集合o 中的所有的几何体 构成的，并且这些几何体之间要同时满足集合c 中的所有的几何约束。 定义2 1 5 几何约束问题的解：指根据一定的算法作出的由集合o 中的所有的几 何体构成的且满足集合c 中的所有的几何约束的几何图形。 根据几何约束问题的解的个数，我们将几何约束问题分成如下三类： ( 1 ) 完整约束的几何约束问题：几何约束问题有有限个解。 ( 2 ) 欠约束的几何约束问题：几何约束问题有无限个解。 ( 3 ) 过约束的几何约束问题：几何约束问题没有解。 下面，我们从几何约束问题本身所具有的性质出发对几何约束问题进一步分 类。首先介绍两个概念： 黑龙江大学硕七论又 定义2 1 6 几何体的自由度：指要确定这个几何体的位置所需要的独立参数的个 数，我们用d o f ( o ) 来记几何体o 的自由度。例如二维空间中的点的自由度是2 ， 圆的自由度是3 ，线段的自由度是4 。三维空间中点的自由度是3 ，直线的自由度 是4 。 定义2 1 7 几何约束的约束度：指为了描述一个几何约束所需要的代数方程的个 数，我们用d e f ( o ) 来表示几何体o 的约束度。例如点与点之间的距离约束的约束 度是1 ，两直线之间的角度约束的约束度是l ，直线与圆的相切约束的约束度是1 。 由以上的定义，我们称一个几何约束问题( o ，c ) 是： 结构上完整约束的几何约束问题：如果集合o 中的任何一个子集o 。中所包含 的几何体的自由度总和等于集合c 中所有关于子集o ，中几何体的几何约束的约束 度的总和减去3 ( 二维) 或6 ( 三维) ； 结构上欠约束的几何约束问题：如果集合o 中的任何一个子集o ，中所包含的 几何体的自由度总和大于集合c 中所有关于子集o ，中几何体的几何约束的约束度 的总和减去3 ( 二维) 或6 ( 三维) ； 结构上过约束的几何约束问题：如果集合o 中的任何一个子集o 。中所包含的 几何体的自由度总和小于集合c 中所有关于子集o ，中几何体的几何约束的约束度 的总和减去3 ( 二维) 或6 ( 三维) 。 2 2 几何约束求解的主要方法 几何约束求解的方法发展到现在，大致可以分为四类：基于数值计算的几何 约束求解方法，基于符号计算的几何约束求解方法，基于规则的几何约束求解方 法和基于图论的几何约束求解方法。下面我们分别介绍： 2 2 1 基于数值计算的几何约束求解方法 通过建立一个直角坐标系，将所有给定的几何约束转化成一系列表示几何约 束的代数方程，方程中的变量表示几何体的独立参数。这样得到一个非线性代数 方程组，解这个非线性代数方程组得到变量值，即几何体在直角坐标系的坐标， 第2 章几何约束求解概述 i i i i i ii ii 然后就可以构造出相应的几何图形。第一个用数值计算的方法求解几何约束问题 的c a d 系统是i e s u t h e r l n a d 研制的s k e t c h p a d 系纠2 1 。除此之外，还有t h i n g l a b 系统i r l ，j u n o 一2 系统【8 】和m a g r i t t e 系统【9 】等。 目前，常用的基于数值计算的几何约束求解方法有n e w t o n r a p h s o n 方法和同 伦连续法。n e w t o n r a p h s o n 方法【1 川是数值计算中用的最多的一种方法，这种方法 的求解速度快，但是需要一个好的初值。为此，j u l l o 【l l 】提出用草图作为初值的方 法。r l i g h t 和g o s s a r d 提出了一种求逆矩阵的新方法【5 j ，降低对初值的敏感性。 同伦连续法在一定程度上可以弥补n e w t o n - r a p h s o n 方法对初值的选取比较敏感的 不足【1 2 1 5 1 。设取) ：0 是我们所要求的方程组，根据同伦连续法可以找到一个容易 求解的方程组g ( x ) = o ，然后令f ( x ，a ) ：( 1 兄) g ( x 卜兄f ( x ) ，则f ( x ，o ) = g ( x ) ，f ( x ，1 ) - - - f ( x ) 。 设x 。是g ( x ) - o 的一个解，即v ( x 。，o ) = 0 ，在名从o 连续变化到1 的过程中，以x 。为 初值进行迭代，最终可以得到f ( x p o 的解。同伦连续法往往需要很大的计算量， 通常仅限于求解一些小的方程组。 用数值计算的方法求解几何约束问题的优点是速度快，而且能够解一些其他 方法解不了的大的代数方程组，缺点是不能处理欠约束和过约束的几何约束问题， 并且对初值的选取比较敏感。在实际的几何约束求解过程中，当用其他的方法无 效的时候，都用数值计算的方法来求解。 为了弥补基于数值计算的方法求解几何约束问题的不足，中国科学院的高小 山研究员提出一种将代数方程组的求解问题转化成一个优化问题的极小值求解问 题【16 1 ，然后再用拟牛顿法求解这个极小值的方法。文献 1 7 中给出了一个轨迹求 交的数值计算方法。文献 1 8 中还提出了一种将同伦函数与传统迭代法结合起来 的新数值迭代法。文献 1 0 ，1 9 ，2 0 ，2 1 中也给出了一些改进的基于数值计算的 几何约束求解方法。 2 2 2 基于符号计算的几何约束求解方法 当几何约束问题的代数方程组中的方程系数不是确定的数值，而是一个参数 的时候，需要用符号计算中的消元法求解代数方程组，这种方法可以给出由参数 黑龙江大学硕士论文 形式的系数表示的方程组的解析解。 基于符号计算的几何约束求解方法大致有w u r i t t 特征列方法，g r o b n e l 基方 法和结式法。w u r i t t 特征列方法瞄1 是将方程组的零点集分解成一个包含一些容易 求解的简单的代数方程组的零点集的集合。基于理想多项式理论的g r o b n e r 基方法 2 3 , 2 4 1 ，首先将方程组转化成一个同解的三角化方程组，这个方程组可以很容易用 回代的方法求解。著名的b u c h b e r g e r 算法就是采用这种方法求解的。文献 2 5 中 g r o b n e r 基方法被应用在几何约束求解。基于行列式理论的结式、法【2 6 1 ，其基本思想 是利用原有的方程组生成一个以原有的方程组中的变量的系数为变量的方程组， 这个方程组相对于原来的方程组具有某些容易求解的特征。 基于符号计算的几何约束求解方法的优点是可以符号求解，即方程组的变量 的系数可以是一个符号而不是具体的数值，而且可以求出方程组所有的解。另外， 符号计算的方法还可以用来判断几何约束问题是否是完整约束的、欠约束的和过 约束的。缺点是求解的速度比较慢，通常需要消耗大量的计算时间和空间。 2 2 3 基于规则的几何约束求解方法 首先将几何约束用谓词来代表，然后将一系列的重写规则应用于这些谓词， 通过推理，最后将几何约束问题转化成一个可构造的形式 2 7 - 2 9 ，即通过直尺和圆 规将满足几何约束的几何图形构造出来。 全局延拓法【3 0 】是一个典型的基于规则的几何约束求解方法。a h b o r n i n g 是 第一个尝试用这种方法求解几何约束问题的i r l 。全局延拓法以几何约束问题的构 造性描述作为输入，最后输出几何体的具体位置，在确定几何体的位置之前，首 先通过一定的推理规则和一个几何公理集合从几何约束问题本身出发，得到一个 几何信息库，在几何信息库中找到关于这个几何体的所有全局信息，然后去掉一 个几何约束，则会得到这个几何体所在的一条几何轨迹；再去掉另外一个几何约 束，会得到另外一条几何轨迹，通过求这两条轨迹的交点，就可以得到这个几何 体的位置。b e a td b r u d e r l i n 第一个利用推理数据库的方法符号求解几何约束问题 【3 1 1 ，并且在用p r o l o g 程序语言实现算法的同时向m o d u l a 2 程序语言提供了一 第2 章几何约束求解概述 个接口，使得这两个程序语言可以通过一个共同的推理数据库来实现交流。随后 又出现了大量的利用数据库推理的方法进行几何约束求解的算法【3 2 3 7 。k r a m e r 提 出了一个可以处理三维几何约束问题的自由度分析法【3 8 , 3 9 1 ，用于处理由连杆所产 生的几何约束问题。陈立平等人提出了一种以图论、稀疏矩阵和自由度分析等理 论为基础的几何约束满足问题的规约分治算法【4 0 ，4 1 1 ，通过对几何约束系统的最大 分解，大大减少了求解的规模。文献 4 2 中董金祥和葛建新等人提出了一种基于几 何抽象的几何约束求解方法，通过几何抽象来表达约束，并利用约束网的形式， 在层进行几何化简推导和运算，获得解集。文献 4 3 中提出了一种基于数值的几 何约束求解方法和基于规则的几何约束求解方法相结合的方法，文献 4 4 中将图 论的方法与基于规则的方法结合起来以提高速度。 基于规则的几何约束求解方法的优点是可构造性。一旦几何约束问题可以转 化成可构造的形式，就可以很快构造出满足约束的几何图形，而且构造步骤简单 明了，容易被用户理解。缺点是由于推理过程往往要搜索和匹配整个数据库，所 以导致用这种方法求解几何约束问题的速度比较慢而且实现起来也很困难。对于 过约束和欠约束问题，基于规则的方法会以交互式的方式提醒用户发生过约束和 欠约束的地方，同时给出几种可选的解决方案供用户选择，但这要取决于用于推 理的数据库的建立原则。 2 2 4 基于图论的几何约束求解方法 基于图论的几何约束求解方法首先将几何约束问题用一个约束图表示，顶点 代表几何体，边代表几何约束，一个边和两个顶点相连表示这个边代表的几何约 束是与这两个顶点代表的几何体有关的。然后，用图论中的方法分析约束图后产 生一个构造序列，根据所产生的构造序列实际构造出所要求的几何图形。 1 9 9 1 年，o w e n 提出了三角分解法( 4 5 , 4 6 ，将一个几何约束问题的表示图分解成 一系列的三连通子图，这些子图在几何上对应着一个刚体，然后将这些刚体按分 解的相反顺序组合起来，就得到构造序列。h o f f m a n n 和f u d o s 等人在1 9 9 5 年提出 了簇合并方法【4 7 , 4 8 】，该方法给出了将一个几何约束问题分解为可作图子集的算法， 黑龙江大学硕士论文 使基于图论的几何约束求解方法向前推进了一大步。文献 4 9 ， 5 0 中f i t z e r l a n d 和t o d d 提出了一个只考虑垂直和水平距离的基于图论的几何约束求解算法。c h s u 和b e a td b r u d e r l i n 在1 9 9 4 年利用图论的方法来分析几何体的自由度，从而提 出了求解几何约束问题的自由度分析法【5 。孙家广和胡事民等人提出了一种剪 枝一归约算法的几何约束分解策略【5 2 5 4 】。陈立平等人针对欠约束情况下约束求解 规划存在的问题，提出一种几何约束系统有向图优化处理算法【5 5 1 。高小山和蒋鲲 提出了求解几何约束问题的几何变换法【5 6 1 。l a t h e a m 引入s 树算法提出了一个几何 约束求解的连通图算法【5 丌。文献 5 8 中提出了一种新的约束有向图匹配算法。 基于图论的几何约束求解方法的优点是速度快。缺点是这种方法对几何约束 问题中所包含的几何体和几何约束的类型比较敏感，当每增加一种新的几何体或 几何约束时，都要对原有算法作相当大的改动。 2 3 本章小结 本章介绍了几何约束求解的基本概念，详细叙述了几何约束求解的四种主要 方法，并且指出了四种方法的优缺点。 第3 章利用三次b e z i e r 曲线求解几何约束求解问题的改进算法 i| _ii 第3 章利用三次b e z ior 曲线求解几何约束求解问题的 改进算法 本章将首先介绍一些预备知识、三次b e z i e r 曲线的定义和三次b e z i e r 曲线的几 何作图法。详细讨论三次b e z i e r 曲线与三次b e z i e r 曲线之间的几何约束的定义，以 及利用这些新的几何约束来求解包括三次b e z i e r 曲线在内的几何约束求解问题，最 后给出改进的利用三次b e z i e r 曲线求解几何约束问题的新算法。 3 。1 预备知识 本文主要利用几何约束求解四种主要方法中的基于规则的几何约束求解方 法。通过这种方法进行几何约束求解，首先需要将几何体和几何约束表示成谓词 的形式。 下面将介绍谓词的概念、如何用谓词来表示几何体和几何约束，以及与论文 相关的其他概念。 3 1 1 谓词 谓词是对有关个体的陈述，当与一个个体相联系时，它刻画了个体的性质； 当与两个或两个以上个体相联系时，它刻画了个体之间的联系。在谓词逻辑中， 命题是用谓词来表示的，一个谓词可分为谓词名和个体两个部分。个体表示某个 独立存在的事物或者某个抽象的概念，谓词名用于刻画个体的性质、状态或个体 间的关系。 谓词的一般形式为p ( x 1 ，x 2 ，x n ) ，其中p 是谓词名，x l ，x 2 ，x 。是个体。例 如：o n l i n e ( p ，i i ) 表示尸点在直线，l 上，d i s t a n c e ( p ! ，b ，d ) 表示鼻和最两点间 的距离是d 。 3 1 2 基本构造和构造 将下面每一个谓词形式称为一个基本构造。 ( 1 ) p o i n t ( p ) ：在平面上作一个自由点p 。 黑龙大掌硕士论文 ( 2 ) o n ( p ，d ) ：在几何体d 上作一个半自由点p 。 ( 3 ) i n t e r ( p ，q ，0 2 ) ：作几何体q 和0 2 的交点尸。 ( 4 ) l i n e ( a ，b ) ：作过点彳和点b 的直线。 ( 5 ) c i r c l e ( p ，d ) - 作以点p 为圆心以d 为半径的圆。 根据以上的基本构造，还可以得到一些其他的构造： a l i n e ( a ，0 ) - 作过点彳点与直线，成秒角的直线。 p l i n e ( r ，p ，q ) ：构造一条通过点r 且平行于直线l i n e ( p ，q ) 的直线。 p c i r c l e ( d ，p ) ：构造一个以点o 为圆心且通过点尸的圆。 a c i r c l e ( p ，q ，r ，口) ：画一个通过点r 的圆弧，满足么豫9 = 0 。 c o n s t r u c t ( o ，0 l ，0 2 ，q ) ：表示由几何体d l ，0 2 ，o k 构造几何体d ， k 2 ，o 与q ( f - 1 ，七) 的关系有如下几种情形： 点、线：表示点在线上或线过一点。 点、圆：表示点在圆上或圆过一点。 线、线：表示两直线成某个角度。 线、圆：表示线圆相切。 圆、圆：表示圆圆相切。 我们将基本构造和由它得到的其他的构造组合统称为构造。 3 1 3 构造序列 一个有序的集合( c l ，c 2 ，g ) ，称为一个构造序列，如果这个有序集合满足 以下两个条件：( 1 ) 每个c ，代表一个具体的构造，包括基本构造和其他的构造；( 2 ) 假设由构造c 引入的几何体是q ，则构造几何体q 所需的其他的几何体是由 c l ，c f _ l 引入的。 由上面定义的构造序列，图2 1 中三角形的构造序列为： 构造1p o i n t ( a ) 构造2 o n ( i i ，a ) ； 第3 章 利用三次b e z i e r 曲线求解几何约束求解问题的改进算法 构造3 构造4 构造5 构造6 构造7 i n t e r ( b ，o n ( 1 1 ，a ) ，c i r c l e ( a ，d 1 ) ) ； l i n e ( a ，b ) ； i n t e r ( c , a l i n e ( a ，l ，9 ) ，c i r c l e ( a ，d 2 ) ) ； l i n e ( a ，c ) ； l i n e ( b ，c ) ； 3 2 三次b o z ie r 曲线 本节将简要介绍三次b e z i e r 曲线的定义和三次b e z i e r 曲线的几何作图法。 3 2 1 三次b e z ie r 曲线的定义 给定四个顶点v i ( i = o ，l ，2 ，3 ) ，则可以定义一条平面三次b e z i e r 曲线p ( ”) ： 3 p ( z ，) 2 马，翩) v j i - - = 0 = ( 1 一) 3 v o + 3 ( 1 - u ) 2 u v , + 3 ( 1 一u ) u 2 v j + “3 v j ，u o ，1 】( 3 一1 ) 其中岛，似) 为b e r n s t e i n 多项式，色， ) = q ( 1 一甜) 甜，曲线p ( z ，) 通过首、末 顶点v 0 和v 3 ，并且与由四个顶点相连所形成的控制多边形首、末两边相切。 三次b e z i e r 曲线的参数方程形式为： 其中( 五，咒) 是点v 的坐标，i = 0 , 1 ，2 ，3 3 2 2 三次b e z i e r 曲线的几何作图法 甜【0 , 1 】( 3 2 ) 三次b e z i e r 曲线的几何构造称为几何作图法【5 9 1 ，应用作图法，可便捷地确定 三次b e z i e r 曲线上与某给定参数值相对应的点。首先根据给定的参数值甜，在特 征多边形的每一条边上确定某一分割点，使分割后的两线段之比为z ，：( 1 一甜) 。由此， 可得分割点的点矢为： v i l = ( 1 一甜) v i + u v i + l ， f = o ，1 ，2( 3 3 ) y x 沪 + + 儿 、矿 一 0 义 + 叩f = 妻 妒 叫 卜 义 义 + 肌 妒 叫 一 0 0 = = ) ) “ 甜 ( 0 y x 厂11 黑龙江大学硕士论文 i 式中，第二个下标1 表示第一次分割。第一次分割后，得到3 个分割点，由其组 成一个新的多边形，其边数为2 。用相同的方法再对该多边形的各条边进行分割， 得到2 个分割点v 0 ：和v 1 ：，形成另一个新的多边形。按相同的过程分割2 次以后， 仅剩两个顶点v 0 2 和v l ：，对这两个顶点组成的线段再分割一次，得到点v 即为三 次b e z i e r 曲线上与参数 相对应的点，v 舱v 1 ：为曲线在v 0 3 处的切线。几何作图法 如图3 1 所示： 上述三次b e z i e r 曲线的几何构造过程用德卡斯特里奥【删建立的递归公式表 示： 图3 - 1 三次b e z i e r 曲线的作图法 f i 移- 1am e t h o do fm a k i n gc u b i cb e z i e rc u r v e f ( 甜) = ( 1 一“) u 1 + 川+ 1 r - l r = 0 ，1 ，3i = 0 ，1 ，3 - r iv j 。( 甜) = v i i = 0 ，1 ，3( 3 - 4 ) 其中：v 0 3 ( 甜) = v ( 材) 。 三次b e z i e r 曲线的几何作图法把一个复杂的几何问题化解为一系列的线性运 算，我们可以方便求出曲线上的点，这个性质将被用到定义与三次b e z i e r 曲线相 关的新的几何约束中。 本文只考虑控制多变形为凸多边形的三次b e z i e r 曲线。 第3 章利用三次b e z i e r 曲线求解几何约束求解问题的改进算法 3 3 点、直线、圆与三次b e z i e r 曲线间的几何约束n 1 为了引入三次b e z i e r 曲线作为一个新的几何体，我们首先给出与三次b e z i e r 曲线相关的几何约束。文献【1 】中已经给出点、直线、圆与三次b e z i e r 曲线的几何 约束，但是没有给出三次b e z i e r 曲线与三次b e z i e r 曲线之间的几何约束。下面将 给出这类几何约束。为了便于讨论，我们首先列出文献【1 】中已经给出的点、直线、