Several Geometric Constraint Solving Algorithm

The status of application and development has been one of the important scales to measure the modernization of science and technology and industry of a nation. The development of CAD has been provided with wider stage and better opportunity from the emergence of the technology of parameter to the application of the technology of variable. The geometric constraint solving has been an essential part for the development of the technology of parameter and the technology of variable, so it is significant for researching on geometric constraint solving.The thesis introduces the system of CAD at first including the history, the actuality and the development. And then the concept of the problem of geometric constraint solving and the basic four methods for solving this problem are brought in: the method of algebra, the method of symbol algebra, the method of logical inference and term rewriting and method of graphic construction.Aiming at present systems, there are constraints among points, lines, planes and angles but the constraints for parameter conic are rare. This thesis is focus on how to how to construct conic blending arcs from constraints using a rational parametric representation-rational quadratic Bezier, that combines two separate lines and satisfy the constraints: traverse a fixed point, tangency to or distance from a line. Apart from a constructive method, this thesis also develops an algebra method to solving this problem.This thesis riches the methods of solving geometric constraints using optimal methods. Firstly, the BFGS method is introduced and then uses this method to apply into a geometric constraint problem. But the result will be trapped into a local optimal point if only the BFGS method is used. So a hybrid method is brought out through joins a chaos optimization method to solving the problems of geometric constraints. This hybrid method can keep from trapping into a local optimal result and finally find out a global result.The evident merit of solving geometric constraint using optimization is theimplication that this method can handle the under-constrained and the over-constrained problems. But it has the disadvantage that only an optimal result can be found when using the hybrid method. In order to settle this shortcoming, this thesis brings the genetic algorithms into solving the geometric constraint problems. And a case is presented using genetic simulated annealing algorithms. This algorithm remedies the shortcoming of hybrid method but can't find all optimal results at a time except in repetitious calculation. For the sake of finding all the optimal results, the concept of Niche is introduced and put into use. This new algorithm can solve the problem of multi-results under well-constraint geometric constraints well.