Algorithm for iterating over an outward spiral on

Question

For example, here is the shape of intended spiral (and each step of the iteration)

          y
          |
          |
   16 15 14 13 12
   17  4  3  2 11
-- 18  5  0  1 10 --- x
   19  6  7  8  9
   20 21 22 23 24
          |
          |

Where the lines are the x and y axes.

Here would be the actual values the algorithm would "return" with each iteration (the coordinates of the points):

[0,0],
[1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1], [0,-1], [1,-1],
[2,-1], [2,0], [2,1], [2,2], [1,2], [0,2], [-1,2], [-2,2], [-2,1], [-2,0]..

etc.

I've tried searching, but I'm not exactly sure what to search for exactly, and what searches I've tried have come up with dead ends.

I'm not even sure where to start, other than something messy and inelegant and ad-hoc, like creating/coding a new spiral for each layer.

Can anyone help me get started?

Also, is there a way that can easily switch between clockwise and counter-clockwise (the orientation), and which direction to "start" the spiral from? (the rotation)

Also, is there a way to do this recursively?

---

My application

I have a sparse grid filled with data points, and I want to add a new data point to the grid, and have it be "as close as possible" to a given other point.

To do that, I'll call grid.find_closest_available_point_to(point), which will iterate over the spiral given above and return the first position that is empty and available.

So first, it'll check point+[0,0] (just for completeness's sake). Then it'll check point+[1,0]. Then it'll check point+[1,1]. Then point+[0,1], etc. And return the first one for which the position in the grid is empty (or not occupied already by a data point).

There is no upper bound to grid size.

Answer 1

There's nothing wrong with direct, "ad-hoc" solution. It can be clean enough too.
Just notice that spiral is built from segments. And you can get next segment from current one rotating it by 90 degrees. And each two rotations, length of segment grows by 1.

edit Illustration, those segments numbered

   ... 11 10
7 7 7 7 6 10
8 3 3 2 6 10
8 4 . 1 6 10
8 4 5 5 5 10
8 9 9 9 9  9

.

    // (di, dj) is a vector - direction in which we move right now
    int di = 1;
    int dj = 0;
    // length of current segment
    int segment_length = 1;

    // current position (i, j) and how much of current segment we passed
    int i = 0;
    int j = 0;
    int segment_passed = 0;
    for (int k = 0; k < NUMBER_OF_POINTS; ++k) {
        // make a step, add 'direction' vector (di, dj) to current position (i, j)
        i += di;
        j += dj;
        ++segment_passed;
        System.out.println(i + " " + j);

        if (segment_passed == segment_length) {
            // done with current segment
            segment_passed = 0;

            // 'rotate' directions
            int buffer = di;
            di = -dj;
            dj = buffer;

            // increase segment length if necessary
            if (dj == 0) {
                ++segment_length;
            }
        }
    }

To change original direction, look at original values of di and dj. To switch rotation to clockwise, see how those values are modified.

Answer 2

I had a similar problem, but I didn't want to loop over the entire spiral each time to find the next new coordinate. The requirement is that you know your last coordinate.

Here is what I came up with with a lot of reading up on the other solutions:

function getNextCoord(coord) {

    // required info
    var x     = coord.x,
        y     = coord.y,
        level = Math.max(Math.abs(x), Math.abs(y));
        delta = {x:0, y:0};

    // calculate current direction (start up)
    if (-x === level)
        delta.y = 1;    // going up
    else if (y === level)
        delta.x = 1;    // going right
    else if (x === level)        
        delta.y = -1;    // going down
    else if (-y === level)
        delta.x = -1;    // going left

    // check if we need to turn down or left
    if (x > 0 && (x === y || x === -y)) {
        // change direction (clockwise)
        delta = {x: delta.y, 
                 y: -delta.x};
    }

    // move to next coordinate
    x += delta.x;
    y += delta.y;

    return {x: x,
            y: y};
}

coord = {x: 0, y: 0}
for (i = 0; i < 40; i++) {
    console.log('['+ coord.x +', ' + coord.y + ']');
    coord = getNextCoord(coord);  

}

Still not sure if it is the most elegant solution. Perhaps some elegant maths could remove some of the if statements. Some limitations would be needing some modification to change spiral direction, doesn't take into account non-square spirals and can't spiral around a fixed coordinate.

Answer 3

Here's the algorithm. It rotates clockwise, but could easily rotate anticlockwise, with a few alterations. I made it in just under an hour.

// spiral_get_value(x,y);
sx = argument0;
sy = argument1;
a = max(sqrt(sqr(sx)),sqrt(sqr(sy)));
c = -b;
d = (b*2)+1;
us = (sy==c and sx !=c);
rs = (sx==b and sy !=c);
bs = (sy==b and sx !=b);
ls = (sx==c and sy !=b);
ra = rs*((b)*2);
ba = bs*((b)*4);
la = ls*((b)*6);
ax = (us*sx)+(bs*-sx);
ay = (rs*sy)+(ls*-sy);
add = ra+ba+la+ax+ay;
value = add+sqr(d-2)+b;
return(value);`

It will handle any x / y values (infinite).

It's written in GML (Game Maker Language), but the actual logic is sound in any programming language.

The single line algorithm only has 2 variables (sx and sy) for the x and y inputs. I basically expanded brackets, a lot. It makes it easier for you to paste it into notepad and change 'sx' for your x argument / variable name and 'sy' to your y argument / variable name.

`// spiral_get_value(x,y);

sx = argument0;  
sy = argument1;

value = ((((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*2))+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*4))+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*((max(sqrt(sqr(sx)),sqrt(sqr(sy))))*6))+((((sy==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sx !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sx)+(((sy==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sx !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sx))+(((sx==max(sqrt(sqr(sx)),sqrt(sqr(sy))) and sy !=(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy))))))*sy)+(((sx==(-1*max(sqrt(sqr(sx)),sqrt(sqr(sy)))) and sy !=max(sqrt(sqr(sx)),sqrt(sqr(sy)))))*-sy))+sqr(((max(sqrt(sqr(sx)),sqrt(sqr(sy)))*2)+1)-2)+max(sqrt(sqr(sx)),sqrt(sqr(sy)));

return(value);`

I know the reply is awfully late :D but i hope it helps future visitors.

Answer 4

Here's a stab at it in C++, a stateful iterator.

class SpiralOut{
protected:
    unsigned layer;
    unsigned leg;
public:
    int x, y; //read these as output from next, do not modify.
    SpiralOut():layer(1),leg(0),x(0),y(0){}
    void goNext(){
        switch(leg){
        case 0: ++x; if(x  == layer)  ++leg;                break;
        case 1: ++y; if(y  == layer)  ++leg;                break;
        case 2: --x; if(-x == layer)  ++leg;                break;
        case 3: --y; if(-y == layer){ leg = 0; ++layer; }   break;
        }
    }
};

Should be about as efficient as it gets.