Solving Linear Arithmetic Constraints for User Interface
Applications: Algorithm Details
Authors: Alan Borning, Kim Marriott, Peter Stuckey, and Yi Xiao
Published as UW Tech Report 97-06-01.
Linear equality and inequality constraints arise naturally in specifying
many aspects of user interfaces, such as requiring that one window be to
the left of another, requiring that a pane occupy the leftmost 1/3 of a
window, or preferring that an object be contained within a rectangle if
possible. Current constraint solvers designed for UI applications cannot
efficiently handle simultaneous linear equations and inequalities. This is
a major limitation. We describe incremental algorithms based on the dual
simplex and active set methods that can solve such systems of constraints
efficiently. Both algorithms have been implemented and tested.
This informal technical report is adapted from the paper "Solving Linear
Arithmetic Constraints for User Interface Applications," which will appear
in the Proceedings of UIST'97 (The ACM User Interface and Software
Technology Symposium). It contains additional details, in particular of
the Cassowary and QOCA algorithms.
full tech report (compressed postscript)
Constraints home page