[ENH] Cassowary

Joshua Channing Gargus schwa at cc.gatech.edu
Fri May 18 04:37:42 UTC 2001


On Thu, May 17, 2001 at 07:52:33PM -0700, Ned Konz wrote:
> On Thursday 17 May 2001 19:47, Mark A. Schwenk wrote:
> > At 5/17/2001 07:33 PM, Ned Konz wrote:
> > >Can someone suggest where Cassowary might be useful for the kinds of
> > > drawings I've been dealing with (i.e. shapes connected with lines)?
> >
> > How about automatically positioning the shapes, using the lines as springs.
> > You can read an object instance model from the system, generate
> > collaboration diagrams showing the object relationships with the layout
> > done by the constraint engine. And then if you wanted, you could turn off
> > the constraint engine (at least in localized areas) and tweak the diagram a
> > bit.
> >
> > It could also be used in laying out network diagrams, organization charts,
> > parse trees, etc.
> 
> You know, I've thought about this a bit, and it seems like it could be done 
> without having to use a constraint system.
> 
> I imagine a process that can be run on demand to re-position shapes based on 
> their interconnections. Push a button, and things are rearranged 

Yes, but it would be nice if you didn't have to push a button.

> (with,  perhaps, a property that could exempt certain shapes from being 
> rearranged).

This could be done by putting a 'stay' constraint on them.  

> 
> Attaching a single ConstraintMorph to each of the movable shapes that 
> examines the connections and re-positions its constrained object would do the 
> trick. You could either leave the CM attached, or delete them after they've 
> done their job. Every step time the CM would examine the connections to its 
> constrained shape, and compute a vector that it would use to move its 
> constrained shape.

The problem is that each CM is only acting locally.  They can only try to 
optimize their position based on the other CMs to which they are directly
related.  This can lead to locally optimal but globally non-optimal solutions.

Cassowary uses an approach that will find a globally optimal solution, if one
exists.  It is able to do this efficiently by requiring all constraints to be
specified as linear equations.  At each step in the algorithm, it will either
move closer to an acceptable solution, or it will realize that none exists.

> This would occasionally lead to oscillations, but you could manually move an 
> oscillating shape to fix it.
> 
> I can't imagine a simultaneous solution for _all_ the shapes in a big 
> drawing; you'd almost have to compute them separately anyway. 

See above.

> In which case 
> you have got the simple case: a bunch of independent variables (the 
> connections looked at as springs) and one dependent variable (the resultant 
> vector for this step). And this doesn't require (or benefit from) a 
> constraint solver.
> 
> Unless I'm just not seeing the benefit.

I'm pretty sure that there is one (as I've described above).  However, I'm 
going to sleep on your email; I might not understand your proposal 
completely.

Joshua

> 
> -- 
> Ned Konz
> currently: Stanwood, WA
> email:     ned at bike-nomad.com
> homepage:  http://bike-nomad.com





More information about the Squeak-dev mailing list