# Given a number, getting a grid position in a spiral pattern

+---------------+---------------+---------------+---------------+---------------+
| id:  20       | id:  19       | id:  18       | id:  17       | id:  16       |
| pos: (-2, -2) | pos: (-1, -2) | pos: (0, -2)  | pos: (1, -2)  | pos: (2, -2)  |
+---------------+---------------+---------------+---------------+---------------+
| id:  21       | id:  6        | id:  5        | id:  4        | id:  15       |
| pos: (-2, -1) | pos: (-1, -1) | pos: (0, -1)  | pos: (1, -1)  | pos: (2, -1)  |
+---------------+---------------+---------------+---------------+---------------+
| id:  22       | id:  7        | id:  0        | id:  3        | id:  14       |
| pos: (-2, 0)  | pos: (-1, 0)  | pos: (0, 0)   | pos: (1, 0)   | pos: (2, 0)   |
+---------------+---------------+---------------+---------------+---------------+
| id:  23       | id:  8        | id:  1        | id:  2        | id:  13       |
| pos: (-2, 1)  | pos: (-1, 1)  | pos: (0, 1)   | pos: (1, 1)   | pos: (2, 1)   |
+---------------+---------------+---------------+---------------+---------------+
| id:  24       | id:  9        | id:  10       | id:  11       | id:  12       |
| pos: (-2, 2)  | pos: (-1, 2)  | pos: (0, 2)   | pos: (1, 2)   | pos: (2, 2)   |
+---------------+---------------+---------------+---------------+---------------+


Given a grid, starting at the center and spiraling out like the above. I'm trying to find an algorithm that given an id returns a pos. Is there an algorithm that works like this? I don't want to use a lookup table or anything like that as the grid could be any size.

• Ooh, this would make a great code golf Commented Mar 23, 2018 at 2:49
• Commented Mar 24, 2018 at 3:49
• @Blacksilver - codegolf.stackexchange.com/questions/160148 Commented Mar 24, 2018 at 4:07

I'll give a hint by breaking down the problem into nice looking components. I'll leave it to you to implement the components and use them yourself.

1) A function from id to the ring number it is in. For example,

• id 0 is in the 0th ring.
• id 1,2,3,4,5,6,7,8 is in the 1st ring.

2) A function from ring number to the last id of the ring. For example,

• 0th ring's last id is 0
• 1st ring's last id is 8
• 2nd ring's last id is 24

3) A function from ring number to the last pos of the ring. For example,

• 0th ring's last pos is (0,0)
• 1st ring's last pos is (-1,1)
• 2nd ring's last pos is (-2,2)

4) A function from id to the increment of pos to reach the next id. Let's call this function $g$. For example,

• $g(10) = (1,0)$
• $g(20) = (0,-1)$

It has to do with what part of the ring the id is in.

Hopefully, this has structured the problem in a way you can see the solution easier by yourself.

• This helped a lot. I did 4 a little different but it worked out. Commented Mar 24, 2018 at 3:33

My javascript implementation...

function getRing (id) {
return Math.ceil((Math.sqrt(id + 1) - 1) / 2);
}

function getMinRingID (r) {
if (r == 0) {
return 0;
}
return Math.pow((2 * (r - 1) + 1), 2);
}

function getRingLegFromID (id) {
if (id == 0) {
return 0;
}

var r = getRing(id);
var m = getMinRingID(r);
if (id >= m && id < m + (2 * r)) {
return 0;
} else if (id >=  m + (2 * r) && id <  m + (4 * r)) {
return 1;
} else if (id >=  m + (4 * r) && id <  m + (6 * r)) {
return 2;
} else if (id >=  m + (6 * r)) {
return 3;
}
}


With the above basics, you can get the position with...

function getPos (id) {
var ring = getRing(id);
var min = getMinRingID(ring);
var leg = getRingLegFromID(id);

if (id === 0) {
return [0, 0];
}

switch (leg) {
case 0:
return [-ring + ((id - min) + 1), ring];
break;
case 1:
return [ring, ring - ((id - min) - ((2 * ring) - 1))];
break;
case 2:
return [ring - ((id - min) - ((4 * ring) - 1)), -ring];
break;
case 3:
return [-ring, -ring + ((id - min) - ((6 * ring) - 1))];
break;
}
}


The test...

for (var id = 0; id < 49; id ++) {
var ring = getRing(id);
var min = getMinRingID(ring);
var leg = getRingLegFromID(id);
var pos = getPos(id);

console.log('id = ' + id + '; ring = ' + ring + '; leg = ' + leg + '; pos = ' + pos);
}