一种基于Grbner基和有向图的几何约束求解方法

A Geometric Constraint System Solving Approach Based on Grbner Basis and Graph Analysis

方程组规模大和约束一致性分析方法的欠缺影响基于Gr?bner基的代数法在约束求解中的应用。针对应用有向图进行约束分解产生的强连通分量不饱和问题,提出进行强连通分量内变量匹配,以消去自由实体,从而使强连通分量趋于饱和,方程组得以简化。并以此为基础提出基于Gr?bner基进行约束一致性判别的方法。以含有冗余约束的三角形为例阐述了约束一致性分析和求解的过程。

The application of Grobner basis in geometric constraint system solving is restricted by two facts： the large scale of equations and the lack of consistency detection method. Bipartite graph matching on variable level is adopted to simplify the equations; Then a consistency detection method based on Grobner basis is presented. The process of consistency detection and constraint system solving is illustrated with an inconsistent triangle construction.