A constraint-based dynamic geometry system

ABSTRACT

Dynamic geometry systems are tools for geometric visualization. They allow the user to define geometric elements, establish relationships between them and explore the dynamic behavior of the remaining geometric elements when one of them is moved. The main problem in dynamic geometry systems is the ambiguity that arises from operations which lead to more than one possible solution. Most dynamic geometry systems deal with this problem in such a way that the solution selection method leads to a fixed dynamic behavior of the system. This is specially annoying when the behavior observed is not the one the user intended.

In this work we propose a modular architecture for dynamic geometry systems built upon a set of functional units which will allow to apply some well known results from the Geometric Constraint Solving field. A functional unit called filter will provide the user with tools to unambiguously capture the expected dynamic behavior of a given geometric problem.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: B. Aldefeld, Variation of geometrics based on a geometric-reasoning method, Computer-Aided Design, v.20 n.3, p.117-126, April, 1988 [doi>10.1016/0010-4485(88)90019-X]
• 3: Allen, R., and Trilling, L. 1997. Dynamic geometry and declarative geometric programming. In Geometry Turned On. Mathematical Association of America.
• 4: Allen, R., Idt, J., and Trilling, L. 1993. Constraint based automatic construction and manipulation of geometric figures. In 13th International Joint Conference on Artificial Intelligence.
• 5: Allen, R., Broquin, P., Channac, S., and Trilling, L. 2000. Issues in declarative dynamic geometry system design and implementation. In 5th ERCIM Working Group on Constraints.
• 6: Baulac, Y., Bellemain, F., and Laborde, J.-M. 1992. Cabri - the Interactive Geometry Notebook. Brooks/Cole Publishing Company.
• 7: Denis Bouhineau , Stéphane Channac, La programmation loique par contraintes pour l'aide à l'enseignant, Proceedings of the Third International Conference on Intelligent Tutoring Systems, p.333-342, June 12-14, 1996
• 8: Bouohineau, D. 1995. Vers une approche déclarative pour les logiciels de dessins géométriques. In 4èmes Journées Environements Interactifs d'aprentissage avec ordinaleur.
• 9: Bouma, W., Fudos, I., Hoffmann, C., Cai, J., and Paige, R. 1995. Geometric constraint solver. Computer Aided Design 27, 6 (June), 487--501.
• 10: Brüderlin, B. 1990. Symbolic computer geometry for computer aided geometric design. In Advances in Design and Manufacturing Systems, Proceedings NSF Conference.
• 11: Channac, S. 1996. Techniques d'intelligence artificielle pour l'excution de programmes logiques gomtriques. In Journes Infografie Intractive et Intelligence Artificielle.
• 12: Ulrich H. Kortenkamp , Jürgen Richter-Gebert, The Interactive Geometry Software Cinderella.2, Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• 13: C. Essert-Villard , P. Schreck , J.-F. Dufourd, Sketch-based pruning of a solution space within a formal geometric constraint solver, Artificial Intelligence, v.124 n.1, p.139-159, Nov 2000 [doi>10.1016/S0004-3702(00)00061-8]
• 14: Freixas, M., Joan-Arinyo, R., Soto-Riera, A., and Vila-Marta, S., 2008. SolBCN a constraint-based two dimensional geometric editor, february. http://floss.lsi.upc.edu/wiki/solBCN.
• 15: Fudos, I., and Hoffmann, C. 1996. Correctness proof of a geometric constraint solver. International Journal of Computational Geometry and Applications 6, 4, 405--420.
• 16: Ioannis Fudos , Christoph M. Hoffmann, A graph-constructive approach to solving systems of geometric constraints, ACM Transactions on Graphics (TOG), v.16 n.2, p.179-216, April 1997 [doi>10.1145/248210.248223]
• 17: GeoGebra, July 2007. http://www.geocebra.org/cms.
• 18: Heydon, A., and Nelson, G. 1994. The Juno-2 constraint-based drawing editor. Research Report 131a, Digital Systems Research Center, December.
• 19: 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]
• 20: Hoffmann, C., and Joan-Arinyo, R. 2005. A brief on constraint solving. Computer-Aided Design and Applications 2, 5, 655--663.
• 21: Christoph M. Hoffman , Andrew Lomonosov , Meera Sitharam, Decomposition plans for geometric constraint problems, part II: new algorithms, Journal of Symbolic Computation, v.31 n.4, p.409-427, April 1, 2001 [doi>10.1006/jsco.2000.0403]
• 22: Christoph M. Hoffman , Andrew Lomonosov , Meera Sitharam, Decomposition plans for geometric constraint problems, part II: new algorithms, Journal of Symbolic Computation, v.31 n.4, p.409-427, April 1, 2001 [doi>10.1006/jsco.2000.0403]
• 23: Jackiw, N. 1991--1995. The Geometer's Sketchpad. Key Curriculum Press, Berkeley.
• 24: Jerman, C., Trombettoni, G., Neveu, B., and Mathis, P. 2006. Decomposition of geometric constraint systems: A survey. International Journal of Computational Geometry and Applications 16, 379--414.
• 25: R. Joan-Arinyo , A. Soto-Riera, Combining constructive and equational geometric constraint-solving techniques, ACM Transactions on Graphics (TOG), v.18 n.1, p.35-55, Jan. 1999 [doi>10.1145/300776.300780]
• 26: Joan-Arinyo, R., and Soto, A. 1997. A correct rule-based geometric constraint solver. Computer & Graphics 21, 5, 599--609.
• 27: Robert Joan-Arinyo , Antoni Soto-Riera , Sebastià Vila-Marta , Josep Vilaplana, On the Domain of Constructive Geometric Constraint Solving Techniques, Proceedings of the 17th Spring conference on Computer graphics, p.49, April 25-28, 2001
• 28: Joan-Arinyo, R., Luzón, M., and Soto, A. 2003. Genetic algorithms for root multiselection in constructive geometric constraint solving. Computer & Graphics 27, 1, 51--60.
• 29: Kortenkamp, U. 1999. Foundations of Dynamic Geometry. PhD thesis, Swiss Federal Institute of Technology Zurich.
• 30: Laborde, J.-M., and Bellemain, F. 1993--1998. Cabri-Geometry II. Texas Instruments and Universit Joseph Fourier.
• 31: Mata, N. 2000. Constructible Geometric Problems with Interval Parameters. PhD thesis, Dept. LiSI, Universitat Politècnica de Catalunya.
• 32: Greg Nelson, Juno, a constraint-based graphics system, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.235-243, Jul. 1985
• 33: J. C. Owen, Algebraic solution for geometry from dimensional constraints, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.397-407, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112573]
• 34: Ulrich H. Kortenkamp , Jürgen Richter-Gebert, The Interactive Geometry Software Cinderella.2, Springer-Verlag New York, Inc., Secaucus, NJ, 2007
• 35: Vila, S. 2003. Contribution to Geometric Constraint Solving in Cooperative Engineering. PhD thesis, Department Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya.
• 36: Winroth, H. 1999. Dynamic Projective Geometry. PhD thesis, Stockholms Universitet.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional 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

Keywords:
dynamic geometry, geometric constraint solving