Combining constructive and equational geometric constraint-solving techniques

ABSTRACT

In the past few years, there has been a strong trend towards developing parametric, computer-aided design systems based on geometric constraint solving. An effective way to capture the design intent in these systems is to define relationships between geometric and technological variables. In general, geometric constraint solving including functional relationships requires a general approach and appropriate techniques to achieve the expected functional capabilities. This work reports on a hybrid method that combines two geometric constraint solving techniques: constructive and equational. The hybrid solver has the capability of managing functional relationships between dimension variables and variables representing conditions external to the geometric problem. The hybrid solver is described as a rewriting system and is shown to be correct.

REFERENCES

• 1: AIT-AOUDIA, S., JEGOU, R., AND MICHELUCCI, D. 1993. Reduction of constraint systems. In Compugraphic, A1vor, Portugal, 83-92.
• 2: R. Anderl , R. Mendgen, Parametric design and its impact on solid modeling applications, Proceedings of the third ACM symposium on Solid modeling and applications, p.1-12, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218018]
• 3: BACHMAIR, L. 1991. Proof methods for equational theories. Tech. Rep. Department of Computer Science, SUNY at Stony Brook, Stony Brook, New York.
• 4: BOUMA, W., FUDOS, I., HOFFMANN, C., CAI, J., AND PAIGE, R. 1995. Geometric constraint solver. Comput. Aided Des. 27, 6 (June), 487-501.
• 5: Beat Bruderlin , D. Roller, Geometric Constraint Solving and Applications, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 6: BRUDERLIN, B.D. 1988. Rule-based geometric modelling. Ph.D. Thesis, Institut ffir Informatik der ETH Ztirich.
• 7: J. Van Leeuwen, Handbook of Theoretical Computer Science, Elsevier Science Inc., New York, NY, 1990
• 8: Jean-François Dufourd , Pascal Mathis , Pascal Schreck, Formal resolution of geometrical constraint systems by assembling, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.271-284, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267804]
• 9: FUDOS, I. 1993. Editable representations for 2D geometric design. Master's Thesis, Purdue University, Department of Computer Sciences.
• 10: FUDOS, I. AND HOFFMANN, C.M. 1996. Correctness proof of a geometric constraint solver. Int. J. Comput. Geom. Appl. 6, 4, 405-420.
• 11: David L. Henderson , David C. Anderson, Constraint management for collaborative design, 1996
• 12: Christoph M. Hoffmann , Robert Joan-Arinyo, Symbolic constraints in constructive geometric constraint solving, Journal of Symbolic Computation, v.23 n.2-3, p.287-299, Feb./March 1997 [doi>10.1006/jsco.1996.0089]
• 13: Ching-Yao Hsu, Graph-based approach for solving geometric constraint problems, University of Utah, Salt Lake City, UT, 1996
• 14: JOAN-ARINYO, R. AND SOTO-RIERA, A. 1995a. A rule-constructive geometric constraint solver. Tech. Rep. LSI-95-25-R, Department LiSI, Universitat Polit~cnica de Catalunya, Barcelona.
• 15: JOAN-ARINYO, R. AND SOTO-RIERA, A. 1995b. A set of rules for a constructive geometric constraint solver. Tech. Rep. LSI-95-19-R, Department LiSI, Universitat Polit~cnica de Catalunya, Barcelona.
• 16: JOAN-ARINYO, R. AND SOTO-RIERA, A. 1997a. A correct rule-based geometric constraint solver. Comput. Graph. 21, 5, 599-609.
• 17: R. Joan-Arinyo , A. Soto, A ruler-and-compass geometric constraint solver, Proceedings of the fifth IFIP TC5/WG5.2 international workshop on geometric modeling in computer aided design on Product modeling for computer integrated design and manufacture, p.384-393, January 1997, Airlie, Virginia, United States
• 18: LAMAN, G. 1970. On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 4 (Oct.), 331-340.
• 19: LAMURE, H. AND MICHELUCCI, D. 1998. Qualitative study of geometric constraints. In Geometric Constraint Solving and Applications, B. Brtiderlin and D. Roller, Eds., Springer- Verlag, Berlin, 234-258.
• 20: Lov2{sz, L. AND PLUMMER, M.D. 1986. Matching Theory. Annals of Discrete Mathematics 29, North-Holland, Amsterdam.
• 21: MATA, N. 1997. Solving incidence and tangency constraints in 2D. Tech. Rep. LSI-97-3R, Department LiSI, Universitat Polit~cnica de Catalunya, Barcelona.
• 22: MATHIS, P., SCHRECK, P., AND DUFOURD, J.-F. 1998. YAMS: A multiagent system for 2D constraint solving. In Geometric Constraint Solving and Applications, B. Brfiderlin and D. Roller, Eds., Springer-Verlag, Berlin, 211-233.
• 23: MUROTA, K. 1997. Systems Analysis by Graphs and Matroids. Algorithms and Combinatorics 3, Springer-Verlag, New York.
• 24: Barry K. Rosen, Tree-Manipulating Systems and Church-Rosser Theorems, Journal of the ACM (JACM), v.20 n.1, p.160-187, Jan. 1973 [doi>10.1145/321738.321750]
• 25: ROSENDAHL, M. AND BERLING, R. 1998. Modelling of geometric constraints in CAD-applications. In Geometric Constraint Solving and Applications, B. Brfiderlin and D. Roller, Eds., Springer-Verlag, Berlin, 151-169.
• 26: SOTO-RIERA, A. 1998. Geometric constraint solving in 2D. Ph.D. Thesis, Dept. LiSI, Universitat Polit~cnica de Catalunya, Barcelona (in Catalan).
• 27: VERROUST, A., SCHONEK, F., AND ROLLER, D. 1992. Rule-oriented method for parameterized computer-aided design. Comput. Aided Des. 24, 10 (Oct.), 531-540.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
  I.3 COMPUTER GRAPHICS

  J. Computer Applications

General Terms:
Algorithms, Design

Keywords:
canonical forms, constructive techniques, equational techniques, geometric constraint solving, rewriting systems