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

A Decomposition Method for Directed Graph Based Geometric Constraint System

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

In a directed geometric constraint graph, all vertices in each strongly-connected sub-graph should be solved simultaneously. So, the scales of strongly-connected sub-graphs in the directed constraint graph directly affect the efficiency of constraint solving. However, how to furthest reduce the size of the largest subsystem that is simultaneously solved has been proved to be NP hard in general. In this paper an alternative decomposition method is presented for both under-constrained and well-constrained systems. It tries to find a sub-optimized solution instead of the most optimized one by adaptively adjusting the distribution of constraints. By the method the scales of strongly-connected sub-graphs of the directed constraint graph are greatly reduced and a more optimized and rational solving sequence is obtained.