Research On Algorithm Of Geometric Constraints Solving Based On Bipartite Graph And Numerical Methods

Development and application level of computer aided design has become one of important criteria, that is used to measure a country’s technological modernization and industrial modernization level. The geometric constraint solving techniques is one of core technology of modern modeling technology. In the present paper several issues concerning on geometry constraint solving are addressed as follows.First of all, a bipartite graph decomposition is used to determine the category of geometric constraint problems. This algorithm can not only determine the geometric constraint problem is under-, over-or well-constrained, but also to determine under-constrained and over-constrained geometric elements. A maximum match solving algorithm based on adjacency matrix is proposed to advance the efficiency of maximum match solving.Secondly, a algorithm is proposed to solve the under-constrained and over-constrained geometric constraint problem. This algorithm first solve the well-constrained geometric constraint sub-problem, and then solve the over-constrained geometric constraint sub-problems based on part of graphics, and then solve under-constrained geometric constraint sub-problems. A over-constrained solving algorithm and a under-constrained solving algorithm are proposed to automatically remove and add geometric constraints. This algorithm can transform under-, over-constrained geometric constraint problem into well-constrained geometric constraint problem.Again, for the problem of slow convergence rate in the late stage of particle swarm optimization algorithm, a PSO-BFGS algorithm is proposed to advance convergence rate. PSO-BFGS algorithm is not only has global search capability, as well as rapid local convergence. What more, PSO-BFGS algorithm dose not sensitive to initial value. Compared with particle swarm optimization algorithm, convergence rate of PSO-BFGS algorithm greatly improved. In the end of this article, PSO-BFGS algorithm and particle swarm optimization algorithm has been tested with geometric constraint problem instance, and the test results are compared and analyzed. The result shows that PSO-BFGS algorithm has faster convergence rate of solving geometric constraint problem.The results of this paper have certain theoretical significance and application value. It makes the geometric constraint solving techniques becoming more perfection.