This is a little algorithm I wrote for generating multiple coordinates in a pseudo-spiral fashion using a single incrementing integer index. This function, given a single integer index, will generate an X and Y coordinate that represents a position on a two-dimensional graph, moving around in a spiral as the given index increments. This might sound a little confusing at first, but consider the diagram below. The cell values represent the index given to the function and shows the resulting X and Y coordinates.

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

As you can see the following indexes match with the given coordinates.

  • 0 -> {x: 0, y: 0}
  • 1 -> {x: 0, y: 1}
  • 2 -> {x: 1, y: 1}
  • 3 -> {x: 1, y: 0}
  • 4 -> {x: 1, y: -1}
  • 5 -> {x: 0, y: -1}
  • 6 -> {x: -1, y: -1}
  • 7 -> {x: -1, y: 0}
  • 8 -> {x: -1, y: 1}
  • 9 -> {x: -1, y: 2}

Code

/**
 * Convert spiral location idex to x/y coordinates.
 * 
 * @param {number} idx  Spiral location index.
 * @param {coordinates} origin X/Y origin to start spiral at.
 * 
 * @returns {coordinates} Spiral location coordinates.
 */
function spiralIndexToCoord(idx, origin) {
    origin = origin || {x: 0, y: 0};

    var swSteps = 1;
    var offset = {
        x: 0,
        y: 0
    };

    while(idx > 0) {
        // Calculate number of steps to navigate southwest 1 block.
        var stepsEndpoint = swSteps + 1;
        var movements = ((stepsEndpoint - 1) * 2) + stepsEndpoint * 2;        

        // If we have more indexes left to cover the southwest movement,
        // move the offset.
        if(movements <= idx) {
            idx -= movements;
            
            offset.x--;
            offset.y--;
        } else {        
            // If not, then we need to move it manually to hit the destination.
            // For the given directions N to W, 0 to 3, list out the amount of steps needed.
            var direction = 0;
            var stepArr = [
                swSteps,
                swSteps,
                swSteps + 1,
                swSteps + 1
            ];
            
            // Loop for the remainder of idx.
            while(idx > 0) {
                // Decrement the direction step.
                stepArr[direction]--;

                // Move in the given direction.
                if(direction == 0) { offset.y++; }
                if(direction == 1) { offset.x++; } 
                if(direction == 2) { offset.y--; }
                if(direction == 3) { offset.x--; }

                // Move to next direction if this directions steps have run out.
                if(stepArr[direction] == 0)
                    direction++;

                idx--;
            }
        }

        // Move to next sw count for next iteration.
        swSteps += 2;
    }

    return {
        x: origin.x + offset.x,
        y: origin.y + offset.y
    };
}

Origin parameter

By default, the 0th index of the spiral will start at (0, 0). However you manually set the origin of the spiral through the origin parameter.

spiralIndexToCoord(0, {x: 5, y: 12});

Performance Issues

Due to the nature of the algorithm, higher indexes take longer time to calculate than lower indexes. I have tested the performance hit for generating the first million indexes as well as Number.MAX_SAFE_INTEGER (Which in NodeJS is 9,007,199,254,740,991).

The testing script implementation and result is as follows:

// Show the first ten indexes.
for(var i = 0; i < 10; i++) {
    console.log("Index " + i + ":", spiralIndexToCoord(i, {x: 0, y: 0}))
}

// Measure time taken for 1 million iterations of spiral index to coordinate conversions.
console.time("First million indexes");
for(var i = 0; i < 1000000; i++) {
    var coords = spiralIndexToCoord(i, {x: 0, y: 0});
}
console.timeEnd("First million indexes");

// Measure time taken for a large index.
console.time("MAX_SAFE_INTEGER");
console.log("Index " + Number.MAX_SAFE_INTEGER + ":", spiralIndexToCoord(Number.MAX_SAFE_INTEGER, {x: 0, y: 0}));
console.timeEnd("MAX_SAFE_INTEGER");

Index 0: { x: 0, y: 0 }
Index 1: { x: 0, y: 1 }
Index 2: { x: 1, y: 1 }
Index 3: { x: 1, y: 0 }
Index 4: { x: 1, y: -1 }
Index 5: { x: 0, y: -1 }
Index 6: { x: -1, y: -1 }
Index 7: { x: -1, y: 0 }
Index 8: { x: -1, y: 1 }
Index 9: { x: -1, y: 2 }
First million indexes: 6925ms
Index 9007199254740991: { x: 47453133, y: 23868632 }
MAX_SAFE_INTEGER: 1886ms