（计算数学专业论文）欠过约束几何约束求解问题完整化算法的研究.pdf

中文摘要 中文摘要 计算枫辅助设计( c o m p u t e ra i d e dd e s i g n ，简称c a d ) 技术是一种利用计算杌 的硬件和软件来进行产品的建模、修改、分析和优化的技术。它广泛的应用在科 研和生活的各个领域中，现在它的应用水平已经成为衡量一个国家科技现代化和 工业现代化永平的重要标志之。 c a d 技术的发展经历了四次重大的技术创新，变量化技术是第四次技术创新。 几何约束求解是参数化技术和变量化技术的核心，即一旦给定了设计草图的若干 尺寸和拓扑关系约束，系统就可以自动生成相应的设计图，工程设计领域中很多 问题都可归结为几何约束求解。目前，几何约束求解的方法主要有四种：基于数 值的几何约束求解方法，基于符号的几何约束求解方法，基于规则的几何约束求 解方法和基子图论的几何约束求解方法。 设计者在设计的初始阶段，通常是在草图上不断的添加相关的几何约束，这 往往造成设计的草图不总是完整约束的，而是由欠约束到过约束的过程。但通常 的算法都是针对完整约束薛几何约柬求解问题的。所以，在求解一个几何约束问 题之前，对其欠、过、完整约束性的判定以及将一个欠( 过) 约束的几何约束问 题转化为一个完整约束的几何约束问题尤为重要。基于偶图的d m 分解的判定算 法，可以判定几何约束问题的欠、过、完整约束性，并可以确定欠、过约束发生 的位置。本文在此基础上给出了如何将一个欠( 过) 约束的几何约束问题转化为 完整约束的几何约束问题的方法。对于欠约束的几何约束问题，本文给出了几何 约束的优先级，介绍了如何依据几何约束的优先级添加几何约束的方法，进而提 出了一个将欠约束的几何约束问题转化为完整约束的几何约束问题的算法。对于 过约束的几何约束问题，首先判断过约束是一致性的还是非一致性的，进而将其 转化为一个完整约束的几何约束求解蠢题。本文通过实例验证了此算法的正确性。 关键词：几何约束求解；欠约束；过约束；完整约束；完整化 黑龙江大学硕士学位论文 i i 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 sal ( 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 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 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 d t e c h n o l o g yh a sg o n et h r o u g hf o u rs i g n i f i c a n tt e c h n o l o g y i 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 c c o n s t r a i n ts o l v i n gi st h eg o r eo fp 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 , i t m e a n st h a to n c et h ed e m e n t 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 e s y s t e mw 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 a tp r e s e n t ，t h e r ea r ef o u rb a s i c a p p r o a c h e st og e o m 嘶cc o n s t r a i n ts o l v i n g ：n u m e r i c a la 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 a tt h eb e g i n n i n go ft h ed e s i g n , d e s i g n e ra l w a y sa d d sc o n s t r a i n t st ot h es k e t c h c o n t i n u o u s l y i tm a k e st h es k e t c hn o ta l w a y sc o m p l e t ec o n s t r a i n t ，b u tf r o mu n d e r c o n s t r a i n tt oo v e rc o n s t r a i n t t h ea r i t h m e t i ci sa l w a y su s e dt os o l v ec o m p l e t ec o n s t r a i n t p r o b l e m s t h e r e f o r ei ti si m p o r t a n tt od i s t i n g u i s ht h ep r o b l e mi su n d e r , o v e ro rc o m p l e t e c o n s t r a i n ta n dp u tu n d e ra n do v e rc o n s t r a i n tp r o b l e mt oc o m p l e t ec o n s t r a i n tp r o b l e m b e f o r es o l v i n gt h ep r o b l e m t h ea r i t h m e t i c ，w h i c hb a s e do nt h ed md e c o m p o s i t i o no f b i g r a p h , c o u l dd i s t i n g u i s ht h ep r o b l e mi su n d e r , o v e ro rc o m p l e t ec o n s t r a i n ta n df i n dt h e p o s i t i o n , w h e r eu n d e ro ro v e rc o n s t r a i n th a p p e n s b a s e do nt h i sa r i t h m e t i c ，t h et h e s i s g i v e sam e t h o dt h a tt r a n s f o r m su n d e ra n do v e rc o n s t r a i n tp r o b l e m st oc o m p l e t e c o n s t r a i n tp r o b l e m s f o rt h eu n d e rc o n s t r a i n tp r o b l e m ，t h et h e s i sp r e s e n t st h ep r io ft h e c o n s t r a i n t ，t h em e a n sa n da r i t h m e t i co fa d d i n gc o n s t r a i n t s f o ro v e rc o n s t r a i n tp r o b l e m ， w ej u d g et h ep r o b l e mc o h e r e n c eo rn o tf i r s t l y , t h e nt r a n s f o r mi tt oc o m p l e t ec o n s t r a i n t p r o b l e m t h et h e s i sg i v e ss o m ee x a m p l e st ov a l i d a t et h ec o r r e c t n e s so ft h ea r i t h m e t i c 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 ；u n d e rc o n s t r a i n t ；o v e rc o n s t r a i n t ；c o m p l e t e c o n s t r a i n t ；c o m p l e t i o n 1 1 黑龙汪大学硕士学位论文 独创性声明 本人声明所星交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其健 人已经发表或撰写过的研究成果，也不包含为获得墨蕉逛塞堂或其他教育机构的 学位或证书而使用过的材料。 学位论文作者撼岳畔 签字因期：x 嚆年上月膨日 学位论文版权使用授权书 本人完全了解墨蕉迤塞堂有关保留、使用学键论文的规定，同意学校保留并 向国家有关部f j 或机构送交论文的复印件和电子版，允许论文被查阕帮借阕。本 人授权墨蕴江太堂可以将学位论文的全部或部分内容编入有关数据库进行检索， 可戮采用影瘁、缩印或其他复制手段傈存、汇编本 学位论文作者签名：每碑 导师签名： 学位论文作者签名：去碑 导师签名： 签字尽翘；私研年堂月心嚣 学位论文俸者毕鼗后去悫： 工作单位： 通讯连垃： 签字星期：2 蹲萝年乡胃霹 电话； 罄编： 繁 章绪论 1 1c a d 的发展历史 第| l 章绪论 设计一直是人类认识和改造世界的重要活动。周围世界中的广泛领域，飞机、 轮船、建筑、器疆、家具乃至计算机程序，一切人类的创造物无不需要设计。设 计过程是由信息检索、分析、计算、综合、修改及文件编制等诸多环节构成，其 中形状的分析、综合、修改及图纸绘制是最具有特色的典型设计环节。 2 0 世纪年代中期，在美国诞生了第台电子计算机，这是2 0 世纪科技领 域的卓越成就之一。随着计算机的出现，1 9 6 3 年，美国麻绳理工学院2 4 岁的研究 生i e s u t h e r l a n d 首次提出了计算机辅助设计【l j ( c o m p u t e r a i d e dd e s i g n ，简称c a d ) 的概念，它是指利用计算机硬件和软件迸符的设计活动，包括使用计算机的数据 库、程序库及通信等技术来完成设计过程的信息检索、分析、计算、综合、修改 及文件编制工作。4 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 年代后期出现的变量化 技术。参数化技术的成功应用使它在2 0 世纪9 0 年代前后几乎成为c a d 业界的标 罴缆江大常硕士掌位论文 准。毽参数住技术存在着一些闽题鞠不是，太大限制了设计者豹创造力察想象力 的充分发挥。1 9 9 7 年s d r c 公司首次推出了变量化技术，这是参数化技术的一次 飞跃。变量化技术将整个设计草图当作一个完整的系统来考虑，与构造过程的顺 彦无关，将草蚕孛酶控制尺寸和拓羚关系都粥约柬来表示，这使褥设计初期的草 图可以不是完全定义的，丽将没有完全定义的控制尺寸积拓扑关系用变量存储起 来，暂时以当前的绘制尺寸赋值。设计者可以在任何阶段对草图中的任何尺寸和 拓羚关系进行重新定义，同时这种重新定义也不努牵涉草图孛所有的凡俺实体的 改动。变量化技术提供的灵活更改模型的方式，有效缝支持了c a d 的概念他设计， 可以使设计者的创造力和想象力得到熙充分的发挥。 c a d 技术是最近霹o 年来迅速发展起来的一门新兴的综合性计算机应用系统 技术。它从根本上改变了过去的手工绘图、发图、凭图纸组织整个生产过程的技 术管理方式，将它变为在图形工作站上交互设计，用数据文件发送产品定义，在 统一的数字亿产赫的模型下进行产品的设计打祥、分析计算、工艺规划、工装备 设计、数控燕工、质量控制、编印产晶维护芋麓、组织备件订货供应等，大大提 高了设计的效率和质量，降低了成本。 今天，c a d 技术已经渗透到工程技术和人类生活的几乎所有领域，主要服务 于橇械、电子、字靛、建筑、轻纺、管道铺设等工程领域产品骢总俸设计、辨形 设计、结构设计、优化设计、运动结构的模裂设计、工艺过程设计和数控加工。 它涉及计算机科学、计算数学、计算几何、计算机图形学、数据结构、数据库、 数控技术、较律工程、铸真技术、规器入学鞠人工智囊等众多学科领域。 。2 智畿c a d 的发展历史 智能c a d 是入工智缝( a r t i f i c i a li n t e l l i g e n t ，篱称a i ) 和黝圆技术提终含酶 - - f - j 综合性研究领域，其英文名为i n t e l l i g e n tc a d ，或简写为i c a d 。它将a i 的 理论和技术用于c a d 之中，使c a d 系统麓够在某种程度上具有设计师般的麓能 襄思维方法，麸两把设计叁动化弓| 囊深入，这是c a d 技术在学术上的一个重要方 向。智能c a d 系统的主要目标是支持设计师在设计过程中的思维，“真正”实现 第1 章绪论 具有创造性的设计过程。 1 9 6 3 年，i e s u t h e r l a n d 在他的s k e t c h p a d 系统中第一个采用了用约束定义物 体的方法，此法成为以后约束满足型智能c a d 方法的先驱。最早对智能c a d 的 研究使用专家系统的办法。国际上最早研究智能c a d 的单位是美国的卡耐基梅 隆大学。著名的人工智能学者h a s i m o n 和c a d 学者e a s t m a n 于2 0 世纪7 0 年代 中期带领一批博士研究生研究住宅空间的综合。澳大利亚悉尼大学以j s g e r o 教 授为首的d e s i g nc o m p u t i n gu n i t 从研究工程设计优化方法着手，于2 0 世纪7 0 年 代末开始转向设计中的人工智能技术。2 0 世纪8 0 年代，英国爱丁堡大学的人工智 能系建立一个能支持人做设计的智能c a d 的环境。日本东京大学对智能c a d 的 研究也开展得较早，并具有特色，y o s h i k a w a 教授在1 9 7 7 年首次提出了属性空间 的映射，引入三个公理，并由此从数学上推导出有趣的定理，很好地解释了设计 过程。在国内，浙江大学人工智能研究所是最早开展智能c a d 理论及应用研究的 单位之一。目前，北京航空航天大学、华中理工大学、清华大学、中国科学院数 学与系统研究院等也开始了这方面的研究。 智能交互、智能显示和自动数据获取也是智能c a d 的研究课题之一。为了实 现这些目标和要求，人们提出了面向方案形成过程的i c a d 方法。方案的形成过 程可以看成是一个约束满足问题，即所有的设计要求与限制都被看成对变量的约 束，而最终的方案则是满足所有约束条件后的设计方案。求解的过程则是基于约 束进行的。这一设计方法被称为基于约束满足的设计方法。 目前，智能c a d 的研究中存在着三个前沿问题：第一个问题是解决方案的形 成，第二个问题是围绕着设计对象、设计知识的表达展开的研究，第三个问题是 围绕智能c a d 系统的自动作图功能研究，即几何约束求解。 1 3 几何约束求解技术的引入 工程应用中，大多数机械设计都来源于草图和现有的图形。在概念化的设计 过程中，用户一开始并不关心图形的精确尺寸，而只是粗略地勾画图形的大致形 状。而且，用户也可能在现有图形的基础上，作细微的改进。尺寸的调整是非常 黑龙汪大学硕士掌位论文 普遍的，嚣隽足寸可鼓决定零彳譬酶咒蔼形状，尺寸的改变可以生成不同酶凡衡图 形。两在传统的交互作图系统中，图形一旦生成就很难进行尺寸的调整，没有继 承性。另外，由于概念设计和初步设计阶段要靠设计者的知识和经验樽加以思考 来完成，蠢这些翔识帮经验往往不能用精确的数字模型和算法来箍述，传统的交 互作图系统对此缀难胜任。 为了弥补传统c a d 系统的不足，更好地满足概念化设计的要求，提高设计效 率，2 0 世纪8 e 年代看裁，l i n 和g o s s a r d 等人提出了参数纯设计l 。参数纯设计 的基本原理就是系统在设计过程中自动地播获用户的设计意图，扶焉将用户设计 中的各个设计对象以及对象之间的关系用参数记录下来，而当用户修改图纸中尺 寸标注和设计参数时，系统能够自动对图纸进行必要的修改，使图纸中反映用户 设计意鹜的设计对象之阕的关系依l 毽褥以维持。参数纯技术首次琴l 入了约束的概 念，是一种基于约束的设计方法。而后，1 9 9 7 年s d r c 公闭又推出了变量化技术， 这是参数化技术的一次飞跃溺。变量纯技术将整个设计草图当作个完整的系统来 考虑，与构造过程赡顺序无关；将革露中的控制只寸和拓扑关系都震约束来表示， 这使得设计初期的草图可以不是完全定义的，而将没有完全定义的控制尺寸和拓 扑关系用变量存储起来，暂时戳当前的绘制尺寸赋值。设计者可以在任何阶段对 草图中的任何尺寸和拓扑关系进行重薪定义，同时这种重新定义也不必牵涉草图 中的所有的几何图形的改动。 基于约束满足的参数化和变量化设计系统把问题描述与问题求解技术分离成 摆互独立的两个部分，搜这两部分都褥裂长是的发展。现在，基于终柬的参数纯 和变量化设计系统已成为较成熟的技术领域。它的主要功能包括： ( 1 ) 从几何参数化模型能自动地导出精确的几何模型。它不要求输入精确图 形，只要求输入一个草鍪，标注一些咒俺元素的约束，蒋通过改变约粜条粹来自 动导出精确的几何模型。 ( 2 ) 通过修改局部参数来达到自动地修改精确的几何模型的圈的，大致形状相 戳酶一系裂零箨，只需修改一下参数，便可以生成新麓零件，这大大缝提高了生 产效率。 第 章缮论 同时，也正由于基于约束的设计将问题描述与问题求解技术分离，所以该类 设计方法较其他方法具有明显的优势，主要表现在： ( 1 ) 餍户可以任意方式组合，以钰意顺序定义凡何约束和工程约束。基于约束 的设计具有统一处理这些约束的能力，并能适合广泛意义上的工程设计。 ( 2 ) 基于约束的设计，能很快地记录设计者的意图，允许多个不同应用领域的 用户完成隧一项设计任务。 ( 3 ) 基于约束的设计，能够求解过强约束或约束不足闷题，丽旦允许用户集中 地考虑某一部分的细节设计。 ( 4 ) 基于约束的设计，能全面给出解的过程，便于用户整体考虑。 ( 5 ) 基子约束的设计，具有缀好的入机交互功能，能够充分地利用交互特性， 逐步地确定设计过程，给出全部的设计解。 基于约束的设计是智能c a d 的一个重要标志。基于约束的参数化技术和变量 纯技术的核心就是几何约束求解。凡何约束求解是指在输入一个草图以后，耀户 可以随时在需要的时候，以任意的方式任意的顺序重新输入几何约束，然后由计 算机自动导出精确的满足用户要求的几何图形的过程。除了在机械设计中应用以 外，几何约束求解还经常出现在计算机视觉、连枰设计、机器人、分子结构设计 等领域。 1 4 几何约束求解基本概念 定义1 4 1 几何体：一个几何图形中最基本最具有特征的几何元素。例如2 维中的 点、直线、线段、圆、圆弧和三维中的平面、球面、蓝面等。 定义1 4 2 几何约束：两个或多个几何体之闻所具有的几何关系。例如点与点之间 的距离，直线和直线之间的角度，两条直线垂直，直线与圆相切等。 我们通常将几何约束做如下分类： ( 1 ) 几何形式的几何约束：包括尺寸约束和拓扑约束。 尺寸约束：般是由用户显式输入的。通常包括两点之间的距离、直线与直 线之间的角度、点到直线的距离、半径约束和两条平行直线之间的距离等。 嚣龙江大掌硕士学位论文 拓棼约泰：一般是隐含斡，是壶系统禳攥草墼彝动建立的。遥常包括求乎约 束、竖直约束、蘸条直线平行和垂直、三点共线、鹾个焦相等、两个毽共心等。 根据几何约束中所涉及的几何体的个数，还可以将几何形式的几何约束分为 懿下三类： 一元约束：只涉及个几何体鲍约束。这类足何约束很少见，例如线段的长 度就是一个一元约束。 _ 二元约束：涉及到两个凡褥体的翁束，大多数的咒霸约束属于诧类。 多元约束：涉及到两个以上的几何体的约束。例如三点共线，线段的长度糖 等，角度相等等。 穆) 代数形式的几何约束：包括方程约寨和不等式约柬。 方程约束：指以方程的形式绘出的几何约束。例如，三焦形a b c 的蘸积等于 圆o 的面积。 不等式约束：有时为了表示点在几何图形中的构造顺序时会用劐，例如， a b c 。 几何约束的集合c = 点a 和点b 之间的距离；点b 和点c 之间的距离；直线 a b 和直线b c 之闻的角度) 。 定义1 4 4 几何约束求解；指对于给定的一个几何约束问题( o ，c ) ，根据一定的算 法作出一个或多个几何图形。其中，这个几何图形是由集合0 中所有的几何体构 成的，并且这些凡何体之闻要同时满足集合c 中的所有的几何约束。 定义1 4 。5 几何约束问题的解：指根据一定的算法作出的由集合o 中的所有的几 何体构成的且满足集合c 中所有的几何约束的几何图形。 根据几何约束问题的解的个数，将几何约束闻题分为三类： 完整约束的几何约束问题：几何约束问题有有限个解。 欠约束的几何约束问题：几何约束问题有无限个解。 过约束的几何约束问题：几何约束问题没有解。 根据以上的分类，很难在求解一个几何约束问题之前就能判断出这个几何约 束问题是属于哪一类的。因此，我们从几何约束问题本身所具有的性质出发对几 何约束问题进行重新分类。首先介绍两个相关概念。 定义1 4 6 几何体的自电度：指要确定这个几何体的位置所需要的独立参数的个 数，用d o f ( o ) 来记几何体0 的自由度。例如，二维空间中的点的自由度是2 ，圆 的自由度是3 ，线段的自由度是4 ；三维空闻中的点的自由度是3 ，圆的自由度是 4 。 黑龙江大学硕士学位论文 - - i i i i i i ifii i 黼i i 定义1 1 4 。7 几何约束的约束度：指为了描述一个凡何约束所需要的代数方程的个 数。例如，点与点之间的距离约束的约束度是l ，点m 是线段a b 的中点的三元 约束的约束度是2 。 根据以上定义，我们将一个几何约束闻题( o ，e ) 作如下分类： 结构上完整约束的几何约束问题：如果集合o 中的任何一个子集q 中所包含 的几何体的自由度的总和等于集合c 中的所有关于子集以中几何体的几何约束的 约束度的总和加上3 ( 二维) 或6 ( 三维) 。 结构上欠约束的几何约束闻题：如果集合o 中存在一个子集g 中掰包含的几 何体的自由度的总和大子集合c 中的所有关于子集a 中几何体的几何约束的约束 度的总和加上3 ( 二维) 或6 ( 三维) 。 结构上过约束的几何约束问题：如果集合0 中存在一个子集q 中所包含的几 何体的自由度的总和小予集合c 中的所有关于子集a 中几何体的几何约束的约束 度的总和加上3 ( 二维) 或6 ( 三维) 。 结构上过约束的几何约束问题分为一致性过约束的几何约束问题和非一致性 过约束的几何约束闻题。一致性过约束的足何约束阆题是指结构上是过约束的， 但实际上是完整约束的几何约束问题，即此几何约束问题有有限个解。非一致性 过约束的几何约束问题是指结构上是过约束，实际上也是过约束的几何约束问题， 印此凡谤约束问题无解。 人们经常用几何图形的结构约束性质( 结构上完整约束的、结构上欠约束的 和结构上过约束的) 来刻画几何图形的实际约束性质( 完整约束的、欠约束的和 过约束的) 。这在大多数情形中是正确的，但就一般丽言，由几何图形的结构约束 性质是不能推断出几何图形的实际约束性质的。 一个结构上过约束的几何约束问题可能是完整约束的几何约束问题，也可能 是过约束的凡何约束闻题，还酉能是欠约束的凡何约束闻题：一个结构上欠约束 的几何约束问题可能是过约束的几何约束问题或者是欠约束的几何约束问题；一 个欠约束或过约束的几何约束问题都有可能是结构上完整约束的。 第1 苹绪论 1 5 几何约束求解的主要方法 几何约束求解盼方法发展到现在，大致可分为髓类：基于数值计算的几何约 束求解方法，基于符号计算的几何约束求解方法，基于规则的几何约柬求解方法 和基于图论的几何约束求解方法。下面分别对这四类方法进行简单介绍。 1 5 1 基于数值计算的几何约束求解方法 利用解析几何的知识，建立直角坐标系，将所有给定的几何约束转化成一系 列表示几何约束的代数方程，方程中的变量表示几何体的独立参数，这样就将一 个几何约束问题转化成一个非线性代数方程组的求解问题。然后，用数值计算的 方法求解这个方程组，所得到的解就是几何体的位置坐标，郎可以构造这个几何 墅形。第一个用数值计算的方法求解凡何约束闻题的c a d 系统是1 e 。s u t h e r l a n d 研制的s k e t c h p a d 系统【l 】。除此之外，t h i n g l a b 系统【5 1 ，j u n o 2 系统旧和m a g r i t t e r l 系统也用数值计算的方法求解几何约束闯题。 黧前，常用的基于数值计算的几俺约束求解方法有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 方法f s 是数值计算中用得最多的一种方法，这种方法 求解速度快，但对初值的选取比较敏感。为此，j u n o 提出用革图作为初值的方法1 9 。 为了降低对初值的敏感性，1 l l i g h t 和g o s s a r d 提出一种求逆矩阵的新方法囝，嗣时， 他们又提出了一个改进的d o o l i t t l e s 方法以解决矩阵奇异的问题。同伦连续法在一 定程度上可以弥补n e w t o n r a p h s o n 方法对初值的选取敏感的不足t 1 3 】，而且在理 论上可以找到方程组的所有解。设鼗x ) ：啕是所要求的方程组，根据露侩连续法可 以找到一个容易求解的方程组g ( x ) ：o ，然后令f ( x 舻( 1 g ( x 腿) ，则 f ( x ，o ) = g ( x ) ，f ( x ，1 户f ( x ) 。设而是g ( x ) ：0 的一个解，即f ( x o ，0 ) ：0 。在九从o 连续变 化到l 的过程中，以为初值进行迭代，最终可以得到x ) 司的解。弱伦连续法 往往需要缀大的计算量，通常仪限于求解一些小酶方程组。 用数值计算的方法求解几何约束问题的优点是速度快，而且能够解决一些其 他方法解不了的大的代数方程组。在实际的几何约束问题求解的过程中，当用其 他嚣方法无效的时候，最终都用数值计算的方法来求解。用数值计算的方法求解 黑龙江大学硕士学位论文 几何约束阁题憨缺点是不能处理欠约柬和过约束的几何约束闯题，丽越对初值的 选取比较敏感。 为了弥补基于数值计算的几何约束求解方法的不足，中国科学院的高小山研 究员提出了一种将代数方程组的求鳃闻题转佬成一个优化闻题的极小值求解闯 题，然后再用拟n e w t o n 法求解这个极小值的方法【1 4 】。另外，在文献 1 5 】中还给出 了一个轨迹求交的几何约束求解的数值方法，该方法可以完全求解三维空间中所 有只包含点、线和面的基本构型的问题。文献西，1 6 ，1 7 ，1 8 】中也给出了一些改 进的基于数值计算的几何约束求解方法。 1 5 。2 基于符号计算的几何约束求解方法 当表示几何约束问题的代数方程组中的方程系数是参数的时候，需要用符号 计算静方法来求解方程组。基于符号计算的几何约束求解方法主要用消元法求解 代数方程组，它可以直接给出由参数形式的系数表示的方程组的解析解。 基于符号计算的几何约束求解方法大致有w u r i t t 特征列方法，g r 6 b n e r 基方 法和结式法。w t l 。r i t t 特征列方法醛籀是将方程组的零点集分解成一个包含一些容易 求解的简单代数方程组的零点集的集合。这是由我国著名数学家吴文俊院士提出 的基于特征列的符号计算方法，可以用这种方法进行符号求解的方程组的数量被 证明是最多耐羽。基于理想多项式理论的g r 6 b n e r 基方法馥1 阁首先将方程组转化成 一个同解的三兔化方程组，这个方程组可以很容易地用回代的方法求解。用这种 方法求解的最著名的算法是b u e h b e r g e r 算法。文献 2 3 1 中g r 6 b n e r 基方法被应用于 几何约束求解。基于行列式理论的结式法西j 的基本思想是利用原有的方程组生成 一个以原有的方程组中的变量的系数为变量的方程组，这个方程组相对于原来憋 方程组具有某些容易求解的特性，可以简化和降低求解的难度。 基于符号计算的几何约束求解方法的优点是可以符号求解，即方程组的变量 的系数可以是一个符号丽不是具体数篷。符号计算的方法可以求出方程组的所有 解，而且可以用来判定几何约束问题是完整约束的、欠约束的还是过约束的。这 个方法的缺点是求解速度比较慢，通常需要消耗大量的计算时间和空间。 第 章缭论 5 。3 基于规则的几何约束求解方法 基于规则的几何约束求解方法首先将几何约束用谓词来代表，然后将一系列 重写规则应用于这些谓词，通过推理，最后将几何约束求解问题转化成一个可构 造的形式磷蕊明，帮可以通过蛊尺和圆规将满足几何约束的几何图形构造出来。用 这种方法可以处理一些复杂的几何约束。 全局延拓法【2 8 】是一个典型的基于规则的几何约束求解方法。该方法以几何约 束闷题的构造性描述作为输入，最终输出几俺图形的构造序列，根据构造穿列， 可以将几何图形做出来。该方法的主要思想是，为了决定一个几何体的位置，首 先找到关于这个几何体的所有全局信息；然后，去掉一个几何约束，则将会得到 这个凡何体所在的一条几何轨迹；然后，去掉另外一个几何约束，弱样会得到另 外一条几何轨迹。于是，通过求这两条轨迹的交点，就可以得到这个几何体的位 置。a 。h b o m i n g 是第一个尝试用这种方法求解几何约束问题的【5 1 。除此之外，还 有以下的方法：b e a td b r f i d e r l i n 是第一个利用推理数据库的方法符号求解凡何约 束问题的冽，并且在用p r o l o g 程序语言实现算法的同时向m o d u l a - 2 程序语言 提供了一个接口，使得这两个程序语言可以通过一个共同的推理数据库来实现交 流。随后又出现了大量的利用数据库推理的方法进行几何约束求解的算法 3 0 - - 3 熨。 k r a m e r 提出了一个可以处理三维几何约束瓣题的臻由度分析法【3 6 翊，用来处理由 连杆所产生的几何自动作图问题。陈立平等人提出了一种以图论、稀疏矩阵和自 由度分析等理论为基础的几何约束求解问题的规约分治算法 3 8 , 3 9 ，通过对几何约 束系统的最大分解，大大减少了求解的规模。董金祥和葛建新等人提出了一种基 于几何抽象的几何约束求解方法1 4 0 1 ，通过几何抽象来表达约束，并利用约束网的 形式，在层进行几何化简推导和运算，获得解集。h o f f m a n n 等人提出了一种基于 数值计算的凡何约束求解方法和基于规则的几何约束求解方法相结合的方法鞭。 j y l e e 将图论方法与基于规则的方法结合以提高速度【3 9 4 2 1 ，但是由于取消了回溯 而缩小了方法的适用范围。 基于规则的几何约束求解方法的优点是爵构造性。一量凡簿约束求解瓣题可 以转化成可构造的形式，就可以很快构造出满足约束的几何图形，而且构造步骤 黑龙江大学硕士学位论文 i l t i i ii i ll i i i i l , , i i lil i i i 嵩i i i m li l i i i i i t i t 麓i i 篱单隳了，容易被尾户理解。缺点是由于推理过疆往往要搜索和涎配整个数据库， 所以导致用这秘方法求解几侮约束问题的速度比较慢面且实现起来也缀困难。对 于过约束和欠约束的几何自动组图问题，基于规则的方法会以交互的方式提醒用 户发生过约束藉欠约束的位置，霹时给塞a 种哥遥瀚解决方案供瘸户选择，这要 取决于用于推理的数据瘴的建立原曼| j 。 1 5 4 基于图论的几何约束求解方法 基于图论的几何约束求解方法首先将几何约束问题用一个图来表示。在图中， 顶点代表凡鹰薄，边代表凡何约束，一个边和两令顶点相连表示这个选代表鹩几 何约束是与这两个顶点代表的几何体有关鳇。然盛，用图论中的方法来处理这个 图：第一步是经过分析图后产生一个构造序列，第二步是根据所产生的构造序列， 实际构造所要求的几何蔑形。 溉在1 9 9 1 年首次提蹴一个基于圈论的足何约寨求解方法：兰焦分解法 4 3 , 4 4 。该方法将一个几何约束问题的表示图分解成一系列的三连通子图，这些子 餮在几何蛊观上对应着一个刚体，然后再将这些剐体按照分解的相反顺序组合起 来，就可以得到相应的构造痔列。鸯姥之爱，久们提出了狠多基于圈论的见何终 束求解的算法 1 , 4 2 , 4 5 , 4 6 1 。1 9 9 5 年，h o f f m a n n 和f u d o s 等人提出了种基于图构造的 几何约束求解方法1 7 4 5 4 7 1 ：簇合并方法。该方法给出了将一个几何约束求解问题分 解为可箨鬻子集的算法，使基于銎论的死俺约束求解算法彝翦推进了一大步。 f i t z e r l a n d 和t o d d 在1 9 8 1 年提出了一个只考虑垂直和水平距离的基子图论的几何 自动作图算法郑蚓。1 9 9 3 年，s a i t - a o u d i a 利用偶图的理论将原有的几何约束求解 闯题分解成一些小的完整缝束、过约束和欠约柬的几祷约束求解润题的集合1 5 馔， 这种方法可以用来处理过约束和欠约窳的几何约束问题。c h s u 和b e a r d b r t i d e r l i n 在1 9 9 4 年利用图论的方法来分析几何体的自由度，从而提出了求解几何约束问题 戆鸯壶度分析法餮h 。2 0 世纪9 0 年代，癸家广_ 耩胡事民等人提豳了一静剪枝壤孽约 算法的几何约束分解策略 5 2 - 5 4 1 。陈立平等人针对欠约束情况下约束求解规划存在 的问题，提出了种几何约束系统有向图优化处理算法【5 5 】，成功地实现了约束求 第 章绪论 i i i i 赫篇i i i i 黛鼍i i i i 鞘黼；i i i i 麓i i i i ii i i i i i l i i i i i ii i i ii i i i i 黼i i i i 解排序的自适应优化调整。高小山和蒋鲲提出了求解几何约束阀题的几何变换法 f 5 6 】。l a t h e a m 引入s 树算法提出了一个几何约束求解的连通图算法【5 7 1 。文献【5 8 】 中提出了一种新的约束有向图匹配算法。 基于图论的几何约束求解方法的优点是速度快。缺点是对几何约束问题中所 包含的几何体和几何约束的类型比较敏感，即每增加一种新的几何体或几何约束 时，都要对原有的算法作相当大的改动。 1 。6 论文结构 第l 章绪论简介c a d 和智能c a d 的发展历史，弱时弓l 入几何约束求解， 并介绍几何约束求解的基本概念和主要方法。 第2 章几何约束求解问题欠、过、完整约束性的判定说明了欠、过、完整 约束性判定的必要性，详细介绍了基予偶蚕鲍d m 分解的判定算法，并举例说明。 第3 章欠( 过) 约束几何约束求解问题的完整化算法详细介绍了如何将欠、 过约束的几何约束问题转化为完整约束的几何约束问题的方法，并提出了算法。 第4 章实例分析髑四个具体的例子来验证算法的可行性和有效性。 慧龙江大学硕士学位论文 第2 章几何约束求解问题欠、过、完整约束性的判定 2 。1 欠、过、完整约束性的判定算法 求解个a 旃约束润题蕊算法，除了爵以快速有效媳构造毒足 鼍图形蒙辨， 一个很重要的研究内容就是几何约束求解的定性分析：遴常包括欠、过和完整约 束性的判定问题、参数有效范阐的确定问题、多解问题、求解失败的诊断和误差 的传播离题等。几何约柬求解的定性分析对于提高几何约柬求解的交互性耪准确 性是鼍 常必要的。 设计者在设计的初始阶段，通常是在草图上不断地添加自己的构想，实际上 就是添热些相关蘸尼何约束。这往往造成设计静草图不总是完整约束的，丽是 由欠约束到过约束的设计过程。然藤，几舞约束求解方法一般都是针对完整约束 的几何约束问题的。设计者在设计过程中由于专注于自己的构想，通常会忽略这 个阍题，这可能会给设计酶修改和实现带来许多麻烦。因此，一个麓够判断苹图 的欠、过或完整约束的算法就显褥尤为重要，它可以实时她提示设计者，使设计 者在设计的过程中可以交互的修改草图。 1 9 9 i 年，d 。s e r r a n o 针对自由度和约束度是i 的几何体和几何约束给出了一个 判定算法1 5 9 , a ) 。o w e n 固年绘出了一种判定欠或过约束的数值方法阚。r + s 1 鑫t k 缀 在1 9 9 4 年通过人为地在几何约束上加上权值给出了一个判定算法【6 l 】。1 9 9 8 年，高 小由研究员和周咸青教授给出了一个判断草图是否是过约束的符号计算方法 2 8 1 。 蒋鲲提出了一个基于偶篷酶d m 分解的针对包括代数形式的约束在蠹翡判断草鹜 的欠、过和完整约束性的算法。该算法不仅能够给出判断，同时还能够对欠或过 约束的情形进行定位，郯能够给出欠或过约束发生的具体位置。本文主要是以此 算法为基础给出了欠过) 约束且俺约束求解闻题鲢完整纯算法，因此，下面对 基于偶图的d m 分解的判定算法进行详细介绍。 第2 耄凡舞约束求解闷题欠、过、凳整约束性豹判定 i i 甬麓i in n- - 黼 t mi 1 , , 1 1 dii i i i i i 2 ，2 基于偶图的判定算法 2 。2 。1 偶图的嗍分解 首先，回顾一下在本方法中占有核心地位的偶圈的相关知识1 6 2 1 。 令g v e ) 代表一个有向图，其中v 代表顶点的集合，e 代表边的集合。当且 仅当在图g = m e ) 中存在一条从顶点u 到顶点v 的有向路径时，记做在g 上甜专1 ， ( 或者筒记为群v ) 。在图萨 e ) 中，如果有一条边e 从顶点u 指南顶点v ，称 顶点u 是边e 的始顶点，v 是边e 的终顶点。并且称两个顶点u 和v 与该边是相关 联的。如果图c 阳m e ) 中的任意两个顶点都存在一条有向路径，则称这个图是强连 通的。对予图蝌e ) 中的两个顶点u 和v ，如果同时满足矗啼v 和v 豁，剡称顶 点u 和v 是强联通的。 令集合巧是集合v 的子集，则称图g = ( k ，互) 为图g = e ) 的由顶点子集k 导 出的子图，其中置满足e 磊，边e 的始顶点和终顶点都属于集合k 。如果将顶点 的集合v 分成一些子集，并且在每个子集中的任意两个顶点都是强连通的，则 称由顶点子集k 导出的子图q = ( k ，e ) 为图g = e ) 的强连通子图。对于集合v 的 子集k ，如果存在bgk 和巧使得一哆层，称形巧。如果k 巧，称 g g ，。可以证明“s 弦关系是一种偏序关系。 一个偶图是一个有向图，记药b = ( y 4 - ) 矿一；互) ，其中，顶点集合由两个互不相 交的子集v + 和y 一组成，边的集合由所有从集合矿中的顶点指向集合y 一中的顶点 的边组成。偶图b 的个匹配m 是集合e 的一个子集，其中子集m 中的任意两 条边都不能有相同的始顼点。如果一个匹配中所含的边的个数最多翁时候，称这 令匹配是最大匹配