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