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

中文摘要 中文摘要 计算机辅助设计( c o m p u t e r a i d e dd e s i g n ，简称c a d ) 技术是一种利用计算机的 硬件和软件来进行产品的建模、修改、分析和优化的技术。它广泛的应用在科研 和生活的各个领域中，现在它的应用水平已经成为衡量一个国家科技现代化和工 业现代化水平的重要标志之一。c a d 技术的发展经历了四次重大的技术创新，变 量化技术是第四次技术创新。几何约束求解是参数化技术和变量化技术的核心， 即一旦给定了设计草图的若干尺寸和拓扑关系约束，系统就可以自动生成相应的 设计图，工程设计领域中很多问题都可归结为几何约束求解。目前，几何约束求 解的方法主要有四种：基于数值的几何约束求解方法，基于符号的几何约束求解 方法，基于规则的几何约束求解方法和基于图论的几何约束求解方法。现有的几 何约束求解算法主要是针对构造包括点、直线和圆等几何体在内的几何图形，而 在实际的工程设计中涉及的几何图形常常包括三次曲线或更复杂的曲线。本论文 通过增加三次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 曲线；构造序列： 黑龙江大学硕士学位论文 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 正u s eh a r d w a r ea n d s o r w a f 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 fn 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 d t e c h n o l o g yh a l 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 ”n b o l st oe s t i m a t et h e s c i e n c ea n dt e c h n o l o g ya n dt h ei n d u s t 叫m o d e m 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 t o fc a d t e c h n o l o g yh a sg o n et h r o u 曲f o u rs i g n m c a n tt e c h i l o l o g yi i m o v a t i o n s ，t h el 叙 i 衄o v a t i o ni st h ea p p e a r a n c eo fv 撕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 e c o r eo fp a r 锄e t r i c t e c l m o l o g y a 1 1 dv 撕a b l e t e c i l n o l o g y ， i tm e a n st h a to n c et h e d e m e n t i o nc o n s t r a i n t sa n d t o p o l o g i c a lc o n s t r a i n t sa r eg i v e n ，m es y s t e m “l lp r o d u c et h e d 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 nb ed e a l e da l sg e o m e t r i c c o n s t r a i n ts o l v i n g a tp r e s e n t t h e r ea r ef o u rb a l s i c 印p r o a c h e st og e o m e t r i cc o n s t r a i n t s o l v i n g ：n 啪e r i c ma p p r o a c h ，s y m b 0 1 i ca p p r o a c h ，m l e - b a s e d 印p r o a c ha n dg r a p h b a l s e d a p p r o a c h t 1 1 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 m c tg e o m e t r i c g 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 r e ni n c l u d e sc u b i c c u r v eo rm 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 e d r a w i n gs c o p eo 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 n ，ea sa n e w g e o m e t r i cp r i m i t i v e t h ei m l o v a t i o no ft h e s i s ，o n eg i v e sg e o m e t r i cc o n s t r a i n t sa n d m a t h e m a t i c sd e s c r i p t i o n 锄o n gp o i n t s ，l i n e s ，c i r c l e sa n dc u b i cb e z i e rc u r v e s ，t h eo t h e r g i v e sc o n s 仇j c t i o no fc u b i cb e z i e rc u r v eb yu s i n gt h e s en e wg e o m e t r i cc o n s t r a i n t s ，a n dp u t f o n v a r dan e wm e 吐l o do fg e o m e t d cc o n s t r 2 l i n ts o l v h l gm c l u d i n gp o i n t s ，l i n e s ，c i r c l e sa n d c u b i cb e z i e rc u r v e s t h e r ei sn l o r ep m c t i c a ls 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 蛐s o l v n g ，w m c hi sm ec o r eo fp a r a m e t r i ct e c l l r l o l o g ya r l dv 撕a b l et e c h n o l o 夥 k e y w o r d s ： g e o m e t r i cc 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 l o ns e q u e n c e ； 独创性声明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。掘我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得墨蕉堑太堂或其他教育机构的 学位或证书而使用过的材料。 学位论文作者签名：孑伢签字只期：芴艿年，月多1 同 学位论文版权使用授权书 本人完全了解墨蕉逛太堂有关保留、使用学位论文的规定，同意学校保留并 向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权墨蕉江太堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以采用影印、缩印或其他复制手段保存、汇编本学位论文。 学位论文作者签名：孑僧 导师签名： 猖参昆 签字r 期：么舔年f 月琴1 日 签字同期： 锄瞬，月歹同 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 第l 章绪论 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 ra i d e dd e s i g n ) 简称 c a d 的概念【lj ，它是指利用计算机硬件和软件进行的设计活动，包括使用计算 机的数据库、程序库及通讯等技术来完成设计过程的信息检索、分析、计算、综 合、修改及文件编制工作。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 m 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 年首次提出了属性空 第1 章绪论 间的映射，引入三个公理，并由此从数学上推导出定理，很好地解释了设计过程。 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 等人提出了参数 化设计1 2 3 l 。参数化设计的基本原理就是系统在设计过程中自动地捕获用户的设计 意图，从而将用户设计中的各个设计对象以及对象之问的关系记录下来，而当用 户修改图纸中尺寸标注和设计参数时，系统能够自动对图纸进行必要的修改使图 纸中反映用户设计意图的设计对象之间关系依旧得以维持。参数化技术首次引入 了约束的概念，它是一种基于约束的设计方法。而后，1 9 9 7 年s d r c 公司又推出 了变量化技术，这是参数化技术的一次飞跃。基于约束的设计是智能c a d 的一 3 黑龙江大学硕士学位论文 个重要标志，基于约束的参数化和变量化设计系统把问题描述与问题求解技术分 离成相互独立的两个部分，使得该类设计方法较其他方法更具有明显的优势，它 有以下的优点： ( 1 ) 用户可以任意方式组合，以任意顺序定义几何约束和工程约束。基于约束 的设计具有统一处理这些约束的能力，并能适合广泛意义上的工程设计。 ( 2 ) 基于约束的设计，能很快地记录设计者的意图，允许多个不同应用领域的 用户完成同一项设计任务。 ( 3 ) 基于约束的设计，能够求解过强约束或约束不足问题，而且允许用户集中 地考虑某一部分的细节设计。 ( 4 ) 基于约束的设计，能全面给出解的过程，便于用户整体考虑。 ( 5 ) 基于约束的设计，具有很好的人机交互功能，能够充分地利用交互特性， 逐步地确定设计过程，给出全部的设计解。 基于约束的参数化和变量化设计系统，它的主要功能包括： ( 1 ) 从几何参数化模型能自动地导出精确的几何模型。它不要求输入精确图 形，只要求输入一个草图，标注一些几何元素的约束，再通过改变约束条件来自 动导出精确的几何模型。 ( 2 ) 通过修改局部参数束达到自动地修改精确的几何模型的目的，大致形状相 似的一系列零件，只需修改一下参数，便可以生成新的零件，这可大大地提高生 产效率。 参数化技术与变量化技术的核心就是几何约束求解，几何约束求解是指在输 入一个草图以后，用户可以随时在需要的时候，以任意的方式任意的顺序重新输 入几何约束，然后由计算机自动导出精确的满足用户要求的几何图形的过程。除 了在机械设计中应用以外，几何约束求解经常出现在计算机视觉、连杆设计、机 器人、分子结构设计等领域中】。 1 4 论文的结构 本论文主要分为四个部分 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 几何约束：两个或多个几何体之间所具有的几何关系，例如点与点 之间的距离，直线与直线之i 白j 的角度，直线与圆相切等等。 通常我们将几何约束做如下分类： ( 1 ) 几何形式的几何约束 尺寸约束：一般是由用户显示输入的。通常包括两点之间的距离、直线与直 线之问的角度、点到直线的距离、半径约束和两条平行线之间的距离等等。 拓扑约束：一般是隐含的，是由系统根据草图自动建立的。通常包括水平约 束、竖直约束、两条直线平行和垂直、三点共线、两个角相等、两个圆共心等等。 另外根据几何约束中所涉及的几何体的个数，还可以将几何形式的几何约束 分成如下三类： 一元约束：只涉及到一个几何体的约束，例如线段的长度就是一个一元约束。 二元约束：涉及到两个几何体的约束，大多数的几何约束均属此类。 多元约束：几何约束中涉及到两个以上的几何体，例如a ，b ，c 三点共线、 线段的长度相等，角度相等。 ( 2 ) 代数形式的几何约束 方程约束：指以方程的形式给出的几何约束。例如三角形a b c 的面积等于 圆o 的面积。 不等式约束：有时为了表示点在几何图形中的构造顺序时用到，例如 a b c a 表示点a ，b ，c 是以顺时针的顺序构造的。 第2 章几何约束求解概述 基于以上的基本概念，可以给出几何约束求解的准确定义。 定义2 1 3 几何约束问题：给定一个几何体的集合。和一个关于集合。中的几 何体之间的几何约束的集合c ，则我们将二元组( o ，c ) 称为几何约束问题。有时， 也将几何约束问题称为几何自动作图问题。 下面是一个几何约束问题的例子： 如图2 1 所示，作平行四边形a b c d ，已知线段a b 的长度盔，线段a d 的长 度d ，线段a b 与线段a d 间的角度是臼。 a 矾 图2 1 一个几何约束问题的例子 c f i 9 2 1 绷e x a m p l eo fg 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 ，d ；线段：a b ，b c ，c d ，a d ) 几何约束的集合c = 线段a d 的长度：线段a b 的长度；线段a d 与线段a b 间 的角度 定义2 1 4 几何约束求解：指对于给定的一个几何约束问题( o ，c ) ，根据一定的 算法作出一个或多个几何图形。其中，这个几何图形是由集合o 中的所有的几何 体构成的，并且这些几何体之间要同时满足集合c 中的所有的几何约束。 定义2 1 5 几何约束问题的解：指根据一定的算法作出的由集合。中的所有 的几何体构成的且满足集合c 中的所有的几何约束的几何图形。 根据几何约束问题的解的个数，我们将几何约束问题分成如下三类： ( 1 ) 完整约束的几何约束问题：几何约束问题有有限个解。 黑龙江大学硕十学位论文 ( 2 ) 欠约束的几何约束问题：几何约束问题有无限个解。 ( 3 ) 过约束的几何约束问题：几何约束问题没有解。 下面，我们从几何约束问题本身所具有的性质出发对几何约束问题进一步分 类。首先介绍两个概念： 定义2 1 6 几何体的自由度：指要确定这个几何体的位置所需要的独立参数的 个数，我们用d o f ( 0 ) 来记几何体o 的自由度。例如二维空间中的点的自由度是2 ， 圆的自由度是3 ，线段的自由度是4 。三维空间中点的自由度是3 ，直线的自由度 是4 。 定义2 1 7 几何约束的约束度：指为了描述一个几何约束所需要的代数方程的 个数，我们用d e f ( o ) 来表示几何体o 的约束度。例如点与点之间的距离约束的约 束度是l ，两直线之间的角度约束的约束度是1 ，直线与圆的相切约束的约束度是 1 。 由以上的定义，我们称一个几何约束问题( o ，c ) 是： 结构上完整约束的几何约束问题：如果集合o 中的任何一个子集o 中所包含 的几何体的自由度总和等于集合c 中所有关于子集o 中几何体的几何约束的约束 度的总和减去3 ( 二维) 或6 ( 三维) ； 结构上欠约束的几何约束问题：如果集合0 中的任何一个子集o 中所包含的 几何体的自由度总和大于集合c 中所有关于子集o 中几何体的几何约束的约束度 的总和减去3 ( 二维) 或6 ( 三维) ； 结构上过约束的几何约束问题：如果集合o 中的任何一个子集o 。中所包含的 几何体的自由度总和小于集合c 中所有关于子集o 中几何体的几何约束的约束度 的总和减去3 ( 二维) 或6 ( 三维) 。 第2 章几何约束求解概述 2 2 几何约束求解的主要方法 几何约束求解的方法发展到现在，大致可以分为四类：基于数值计算的几何 约束求解方法，基于符号计算的几何约束求解方法，基于规则的几何约束求解方 法和基于图论的几何约束求解方法。下面我们分别介绍： 2 2 1 基于数值计算的几何约束求解方法 通过建立一个直角坐标系，将所有给定的几何约束转化成一系列表示几何约 束的代数方程，方程中的变量表示几何体的独立参数。这样得到一个非线性代数 方程组，解这个非线性代数方程组得到变量值，即几何体在直角坐标系的坐标， 然后就可以构造出相应的几何图形。第一个用数值计算的方法求解几何约束问题 的c a d 系统是i e s u t h e r l n a d 研制的s k e t c h p a d 系统l 。除此之外，还有t h i n g l a b 系统f6 1 ，j u n o 2 系统【7 】和m a g r i t t e 系统f 8 1 等。 目前，常用的基于数值计算的几何约束求解方法有n e 州o n r 印h s o n 方法和同 伦连续法。n e o n r a p h s o n 方法【9 】是数值计算中用的最多的一种方法，这种方法 的求解速度快，但是需要一个好的初值。为此，j u n o 【1 0 l 提出用草图作为初值的方 法。r l i g h t 和g o s s a r d 提出了一种求逆矩阵的新方法l4 1 ，降低对初值的敏感性。 同伦连续法在一定程度上可以弥补n e o n r a p h s o n 方法对初值的选取比较敏感的 不足一4 1 。设f ( x ) = o 是我们所要求的方程组，根据同伦连续法可以找到一个容易 求解的方程组g ( x ) = o ，然后令f ( x ，旯) = ( 1 - 兄) g ( x ) + 五f ( x ) ，则f ( x ，o ) = g ( x ) ，f ( x ，1 ) = f ( x ) 。 设x 。是g ( x ) = o 的一个解，即f ( xo ，o ) = o ，在兄从0 连续变化到1 的过程中，以x 。为 初值进行迭代，最终可以得到坟x ) = 0 的解。同伦连续法往往需要很大的计算量， 通常仅限于求解一些小的方程组。 用数值计算的方法求解几何约束问题的优点是速度快，而且能够解一些其他 方法解不了的大的代数方程组，缺点是不能处理欠约束和过约束的几何约束问题， 并且对初值的选取比较敏感。在实际的几何约束求解过程中，当用其他的方法无 效的时候，都用数值计算的方法来求解。 黑龙江大学硕士学位论文 为了弥补基于数值计算的方法求解几何约束问题的不足，中国科学院的高小 山研究员提出一种将代数方程组的求解问题转化成一个优化问题的极小值求解问 题l | 引，然后再用拟牛顿法求解这个极小值的方法。文献 1 6 中给出了一个轨迹求 交的数值计算方法。文献 1 7 中还提出了一种将同伦函数与传统迭代法结合起来 的新数值迭代法。文献 9 ，1 8 ，1 9 ，2 0 中也给出了一些改进的基于数值计算的几 何约束求解方法。 2 2 2 基于符号计算的几何约束求解方法 当几何约束问题的代数方程组中的方程系数不是确定的数值，而是一个参数 的时候，需要用符号计算中的消元法求解代数方程组，这种方法可以给出由参数 形式的系数表示的方程组的解析解。 基于符号计算的几何约束求解方法大致有、u 砌t t 特征列方法，g r o b n e r 基方 法和结式法。w u r i n 特征列方法【2 ”是将方程组的零点集分解成一个包含一些容易 求解的简单的代数方程组的零点集的集合。基于理想多项式理论的g r o b n e r 基方法 【2 2 ，2 3 1 ，首先将方程组转化成一个同解的三角化方程组，这个方程组可以很容易用 回代的方法求解。著名的b u c h b e r g e r 算法就是采用这种方法求解的。文献 2 4 中 g r o b n e r 基方法被应用在几何约束求解。基于行列式理论的结式法【2 5 1 ，其基本思想 是利用原有的方程组生成一个以原有的方程组中的变量的系数为变量的方程组， 这个方程组相对于原来的方程组具有某些容易求解的特征。 基于符号计算的几何约束求解方法的优点是可以符号求解，即方程组的变量 的系数可以是一个符号而不是具体的数值，而且可以求出方程组所有的解。另外， 符号计算的方法还可以用来判断几何约束问题是否是完整约束的、欠约束的和过 约束的。缺点是求解的速度比较慢，通常需要消耗大量的计算时间和空间。 2 2 3 基于规则的几何约束求解方法 首先将几何约束用谓词来代表，然后将一系列的重写规则应用于这些谓词， 通过推理，最后将几何约束问题转化成一个可构造的形式【2 “2 引，即通过直尺和圆 第2 章几何约束求解概述 规将满足几何约束的几何图形构造出来。 全局延拓法1 2 9 j 是一个典型的基于规则的几何约束求解方法。a h b o m i n g 是 第一个尝试用这种方法求解几何约束问题的【6 1 。全局延拓法以几何约束问题的构 造性描述作为输入，最后输出几何体的具体位置，在确定几何体的位置之自，j - ，首 先通过一定的推理规则和一个几何公理集合从几何约束问题本身出发，得到一个 几何信息库，在几何信息库中找到关于这个几何体的所有全局信息，然后去掉一 个几何约束，则会得到这个几何体所在的一条几何轨迹；再去掉另外一个几何约 束，会得到另外一条几何轨迹，通过求这两条轨迹的交点，就可以得到这个几何 体的位置。b e a td b 1 1 l d e r l i n 第一个利用推理数据库的方法符号求解几何约束问题 i3 0 j ，并且在用p r o l o g 程序语言实现算法的同时向m o d u l a 2 程序语言提供了一 个接口，使得这两个程序语言可以通过一个共同的推理数据库来实现交流。随后 又出现了大量的利用数据库推理的方法进行几何约束求解的算法【3 卜3 6 1 。k r a m e r 提 出了一个可以处理三维几何约束问题的自由度分析法f 3 7 3 8 1 ，用于处理由连杆所产 生的几何约束问题。陈立平等人提出了一种以图论、稀疏矩阵和自由度分析等理 论为基础的几何约束满足问题的规约分治算法【3 9 4 0 1 ，通过对几何约束系统的最大 分解，大大减少了求解的规模。文献 4 1 中董金祥和葛建新等人提出了一种基于几 何抽象的几何约束求解方法，通过几何抽象来表达约束，并利用约束网的形式， 在层进行几何化简推导和运算，获得解集。文献 4 2 中提出了一种基于数值的几 何约束求解方法和基于规则的几何约束求解方法相结合的方法，文献 4 3 中将图 论的方法与基于规则的方法结合起来以提高速度。 基于规则的几何约束求解方法的优点是可构造性。一旦几何约束问题可以转 化成可构造的形式，就可以很快构造出满足约束的几何图形，而且构造步骤简单 明了，容易被用户理解。缺点是由于推理过程往往要搜索和匹配整个数据库，所 以导致用这种方法求解几何约束问题的速度比较慢而且实现起来也很困难。对于 过约束和欠约束问题，基于规则的方法会以交互式的方式提醒用户发生过约束和 欠约束的地方，同时给出几种可选的解决方案供用户选择，但这要取决于用于推 理的数据库的建立原则。 黑龙江大学硕士学位论文 2 2 4 基于图论的几何约束求解方法 基于图论的几何约束求解方法首先将几何约束问题用一个约束图表示，顶点 代表几何体，边代表几何约束，一个边和两个顶点相连表示这个边代表的几何约 束是与这两个顶点代表的几何体有关的。然后，用图论中的方法分析约束图后产 生一个构造序列，根据所产生的构造序列实际构造出所要求的几何图形。 1 9 9 1 年，o w e n 提出了三角分解法【4 4 ，4 引，将一个几何约束问题的表示图分解成 一系列的三连通子图，这些子图在几何上对应着一个刚体，然后将这些刚体按分 解的相反顺序组合起来，就得到构造序列。h o f h n 锄和f u d o s 等人在1 9 9 5 年提出 了簇合并方法【4 6 ，4 7 1 ，该方法给出了将一个几何约束问题分解为可作图子集的算法， 使基于图论的几何约束求解方法向前推进了一大步。文献 4 8 ， 4 9 中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 年利用图论的方法来分析几何体的自由度，从而提 出了求解几何约束问题的自由度分析法”0 1 。孙家广和胡事民等人提出了一种剪 枝一归约算法的几何约束分解策略【5 卜5 3 1 。陈立平等人针对欠约束情况下约束求解 规划存在的问题，提出一种几何约束系统有向图优化处理算法【5 4 1 。高小山和蒋鲲 提出了求解几何约束问题的几何变换法1 5 5 】。l a t h e 锄引入s 树算法提出了一个几何 约束求解的连通图算法【56 | 。文献 5 7 中提出了一种新的约束有向图匹配算法。 基于图论的几何约束求解方法的优点是速度快。缺点是这种方法对几何约束 问题中所包含的几何体和几何约束的类型比较敏感，当每增加一种新的几何体或 几何约束时，都要对原有算法作相当大的改动。 2 3 本章小结 本章介绍了几何约束求解的基本概念，详细叙述了几何约束求解的四种主要 方法，并且指出了四种方法的优缺点。 第3 章利用三次b e z i e r 曲线求解几何约束问题 第3 章利用三次b e z ier 曲线求解几何约束问题 本章将首先介绍一些预备知识、三次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 ，x ：，x 。) ，其中p 是谓词名，x 。，x 2 ，x 。是个体。例如：o n l e ( p ，1 ) 表示p 点在直线，l 上， d i s t a n c e ( 鼻，足，d ) 表示只和足两点间的距离是d 。 3 1 2 基本构造和构造 将下面每一个谓词形式称为一个基本构造。 ( 1 ) p o n t ( j p ) ：在平面上作一个自由点j p 。 ( 2 ) 0 n ( 尸，d ) ：在几何体d 上作一个半自由点尸。 ( 3 ) 附t e r ( 尸，q ，d ：) ：作几何体q 和d 2 的交点尸。 1 1 黑龙江大学硕士学位论文 ( 4 ) l i n e ( 彳，b ) ：作过点彳和点b 的直线。 ( 5 ) c i r c l e ( p ，d ) ：作以点尸为圆心以d 为半径的圆。 根据以上的基本构造，还可以得到一些其他的构造： a l 烈e ( 彳，乡) ：作过点彳点与直线，成秒角的直线。 pl i n e ( r ，p ，q ) ：构造一条通过点r 且平行于直线l 烈e ( p ，q ) 的直线。 p c i r c l e ( d ，尸) ：构造一个以点d 为圆心且通过点尸的圆。 a c i r c l e ( j p ，q ，尼9 ) ：画一个通过点尺的圆弧，满足么袱q = 臼。 c o n s t r u c t ( d ，q ，d 2 ，q ) ：表示由几何体q ，0 2 ，仇构造几何体d ， 七2 ，d 与9 ( f _ l ，七) 的关系有如下几种情形： 点、线：表示点在线上或线过一点。 点、圆：表示点在圆上或圆过一点。 线、线：表示两直线成某个角度。 线、圆：表示线圆相切。 圆、圆：表示圆圆相切。 我们将基本构造和由它得到的其他的构造组合统称为构造。 3 1 3 构造序列 一个有序的集合( c 。，c ：，c 。) ，称为一个构造序列，如果这个有序集合满足 以下两个条件：( 1 ) 每个c ，代表一个具体的构造，包括基本构造和其他的构造；( 2 ) 假设由构造c ，引入的几何体是p ，则构造几何体9 所需的其他的几何体是由 c l ，一，c ，i 引入的。 由上面定义的构造序列，图2 1 中平行四边形的构造序列为： 构造1p o m t ( 彳) ： 第3 章利用三次b e z i e r 曲线求解几何约束问题 构造2 o n ( “彳) ； 构造3n 、j t e r ( b ，o n ( ，1 ，彳) ，c i r c l e ( 爿，d 1 ) ) ； 构造4l 烈e ( 爿，b ) ； 构造5烈t e r ( d ，a l n 、i e ( 彳，1 ，秒) ，c i r c l e ( 彳，d 2 ) ) ； 构造6l 烈e ( 爿，d ) ： 构造7n t e r ( c ，p l 烈e ( b ，么，d ) ，p l 烈e ( d ，彳，b ) ) ； 构造8l 烈e ( b ，c ) ； 构造9l 烈e ( c ，d ) 。 3 2 三次b e zie r 曲线 本节将简要介绍三次b e z i e r 曲线的定义和三次b e z i e r 曲线的几何作图法。 3 2 1 三次b e zie r 曲线的定义 给定四个顶点v i ( i - o ，1 ，2 ，3 ) ，则可以定义一条平面三次b e z i e r 曲线p ( 甜) ： p ( 甜) = 色舢) v = ( 1 一甜) 3v o + 3 ( 1 一“) 2 “v l + 3 ( 1 一甜) 材2 v 2 + “3 v 3 ， 甜【0 ，1 】( 3 - 1 ) 其中b ，( “) 为b e m s t e i n 多项式，b 3 ，( “) = c ；( 1 一甜) 3 一甜，曲线p ( ) 通过首、 术顶点v 。和v ，并且与由四个顶点相连所形成的特征多边形首、术两边相切。 三次b e z i e r 曲线的参数方程形式为： “【o ，1 】( 3 2 ) b 乃 沪j 矿 + 岛 儿 甜 d d 一 一 0 0 3 3 + + 蜣 砂 2 2 、， 甜 一 一 1 l 1 ，l，l 3 3 + + 儿 1 ， j 、，、j 甜 一 一 0 0 = | | 、，、， ，k，、 x y 厂y、l 黑龙江大学硕+ 学位论文 ( ，) 是点v 0 的坐标，( 工，j ，。) 是点v 的坐标，( x ：，y ：) 是点v ：的坐标， ( 屯，j ，3 ) 是点v ，的坐标。 3 2 2 三次b e zie r 曲线的几何作图法 三次b e z i e r 曲线的几何构造称为几何作图法【5 8 1 ，应用作图法，可便捷地确定 三次b e z i e r 曲线上与某给定参数值相对应的点。首先根据给定的参数值甜，在特 征多边形的每一条边上确定某一分割点，使分割后的两线段之比为“：( 1 一z ，) 。由 此，可得分割点的点矢为：v i i = ( 1 一“) v + “v i + i ，f = 0 ，1 ，2( 3 3 ) 式中，第二个下标1 表示第一次分割。第一次分割后，得到3 个分割点，由其组 成一个新的多边形，其边数为2 。用相同的方法再对该多边形的各条边进行分割， 得到2 个分割点v o ：和v 1 2 ，形成另一个新的多边形。按相同的过程分割2 次以后， 仅剩两个顶点v 。：和v 。：，对这两个顶点组成的线段再分割一次，得到点v 0 ，即为 三次b e z i e r 曲线上与参数甜相对应的点，v 。：v 。：为曲线在v o ，处的切线。几何作图 法如图3 1 所示： v ， v 3 图3 1 二次b e z i e r 曲线的作图法 f i 9 3 - lam e t h o do fm a k i n gc u b j cb e z i e rc u r v e 上述三次b e z i e r 曲线的几何构造过程用德卡斯特罩奥1 5 9 1 建立的递归公式表示： 第3 章利用三次b e z i e r 曲线求解几何约束i 司题 厂v i ，( 甜) = ( 1 一”) v r 1 + 甜v r - l f o ，1 ，3 i _ o ，1 ，3 - r 弋v “甜) ：v i i = 0 ，1 ，3( 3 4 ) 其中：v 0 3 ( “) = v ( “) 。 三次b e z i e r 曲线的几何作图法把一个复杂的几何问题化解为一系列的线性运 算，我们可以方便求出曲线上的点，这个性质将被用到定义与三次b e z i e r 曲线相 关的新的几何约束中。 3 3 引入新的几何约束 引进三次b e z i e r 曲线，即增加了一个新的几何体，我们需要给出与三次b e z i e r 曲线相关的新的几何约束，也就是三次b e z i e r 曲线与点、直线和圆间的几何约束， 下面将给出这些新的几何约束的定义。 3 3 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 曲线的距离。 点在三次b e z i e r 曲线上：令点的坐标为( x ，y ) ，满足三次b e z i e r 曲线的