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

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

一种基于有向图的几何约束系统分解方法

1引言 约束分解是几何约束满足问题(GCSP)研究的一个重要内容.此前已经有很多工作实现了将GCSP向非线性方程组求解的转化,并研究了约束系统的表达和分解的问题[1-4].特别是Kramer[6]以机构学为背景,提出了几何约束系统的无向图表达.后来,董金祥[10]将约束无向图转换成有向图,为构造全参数化的图形奠定了基础;J.Y Lee[1]则针对尺规构造图形进一步发展了基于自由度分析的图规约方法.但是在上述的研究中,对欠约束几何系统的分析比较欠缺.