The Cassowary Linear Arithmetic Constraint Solving Algorithm:
Interface and Implementation
Authors: Greg J. Badros and Alan Borning
Published as UW Tech Report 98-06-04.
Abstract
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 Cassowary--an incremental algorithm based
on the dual simplex method that can solve such systems of constraints
efficiently.
This informal technical report describes the latest version of the
Cassowary algorithm. It is derived from the paper
"Solving Linear Arithmetic Constraints for User
Interface Applications" by Alan Borning,
Kim Marriott, Peter Stuckey, and Yi Xiao, published
in the UIST'97 Proceedings. The UIST paper also contains a description of
QOCA, a closely related solver that finds least-squares solutions to linear
constraints. This technical report, which is intended to be
self-contained, includes material on Cassowary from the UIST paper, plus
a description of the Java, C++, and Smalltalk implementations and
their interfaces, along with additional details, corrections, and
clarifications.
An earlier technical report also
discussed QOCA and the similarities between Cassowary and that algorithm.
full tech report
(pdf,
ps.gz)
Constraints home page