二、三维几何约束问题的冗余性分析与求解方法研究

摘要

计算机辅助设计(CAD)技术的发展和应用水平已成为衡量一个国家科技现代化和工业现代化水平的重要标准之一。几何约束求解技术也随着CAD而发展起来，并逐渐成为目前的研究热点。本文结合图论方法和数值方法来求解几何约束问题。本文求解几何约束问题的思路:首先对二、三维几何约束问题进行统一建模;其次利用图论方法对几何约束问题的冗余性进行分析、判断及处理;最后将几何约束约束问题转化为优化问题，利用优化算法进行求解。 首先，实现几何约束系统的首要任务就是解决系统的建模问题，为了实现几何约束的统一表达，首先要实现几何实体的统一表达，鉴于欧拉角和卡尔丹角均引入超越函数，本文采用基于欧拉参数的几何实体统一表达。面对复杂几何实体及几何约束的表达问题，可以将其分解为若干基本几何实体或基本几何约束的组合来表达。本文用基于偶图的模型来描述几何约束系统，针对传统建模方法只粗略的描述实体与约束的关系，仅能判定约束系统结构上的欠、过约束关系的缺陷，本文改进传统建模方法的思路，使模型可以更加精准的描述实体中的具体参数与基本约束之间的关系，达到判定约束系统几何上的欠、过约束关系。 其次，本文利用偶图DM分解算法来判定几何约束问题的欠、过约束性。求解偶图最大匹配时，针对传统算法难理解、实现复杂、时间复杂度大的缺点，本文提出以结点度为优先级的最优选择算法，进而降低求解最大匹配的时间复杂度。在处理欠约束几何约束问题时，为提高欠约束处理速度，设置添加约束优先级，由系统自动选择添加约束;在处理过约束几何约束问题时，首先判定过约束的类型，针对传统符号判定算法计算量大、实现复杂及求解速度慢的缺点，本文采用改进人工蜂群算法来判定过约束的一致性与非一致性，不同类型的过约束问题采用不同的处理方法。最后通过实例证明了本文欠、过约束判定算法及处理算法的可行性。 最后，求解完备约束的几何约束问题，将几何约束问题转化为单目标优化问题，利用智能算法求解，本文提出利用人工蜂群算法来求解几何约束问题。针对传统人工蜂群算法存在“早熟”以及收敛速度相对较慢的缺陷与问题，本文对传统人工蜂群算法进行了改进，改进人工蜂群算法中，雇佣蜂在搜索阶段进行向最优值的多维递进搜索来代替传统人工蜂群算法的随机一维搜索，并采用一种新的自适应的非雇佣蜂跟随概率计算方法，且动态调整雇佣蜂的淘汰频率。通过仿真实例测试，对比改进人工蜂群算法、经典粒子群算法与传统人工蜂群算法的实验数据表明，改进人工蜂群算法综合性能明显优于后两者，具有收敛快、求解精度高、效率高、稳定性好的优点。

目录

声明

摘要

1．1研究意义

1．2 CAD技术发展历程及现状

1．3参数化与变量化设计技术

1．4几何约束求解技术

1．4．1数值方法

1．4．2符号代数法

1．4．3基于规则的方法

1．4．4基于图论的方法

1．5论文的主要研究内容和组织结构

第2章几何约束系统的统一建模

2．1引言

2．2几何约束系统的相关知识

2．3二维几何约束系统的表达

2．3．1二维几何元素的表达

2．3．2二维几何约束的表达

2．4三维几何约束系统的表达

2．4．1欧拉参数

2．4．2三维几何实体的欧拉参数表达

2．4．3三维几何约束的欧拉参数表达

2．5几何约束系统的建模

2．6本章小结

第3章几何约束系统的冗余性分析

3．1引言

3．2几何约束系统的冗余性判定

3．2．1偶图

3．2．2偶图最大匹配

3．2．3偶图的DM分解

3．2．4基于偶图的判定算法

3．3几何约束系统的冗余性处理

3．3．1欠约束几何约束问题的处理

3．3．2过约束几何约束问题的处理

3．4实例分析

3．5本章小结

第4章基于改进人工蜂群算法的几何约束求解

4．1引言

4．2几何约束问题的优化模型

4．3人工蜂群算法

4．3．1人工蜂群算法的基本原理

4．3．2人工蜂群算法的步骤

4．3．3人工蜂群算法的改进

4．4仿真实验

4．4．1测试实例描述

4．4．2实验结果及分析

4．5本章小结

5．1总结

5．1展望

参考文献

致谢

攻读硕士学位期间的论文项目情况