<div dir="ltr">Spread layout should:<div><br></div><div>* Position icons so as to minimize overlap</div><div>* Support a suggested location for the position of a given icon</div><div>* Support both addition and removal of nodes</div>
<div>* Support in-place scaling of nodes, both growing and shrinking</div><div>* Have a low big-O (O(n)? O(nlogn)? But, as we've seen, it also needs a fairly low constant)</div><div><br></div><div>I noticed after glancing at the code in place now that you don't actually follow my algorithm (which is technically O(n), I think, but with a (really) large constant) because you recurse on the collision checks.  Removing that recursion is one small step in the right direction.  However, the overhead of maintaining the weights array seems to be a bottleneck on the laptops.</div>
<div><br></div><div>I discussed a few possible options with Michael the other day. One option is to use a quad tree to isolate nodes hierarchically, to minimize the amount of collision checking needed and to prevent the need for a weights array.  Instead, the nodes of the quad tree are assigned weights which represent the sum total of weights in their subtrees.  This is really nothing more than an optimization of the current algorithm, but it could help a fair amount.</div>
<div><br></div><div>Another potentially interesting solution is a pseudo-spring algorithm, by which we detect some numbers of neighbors (O(n)) and then we "push" those neighbors away with some force vector, the magnitude of which is weighted based on the size of the nodes, and the direction of which is calculated as the angle between them.  This solution doesn't, in theory, yield results that are as good as the other options (since it pushes away at a fixed angle, instead of towards nearby positions with ow weights), but it should be really quick.</div>
<div><br></div><div>I'm sure there are other options, or combinations of these, that we could explore as well.</div><div><br></div><div>- Eben<br><br></div><div>PS.  I did a review of the current algorithm a while back, but lost the notes on it.  I'll go back through it again, because there did seem to be a bit of unnecessary work being done when I looked at it before.</div>
<div><br></div><div><br></div><div><br><div class="gmail_quote">On Fri, Aug 1, 2008 at 6:30 AM, Tomeu Vizoso <span dir="ltr"><<a href="mailto:tomeu@tomeuvizoso.net">tomeu@tomeuvizoso.net</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="Ih2E3d">On Fri, Aug 1, 2008 at 7:55 AM, riccardo <<a href="mailto:riccardo.lucchese@gmail.com">riccardo.lucchese@gmail.com</a>> wrote:<br>
> On Thu, 2008-07-31 at 17:27 +0100, Tomeu Vizoso wrote:<br>
>> On Tue, Jul 29, 2008 at 3:15 PM, riccardo <<a href="mailto:riccardo.lucchese@gmail.com">riccardo.lucchese@gmail.com</a>> wrote:<br>
>><br>
</div><div class="Ih2E3d">>> I guess that's for the mesh and friends view?<br>
> Oh, right!<br>
> +1 for changing the algorithm.<br>
<br>
</div>Eben, can you write down a list of requirements for the spread layout?<br>
<br>
Thanks,<br>
<font color="#888888"><br>
Tomeu<br>
</font></blockquote></div><br></div></div>