[sugar] collisions in free form layouts

[Tomeu Vizoso]

On Mon, Jun 16, 2008 at 4:45 AM, Wade Brainerd <wadetb at gmail.com> wrote:
> I'm not familiar with Eben's algorithm, but I thought I would chime in
> that IMO the ideal algorithm for these kinds of layouts is what is
> called a "relaxation algorithm".  It's the basis of most physics
> engines like Box2D.
>
> You define a set of rules, called constraints, which define the order
> of the layout.  For example "no two icons can oversect", "no icon can
> intersect the XO", and "no icon can leave the screen".
>
> To process, you iterate over the constraints, "relaxing" them by some
> percentage, for a fixed number K iterations.  For constraints
> involving intersecting objects, this involves moving them each apart
> along their separating axis by 0.5*penetration/K.  This "relaxes" the
> system over time by resolving each constraint a little bit at a time
> until all are satisfied.
>
> Implemented naively the complexity is O(N^2), but plenty of
> optimizations exist to make it very quick.  The simplest would be a
> grid based spacial subdivision.
>

I like the idea, although for the sake of getting things done, I'm
going to push just some modifications to the algorithm implementation
currently in sugar.

As always, feel free to play with the code and we'll welcome any patches.

Thanks,

Tomeu