# Find ID from Spiral x, y positions. Hard programming formula

I have a formula, which gets coordinates from user_id (see below).
I give User_id, and I get back coordinates.
But now I need to get User_id from coordinates.
For example:

function get_user_id_from_coordinates(x, y) {
// if x = 1, y = 0, returns 4 (as in this image)
}


// if user_id = 64
function get_coordinates_from_user_id(user_id) {

// Math.sqrt(user_id) = 8
// 8-1 = 7
// 7 / 2 = 3.5
// Math.ceil(3.5) = 4
var k = Math.ceil( (Math.sqrt(user_id) - 1) / 2 );

// t = 2 * 4 + 1 = 9
var t = 2 * k + 1;

// m = 81
var m = t * t;

// t = 9 - 1 = 8
t = t - 1;

// if 64 >= 81 - 8.   If 64 >= 73
if (user_id >= m - t) {
// return [ -4, 4 - (81 - 64)].   return [ -4, -13 ]
return [ -k,  k - (m - user_id)  ]
}
// else m = 81 - 8 = 73
else m = m - t;

// if 64 >= 73 - 8.   If 64 >= 65
if (user_id >= m - t) {
// return [ -4 + (73 - 64), -4].   return [ 5, -4 ]
return [ -k + (m - user_id), -k]
}
// else m = 73 - 8 = 65
else  m = m - t;

// if 64 >= 65 - 8.   If 64 >= 57
if (user_id >= m - t) {
// return [ 4, -4 + (65 - 64) ].   return [ 4, -3 ]  <== passes
return [ k, -k + (m - user_id) ]
};

// return [ 4 - (65 - 64 - 8), 4 ].   return [ 11, 4 ]
else return [ k - (m - user_id - t), k ];
}

• Is there a reason you can't make a look up table? For example, do you need infinite size? – tom10 Apr 8 '18 at 16:57
• Yep. I need infinite size.. – mansim Apr 8 '18 at 17:45

Let's add some colour coding to see if we can reveal some structure in the problem:

Here I've colour-coded the spiral into concentric rings of alternating colours. You'll notice the tile just before the bottom-left corner is always a perfect square. I'll dub this number the "Leader" of a given ring.

If we number our rings from 1 out, then the sequence of leader numbers is:

\begin{align} L(1) &= 1 &= 1^2\\ L(2) &= 9 &= 3^2\\ L(3) &= 25 &= 5^2\\ L(4) &= 49 &= 7^2\\ .&..\end{align}\\ L(ring) = (2\cdot ring - 1)^2

This will make it easy to number all the cells in a given ring, with reference to the corner. To reach...

• the row $y = 0$ in the left side of the ring, we subtract $(ring - 1)$
• the column $x = 0$ in the bottom of the ring, we add $(ring)$
• the bottom-right corner, we add $(2 \cdot ring)$
• the row $y = 0$ in the right side of the ring, we add $(3 \cdot ring)$
• the top-right corner, we add $(4 \cdot ring)$
• back to the column $x = 0$ along the top row, we add $(5 \cdot ring)$

So here's how we can translate that into a conversion method:

function spiralCellIndex(position) {
// First, we round our position to the nearest grid cell.
// Skip this if your input is already an integer pair grid coordinate.
var x = Math.round(position.x/gridSpacing);
var y = Math.round(position.y/gridSpacing);

// Compute a modified x value symmetric across the line x = 0.5
// (In the diagram I let this go negative,
// but doing it this way saves an unnecessary abs() )
var offCenterX = x > 0 ? x : -x + 1;

var ring = Math.max(offCenterX, Math.abs(y));

var leader = (2 * ring - 1);

// Top row of ring
// (This one has to come before the left side, because the two
// formulas disagree about the value to give the top-left cell)
if(y === -ring)
return leader + 5 * ring - x;

// Right side of ring
if(x === ring)
return leader + 3 * ring - y;

// Bottom of ring
if(y === ring)
return leader + ring + x;

// Finally, left side of ring
return leader - ring + 1 + y;
}

• Testet 1 bilion examples, id to coordinates and coordinates to id with your formula - its perfect and runs fast! :) – mansim Apr 9 '18 at 5:30
• I'm glad! I'll confess I didn't test it so I was worried I'd left a typo or off-by-one error in there somewhere.... – DMGregory Apr 9 '18 at 10:52