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

Planning and Decomposition of Directed Geometric Constraint Graph

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

For a geometric constraint system based on directed graph,matching direction and distribution of constraints and scale of strongly-connected sub-graphs in the directed graph affect the efficiency of constraint solving directly.How to plan the constraint solving properly and get correct and efficient solving sequence is an important subject in the research of constraint decomposition.In this paper,an optimal method for constraint decomposition is presented.It optimizes initial matching direction of any newly added constraint.For strongly-connected sub-graphs created during the course of construction of directed constraint graph,the algorithm proposed adaptively improves the distribution of constraints and reduces the scale of the strongly-connected sub-graphs by adjusting matching directions of constraints.By these methods,it tries to get a correct and efficient constraint solving sequence.In addition,a method of singularity analysis for geometric constraint system is also advanced based on the optimal decomposition,and a concrete algorithm of singularity judgment is presented.