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

Question

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)
}

Please help me with that formula :) The first one i got also form this forum.

// 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 ];
}

Answer 1

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);
    leader *= leader;

    // 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;
}