Question: algorithm of rectangular spiral

[rogerz]

@jasondavies , I'm a bit curious on how the rectangular spiral is generated from the formula (sqrt(1+4*t) - 1) & 3.

https://github.com/jasondavies/d3-cloud/blob/master/d3.layout.cloud.js#L347

Is there any reference link for further reading?

[jasondavies]

Technically it’s a square spiral, but with the step sizes scaled to match the rectangular extent.

For a given value of our integer parameter t, we’d like to find the direction of the corresponding leg.

First, examine the length of each “leg” of the spiral (every time it changes direction): the sequence is 1, 1, 3, 3, 6, 6, 10, 10, …

Very similar to triangular numbers, except that the length of a leg changes every 2nd leg, so the leg length L_i = T_floor(i/2).

If we can determine the step i for our parameter t, then we can determine the direction.

The curious formula is similar to finding the triangular root, but modified to take into account that the leg length changes every second step. We perform a bitwise operation on the root x, which gives us the two least significant bits of floor(x) and hence one of four directions.