A modular geometric constraint solver for user interface applications

ABSTRACT

Constraints have been playing an important role in the user interface field since its infancy. A prime use of constraints in this field is to automatically maintain geometric layouts of graphical objects. To facilitate the construction of constraint-based user interface applications, researchers have proposed various constraint satisfaction methods and constraint solvers. Most previous research has focused on either local propagation or linear constraints, excluding more general nonlinear ones. However, nonlinear geometric constraints are practically useful to various user interfaces, e.g., drawing editors and information visualization systems. In this paper, we propose a novel constraint solver called Chorus, which realizes various powerful nonlinear geometric constraints such as Euclidean geometric, non-overlapping, and graph layout constraints. A key feature of Chorus is its module mechanism that allows users to define new kinds of geometric constraints. Also, Chorus supports "soft" constraints with hierarchical strengths or preferences (i.e., constraint hierarchies). We describe its framework, algorithm, implementation, and experimental results.

REFERENCES

• 1: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• 2: Alan Borning , Kim Marriott , Peter Stuckey , Yi Xiao, Solving linear arithmetic constraints for user interface applications, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.87-96, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263518]
• 3: Carter, E. Simulated Annealing Package. http://www.taygeta.com/annealing/.
• 4: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987
• 5: Bjorn N. Freeman-Benson , John Maloney , Alan Borning, An incremental constraint solver, Communications of the ACM, v.33 n.1, p.54-63, Jan. 1990 [doi>10.1145/76372.77531]
• 6: Arne Frick , Can Keskin , Volker Vogelmann, Integration of Declarative Approaches, Proceedings of the Symposium on Graph Drawing, p.184-192, September 18-20, 1996
• 7: Ioannis Fudos , Christoph M. Hoffmann, Constraint solving for computer-aided design, 1995
• 8: Michael Gleicher, A graphics toolkit based on differential constraints, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.109-120, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168653]
• 9: Goffe, B. SIMANN. Netlib. http://www.netlib.org/opt/simann.f.
• 10: Weiqing He , Kim Marriott, Constrained Graph Layout, Proceedings of the Symposium on Graph Drawing, p.217-232, September 18-20, 1996
• 11: F. Herrera , M. Lozano , J. L. Verdegay, Tackling Real-Coded Genetic Algorithms: Operators and Tools for Behavioural Analysis, Artificial Intelligence Review, v.12 n.4, p.265-319, Aug. 1, 1998 [doi>10.1023/A:1006504901164]
• 12: Heydon, A., and Nelson, G. The Juno-2 constraintbased drawing editor. Research Report 131a, Digital Systems Research Center, 1994.
• 13: Hiroshi Hosobe, A Scalable Linear Constraint Solver for User Interface Construction, Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming, p.218-232, September 18-21, 2000
• 14: Takeo Igarashi , Satoshi Matsuoka , Sachiko Kawachiya , Hidehiko Tanaka, Interactive beautification: a technique for rapid geometric design, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.105-114, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263525]
• 15: T. Kamada , S. Kawai, An algorithm for drawing general undirected graphs, Information Processing Letters, v.31 n.1, p.7-15, April 1989 [doi>10.1016/0020-0190(89)90102-6]
• 16: Tomihisa Kamada , Satoru Kawai, A general framework for visualizing abstract objects and relations, ACM Transactions on Graphics (TOG), v.10 n.1, p.1-39, Jan. 1991 [doi>10.1145/99902.99903]
• 17: Kitano, H., Ed. Genetic Algorithms. Sangyo-Tosho, 1993. In Japanese.
• 18: Glenn A. Kramer, A geometric constraint engine, Artificial Intelligence, v.58 n.1-3, p.327-360, Dec. 1992 [doi>10.1016/0004-3702(92)90012-M]
• 19: Kim Marriott , Sitt Chen Chok , Alan Finlay, A Tableau Based Constraint Solving Toolkit for Interactive Graphical Applications, Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming, p.340-354, October 26-30, 1998
• 20: Masui, T. Graphic object layout with interactive genetic algorithms. In Proc. IEEE VL, 1992, 74-80.
• 21: Greg Nelson, Juno, a constraint-based graphics system, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.235-243, July 1985
• 22: 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]
• 23: Kathy Ryall , Joe Marks , Stuart Shieber, An interactive constraint-based system for drawing graphs, Proceedings of the 10th annual ACM symposium on User interface software and technology, p.97-104, October 14-17, 1997, Banff, Alberta, Canada [doi>10.1145/263407.263521]
• 24: Saltire Software. Constraint geometry. http://www.saltire.com/constraints.html.
• 25: Michael Sannella, Skyblue: a multi-way local propagation constraint solver for user interface construction, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.137-146, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192485]
• 26: Spellucci, R DONLP2. Netlib. http://www.netlib.org/opt/donlp2/.
• 27: Sutherland, I. E. Sketchpad: A man-machine graphical communication system. In Proc. AFIPS Spring Joint Conf., 1963, 329-346.
• 28: Roberto Tamassia, Constraints in Graph Drawing Algorithms, Constraints, v.3 n.1, p.87-120, April 1998 [doi>10.1023/A:1009760732249]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Theory and methods

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Evaluation/methodology

General Terms:
Algorithms, Experimentation, Human Factors

Keywords:
constraint solvers, geometric constraints, graph layouts, module mechanisms, soft constraints