## Integer Indexable Spiral Algorithm

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
``````