二维几何约束求解器

开发了一个二维几何约束求解器.该求解器是新一代智能CAD系统的核心,它采用了基于图和规则的几何推理方法,高效、稳定、实用.论文提出了几何约束模型及其约束图表示,深入介绍了基于点刚体归约的几何推理算法,描述了求解器的体系结构.     

基于改进鱼群算法的几何约束求解

几何约束求解是CAD建模中的关键技术。针对求解质量不高和求解速度慢的问题,进行了研究。提出了一种鱼群算法和混沌算法相结合的几何约束求解方法。首先,将CAD模型中的几何约束关系表示为一组代数方程组;然后,利用代数方程组来构造目标函数。将几何约束求解问题转换为目标函数的优化问题。最后,使用混沌算法来改进鱼群算法以寻找目标函数的最优解。实验结果表明：该方法可以有效地解决几何约束问题。     

基于有向图的二维约束求解算法研究

针对过约束、几何完全定义状态判定和约束求解效率等问题,提出了基于约束图,利用自由度理论和约束冲突机制,通过反向约束方向平衡约束,进而通过排序进行约束求解的算法。算法采用约束图记录约束和几何的关系;通过约束平衡的方法进行过约束和几何完全定义的判定;采用排序求解方法,将庞大计算问题转化为一组相对简单的计算问题。算法已得到初步应用,对过约束和几何完全定义状态的判定有明显的效果,而且提高了约束求解效率。     

基于雁群启示的粒子群优化算法的几何约束求解

几何约束是约束求解技术中最关键的问题之一.求解一个几何约束问题的最终目的是确定几何图形中每一个几何体的具体坐标位置.几何约束问题可以等价为求解非线性方程组问题.约束问题转化为一个优化问题.本文采用基于雁群启示的粒子群优化算法来求解该问题.该算法受雁群飞行特征启发,一方面将粒子排序,每个粒子跟随其前面那个较优粒子飞行,保持了多样性;另一方面使每个粒子利用更多其他粒子的有用信息,粒子之间的竞争被增强.两个方面的结合将平衡速度和精度之间的矛盾.实验表明,该方法可以提高几何约束求解的效率和收敛性.     

几何约束求解的去并拟合方法

依据有向图理论提出了去并拟合方法,由此导出了对于几何约束求解问题的去并拟合的并行处理及串行处理策略,进而得到了一套求解几何约束问题的完备算法。通过将该理论引入到参数化CAD的设计中,使得在算法复杂度增加不大的情况下,几何自动作图的范围大大拓宽。还将其应用于智能动态几何软件的设计中,取得了较好的结果。     

几何约束求解的简化迭代算法

针对几何约束系统图分解中复合顶点的求解问题,提出复合顶点的图分解算法和等价自由变量的简化迭代求解算法.通过去除复合顶点部分边界约束对复合顶点进行图分解,对求解序列中的欠约束顶点添加等价自由变量、以等价自由变量的部分迭代求解、替代系统的整体数值求解,以提高求解效率和稳定性.该算法具有很强的通用性,并在实际应用中得到验证.     

D-优化算法实现几何约束问题的重组

当前对几何约束求解普遍使用建设性方法,按照先分解后重组的方式进行求解.但多数情况下这些方法产生非线性方程数量多,计算量大,解决问题较为复杂.此处提出D-优化算法通过将欠约束子问题分离的方法,利用自定义的分离规则,将问题分解为若干单位问题.单位问题规模较小,求解难度较低.实验证明,该优化方法可有效降低问题求解的复杂程度.     

面向欠约束几何系统的一种同伦求解方法

针对几何约束系统的数值求解过程中，经常发生的数值不稳定性问题，构造了一种面向欠约束系统的同伦方法，并将其与现有的求解与分解方法有机地结合起来，提出了一种牛顿－同伦混合方法，在牛顿迭代失败的位置自动调用欠约束同伦法，既提高了几何约束求解器的效率，同时又保证了求解的效率。     

动态种群划分量子遗传算法求解几何约束

几何约束问题的约束方程组可转化为优化模型,因此约束求解问题可以转化为优化问题。针对传统量子遗传算法个体间信息交换不足,易使算法陷入局部最优的缺点,提出了动态种群划分量子遗传算法（dynamic population divided quantum genetic algorithm,DPDQGA）,并将其应用于几何约束求解中。该算法种群中的个体按照一定规则自发地进行信息交换。在每一代进化的开始阶段,分别对两个初始种群中的个体计算个体适应度。将两个种群合并,使用联赛选择的方法为种群中的个体打分,并按照得分对种群进行排序。最后将合并的种群重新划分为两个子种群。实验表明,基于动态种群划分的量子遗传算法求解几何约束问题具有更好的求解精度和求解速率。     

三维几何约束系统的等价性分析

针对过约束、完整约束和欠约束三维几何约束系统的求解问题,提出了等价性分析方法.该方法基于三维几何约束系统的内在等价性,充分挖掘几何领域知识,依据拆解约束闭环、缩减约束闭环和析出约束闭环等原则,采用等价约束替换来处理几何约束闭环问题,优化几何约束图的结构,实现几何约束系统的优化分解.最后用多个实例验证了该方法的正确性和有...     

几何约束有向图的规划分解研究

在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。     

Geometric constraint solving with geometric transformation

This paper proposes two algorithms for solving geometric constraint systems. The first algorithm is for constrained systems without loops and has linear complexity. The second algorithm can solve constraint systems with loops. The latter algorithm is of quadratic complexity and is complete for constraint problems about simple polygons. The key to it is to combine the idea of graph based methods for geometric constraint solving and geometric transformations coming from rule-based methods.     

一种基于图分解的几何约束求解方法

为了提高几何约束求解的效率和鲁棒性 ,对基于图的构造方法进行了改进 ,即加入虚约束进行扩展和过约束问题的一致性判定 ,提出了一种基于图分解的方法 ,用此方法可以处理包括完全约束、过约束和欠约束等多种情况的约束求解问题 ,另外 ,在该方法中还通过引入分解树将约束求解的范围由整体下降到局部 ,使大部分求解过程能够采用几何求解实现 ,提高了求解和后续修改的效率 ,通过实验数据测试证明 ,该方法对于大型约束求解问题可以达到实时处理的效果 ,具有较强的实用性     

三维装配几何约束组合的分类求解策略

针对两个刚体之间的三维几何约束求解问题,依据几何约束的参数结构 分析了角度约束和距离约束的解耦性,给出了角度约束和距离约束可解耦求解的条件;然后 对两个刚体之间的几何约束进行组合分析,总结出约束度不小于2 的几何约束构成的组合只 有几十种,且均可采用几何推理方法进行求解;最后阐述了附加方向约束、冗余约束和矛盾 约束对数值求解的不利影响,提出了三维几何约束组合的分类求解策略,并用实例验证了该 求解策略的有效性。     

用于三维几何约束求解的分组重写方法

提出一种基于分组重写的解决三维几何约束的方法,原有的算法在解决大型系统几何约束求解时效率较低,系统开销较大,并且由于算法规则的局限性,使得很多复杂系统无法解决,包括三维几何约束问题。该方法提出了两种新的分组表示类型,拓展子集和放射子集,使得分组更加直观,准确,并有效地提高了求解效率,减小了开销,方法在三维领域更能发挥其作用,能够满足计算机辅助造型中集合造型的需求。     

三维几何约束求解的变分算法

研究了运动学变分原理在三维几何约束求解中的应用，提出了变分求解算法．该算法采用相对坐标，将求解域从笛卡儿空间转换到相对坐标空间．对于约束开环，依次选取相对坐标即可获得满足几何约束的刚体位姿；对于约束闭环，通过切断闭环铰，将约束闭环转化为等价的广义开环与切断铰约束代数方程，其切断铰约束代数方程的相对坐标雅克比矩阵解析式可通过变分关系显式获得．最后通过实例验证，说明该算法具有较高的求解效率与稳定性．