The Cassowary Linear Arithmetic Constraint Solving Algorithm

作     者：Badros, Greg J. Borning, Alan Stuckey, Peter J. 

作者机构：Dept. of Computer Science and Engineering University of Washington Seattle Box 352350 WA 98195-2350 United States Dept. of Computer Science and Software Engineering University of Melbourne Victoria 3052 Parkville Australia 

出 版 物：《ACM Transactions on Computer-Human Interaction》 (ACM Trans. Comput.-Hum. Interact.)

年 卷 期：2001年第8卷第4期

页      面：267-306页

学科分类：08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Algorithms Cassowary constraint-solving toolkit constraints Design Theory user interface Verification 

摘      要：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 third of a window, or preferring that an object be contained within a rectangle if possible. Previous constraint solvers designed for user interface applications cannot handle simultaneous linear equations and inequalities efficiently. This is a major limitation, as such systems of constraints arise often in natural declarative specifications. We describe Cassowary—an incremental algorithm based on the dual simplex method, which can solve such systems of constraints efficiently. We have implemented the algorithm as part of a constraint-solving toolkit. We discuss the implementation of the toolkit, its application programming interface, and its performance. © 2001, ACM. All rights reserved.