Location via proxy:   [ UP ]  
[Report a bug]   [Manage cookies]                
Skip to content

Latest commit

 

History

History
98 lines (73 loc) · 3.25 KB

README.md

File metadata and controls

98 lines (73 loc) · 3.25 KB
Raw

cassowary

This is a Swift implementation of the cassowary1 simplex solver inspired by the C++ implementation, Kiwi2.

Constraints

Cassowary supports linear equations and non-strict inequalities. Additionally, a strength may be associated with each constraint in the system, constrolling its importance to the overall solution to the system.

Defining Variables and Constraints

Variables are the values which the solver is trying to resolve. These correspond to the Variable type in the implementation. The variables can be used to create the expressions which form constraints of the system. These must be added to an instance of the solver.

import cassowary

let simplex: Solver = Solver()

let x_l: Variable = Variable("x_l")
let x_r: Variable = Variable("x_r")
let x_m: Variable = Variable("x_m")

simplex.add(constraint: 2.0 * x_m == x_l + x_r)
simplex.add(constraint: x_l + 10.0 <= x_r)
simplex.add(constraint: x_l >= -10.0)
simplex.add(constraint: x_r <= 100.0)

This creates a system with three variables (xl, xr, xm) representings points on a line segment. xm is constrained to the midpoint between xl and xr, xl is constrained to be at least 10 to the left of xr, and all variables must lie in the range [-10, 100]. All constraints must be satisfied and are considered as required by the cassowary algorithm.

NOTE The same constraint in the same form cannot be added to the solver multiply. Redundant constraints, as per cassowary, are supported. That is, the following set of constraints can be added to the solver:

x     == 10
x + y == 30
    y == 20

Managing Constraint Strength

Cassowary supports constraints which are not required but are handled as best-effort. Such a constraint is modelled as having a strength other than required. The constraints are considered in order of the value of their strengths. Three standard strengths are defined by default:

  1. strong
  2. medium
  3. weak

We can add a constraint to our previous example to place xm at 50 by adding a new weak constraint:

simplex.add(constraint: x_m == 50.0, strength: .weak)

Edit Variables

The system described thus far has been static. In order to find solutions for particular value of xm, Cassowary provides the concept of edit variables which allows you to suggest values for the variable before evaluating the system. These variables can have any strength other than required.

Continuing our example, we could make xm editable and suggest a value of 60 for it.

simplex.add(variable: x_m, .strong)
simplex.suggest(value: 60.0, for: x_m)

Solving and Updating Variables

This implementation solves the system each time a constraint is added or removed, or when a new value is suggested for an edit variable. However, the variable values are not updated automatically and you must request the solver to update the values.

simplex.suggest(value: 90, for: x_m)
simplex.update()

1 https://constraints.cs.washington.edu/solvers/cassowary-tochi.pdf ↩
2 https://github.com/nucleic/kiwi ↩