The Cassowary linear arithmetic constraint solving algorithm

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 rect-angle if possible. Current constraint solvers designed for UI applications cannot eciently 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 eciently