Layout via Optimisation

Since I mentioned linear programming in the last entry I've managed to wrap my head around it enough to come up with a possible solution for my layout issues.

Example layout problem:


If I just consider the horizontal coordinates, the following known values and relationships describe this layout:

B centre = A centre
B width = 40
C width = B width / 2
C left = B right + 5
D width = 100
D right = B right

Want to know:

Left and right of every box.

Now a recursive layout algorithm has trouble with this. It can't determine the offset of B without knowing the size of A, but the size of A depends on the offset of B. You need to do at least a couple of size and layout passes, and even then I'm having trouble getting it working (and I don't have the perserverance to keep trying).

It seems at first that solving the simultaneous equations would work. But in general this isn't useful because there is nothing to stop negative widths being created -- which isn't terribly useful. And determining enough additional terms to constrain the solution (e.g. that D left = A left) requires calculation itself.

Changing this to an optimisation problem allows it to be defined without the need for it to be fully specified. And constraints keep the values pointing the right way.

After a bit of fiddling about, I think I've come up with a basic systematic procedure which should allow the determination of the results using the simplex algorithm. It may not be the most optimal setup, but it appears to be relatively robust so far.

1. Trivially define the objective function in terms of the sum of every left and right X coordinate.
2. Define width relationships - the known knowns, or the known unknowns.
3. Define container constraints - every child is fully inside its parent. Unless the parent size is defined explicitly, in which case do not add any implicit relationship.
4. Define layout constraints.

Applied to the problem above, first, trivially define the object function in terms of the left and right bounds of every box:

p = ar + al + bl + br + cl + cr + dl + dr

This is a minimisation problem in p.

Next define the widths:

br - bl = 40
dr - dl = 100
ar - al >= 0
cr - cl >= 0 (since we know this is B width / 2, we could just use 20 too)

Define the container relationship -- everything inside A must be inside A:

br - ar <= 0 cr - ar <= 0 dr - ar <= 0 al - cl <= 0 al - bl <= 0 al - dl <= 0 Everything is relative to A, so set A's left edge to 0, so it doesn't float up to meet the highest other boundary. al = 0 Now define the layout relationships. B centre = A centre bl + (br - bl)/2 = (ar - al) / 2 or bl/2 + br/2 - ar/2 + al/2 = 0 C width = B width / 2 cr - cl = (br - bl)/2 or br/2 - bl/2 - cr + cl = 0 C left = B right + 5 cl = br + 5 or cl - br = 5 D right = B right dr = br dr - br = 0 And running the simplex method over this system generates everything I need directly: Optimal Solution: p = 650; ar = 160, al = 0, bl = 60, br = 100, cl = 105, cr = 125, dl = 0, dr = 100 (calculated using http://www.zweigmedia.com/RealWorld/simplex.html) Nice. And just as a test, lets shrink D to be smaller than B, say 30.

Optimal Solution: p = 440; ar = 90, al = 0, bl = 25, br = 65, cl = 70, cr = 90, dl = 35, dr = 65

Still works.

It should be able to calculate both dimensions and deeper structures simultaneously. This will allow relationships across dimensions, e.g. A width = B height * factor + offset.

One thing the recursive layout routine handled ok was affine transforms (after a lot of mucking about mind you). I guess this should handle them too if I get the coordinate space correct. Relative position calculations need to be in parent space, but the layout calculations need to be in global space.

Now I just have to work out how to calculate those parameters from expression trees, and find out if a solver will run fast enough. Actually I'm pretty confident of the performance question, even a trivial implementation I wrote for work did thousands of rows and columns in a few hundred ms.