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. Best, Wade On Sun, Jun 15, 2008 at 1:33 AM, Tomeu Vizoso <[EMAIL PROTECTED]> wrote: > On Sun, Jun 15, 2008 at 10:23 AM, Marco Pesenti Gritti > <[EMAIL PROTECTED]> wrote: >> On Sun, Jun 15, 2008 at 9:48 AM, Tomeu Vizoso <[EMAIL PROTECTED]> wrote: >>> I have some ideas, but I'm not sure how big an advantage they are >>> because the actual code in SpreadLayout is not resolving collisions. >>> >>> I will look at your demo now, but if someone involved in >>> SpreadLayout/_Grid could explain why the implementation never got >>> complete, that could save me quite some time. >> >> The usual reason, not enough time :) > > Ok, then if there's no known problem with the approach in Eben's demo, > I'll tackle it next. > > Regards, > > Tomeu > _______________________________________________ > Sugar mailing list > [email protected] > http://lists.laptop.org/listinfo/sugar > _______________________________________________ Sugar mailing list [email protected] http://lists.laptop.org/listinfo/sugar
