Similar articles

Abstract: This paper applies genetic simulated annealing algorithm (SAGA) to solving geometric constraint problems. This method makes full use of the advantages of SAGA and can handle under-/over- constraint problems naturally. It has advantages (due to its not being sensitive to the initial values) over the Newton-Raphson method, and its yielding of multiple solutions, is an advantage over other optimal methods for multi-solution constraint system. Our experiments have proved the robustness and efficiency of this method.

[1]Aldefeld, B., 1988. Variation of geometries based on a geometric-reasoning method. CAD, 20(3):117-126.

[2]Borning, A.H., 1981. The programming language aspects of ThingLab, a constraint oriented simulation laboratory. ACM TOPLAS, 3(4):353-387.

[3]Bose, N.K., 1985. Multidimensional Systems Theory. D. Reidel Publishing Co., p.184-232.

[4]Bouma, W., Fudos, I., Hoffmann, C.M., Cai, J. and Paige, J., 1994. A geometric contraint solver. CAD, 27:487-501.

[5]Bruderlin, B., 1990. Symbolic Computer Geometry for Computer Aided Geometric Design. In: Advances in Design and Manufacturing Systems, NSF conference, AZ, USA.

[6]Davis, L., 1991. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.

[7]David, P. and Borut, Z., 2001. A Geometric Constraint Solver With Decomposable Constraint Set. Skala, V.Eds., The 9th International Conference in Central Europe on Computer Graphics and Visualisation'01 - WSCG'01, Plzen, Czech Republic, University of West Bohemia, 2:222-229.

[8]De Jong, K., 1975, An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD Dissertation, University of Michigan. Dissertation Abstract International, 36(10), 5140B.(University Microlms No.76-9381).

[9]Dennis, J.E. and Schnabel, R.B., 1983. Numerical Methods for Unconstrainted Optimization and Nonlinear Equations. Prentice-Hall Inc., New Jersey.

[10]Durand, C., 1998. Symbolic and Numerical Techniques for Constraint Solving. PhD thesis, Department of Computer Sciences, Purdue University, IN, USA.

[11]Durand, C. and Hoffmann, C.M., 1999. Variational Constraints in 3D. Proc. Intl Conf on shape Modeling and Appl, Aizu, Japan, p.90-97.

[12]Durand, C. and Hoffmann, C.M., 2000. A systematic framework for solving geometric constraint analytically. J. of Symbolic Computing,30:483-520.

[13]Emiris, I.Z. and Verschelde, J., 1997. How to count efficiently all affine roots of a polynomial system. Discrete Applied Mathematics, 93(1).

[14]Fudos, I., 1993a. Editable Representations for 2D Geometric Design, Master's Thesis, Purdue University, Dept. of Computer Science.

[15]Fudos, I. and Hoffmann, C.M., 1993b. Correctness proof of a geometric constraint solver. Intl. J. Comp Geometry and Applic, 6: 405-420.

[16]Fudos, I. and Hoffmann, C.M., 1997. A graph-constructive approach to solving systems of geometric constraints. ACM Transactions on Graphics,16:179-216.

[17]Ge, J.X., Gao, X.S. and Chou, S.C., 2000. Geometric constraint satifaction using optimization methods. Computer Aided Design,31:867-879.

[18]Goldberg, D.E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley Publishing Company, New York, p.1-88.

[19]Hoffmann, C.M. and Vermeer, P., 1995a. Geometric Constraint Solving in R² and R³. In: Computing in Eulidean Geometry Second Edition. World Scientific Publishing, Singapore, p.266-298.

[20]Hoffmann, C.M. and Vermeer, P., 1995b. A Spatial Constraint Problem. In: Computational Kenematics's 95,J.P. Merlet and B.Ravani,Eds.,Kluwer Academic Publ.,p.83-92.

[21]Hoffmann, C.M. and Joan-arinyo, R., 1997. Symbolic constraints in constructive geometry. Journal of Symbolic Computation,23:287-300.

[22]Hoffmann, C.M. and Yuan, B., 2000. On Spatial Constraint Solving Approaches. Proc.ADG 2000, Springer verlag, ETH Zurich.

[23]Ivan, S.E., 1963. Sketchpad: A Man-Machine Graphical Communication System. In: Proceedings-Spring Joint Computer Conference, Michigan, 23:329-346.

[24]Joan-Arinyo, R. and Soto, A., 1997a. A correct rule-based geometric constraint solver. Computer and Graphics,21(5):599-609.

[25]Joan-Arinyo, R. and Soto, A., 1997b. A Ruler-and-Compass Geometric Constraint Solver. In: M.J., Pratt,R.D., Sriram and M.J., Wozny,editors,Product Modeling for Computer Integrated Design and Manufacture, Chapman and Hall,London, p.384-393.

[26]Kondo, K., 1992. Algebraic method for manipulation of dimensional relationships in geometric models. CAD,24(3):141-147.

[27]Kirkpatrick, S., Gelatt Jr., C.D. and Vecchi, M.P., 1983. Optimization by simulated annealing. Science, 220:671-680.

[28]Lazard, D., 1999. On theories of triangular sets. Journal of Symbolic Computation, 28:105-124.

[29]Michalewicz, Z., Krawczyk, J., Kazemi, M. and Janikow, C., 1990. Genetic Algorithms and Optimal Control Problem. In: Proc. of 29th IEEE Conf. On Decision and Control,p.1664-1666.

[30]Morgan, A., 1992. Polynomail Continuation and its Relatoinship to the Symbolic Reduction of Polynomial Systems. In: B.Donald,D.Kapur, and J.Mundy,editors,Symbolic and Numerical Computation for Artificial Inteligence. Academic Press.

[31]Song, P., Tang, M. and Dong, J.X., 2000. A Constraint Solving Approach Based on Graph Decomposition. China Graph'2000, Hangzhou.

[32]Sturmfels, B., 1997. Introduction to Resultants. Lecture Notes at the AMS Short Course on Applications of Computational Algebraic Geometry,San Diego.

[33]Verroust, A., Schonek, F. and Roller, D., 1992. Rule-oriented method for parametrized computer-aided design. Computer Aided Design,24(10):531-540.

[34]Wang, D., 1998. Decomposing polynomial systems into simple systems. Journal of Symbolic Computation,25:295-314.

[35]Wu, W.T., 1986. Principles of mechanical theorem proving. J. of Automated Reasoning,2:221-252.