基于二部图模型的欠、过约束几何约束系统的识别和处理

Identification and process of under-and over-constrained geometric constraint systems based on bipartite graph model

采用表达几何基元参数和基本几何约束的二部图模型表示几何约束系统,提出一种新的基于二部图最大匹配的几何约束求解方法,并由二部图分解法对几何约束系统的欠、过约束属性进行识别。通过加入几何约束优先级,改进几何约束装配机制来处理欠约束几何约束系统;当处理过约束的几何约束系统时,由改进的人工蜂群算法识别一致性与非一致性过约束并对识别的过约束子域进行有效处理。研究结果表明,本文基于新的二部图模型的几何约束求解方法是行之有效的。

In this paper,ageometric constraint system is represented by a bipartite graph model,which expresses geometric primitive parameters and basic geometric constraints,and a new Geometric Constraint Solving(GCS)method based on the maximum matching of bipartite graph is proposed.The under-and over-constrained sub-domains are identified by using the bipartite graph decomposition method.An under-constrained sub-domain is processed by introducing the geometric constraint priority and improving the geometric constraint assembly mechanism.The consistent and inconsistent over-constraints are identified by the modified artificial bee colony algorithm,and the identified overconstrained sub-domain is also effectively processed.Research results show that the GCS method based on the new bipartite graph model is effective.