3
\$\begingroup\$

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.

enter image description here

// 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 ];
}
\$\endgroup\$
  • \$\begingroup\$ Is there a reason you can't make a look up table? For example, do you need infinite size? \$\endgroup\$ – tom10 Apr 8 '18 at 16:57
  • \$\begingroup\$ Yep. I need infinite size.. \$\endgroup\$ – mansim Apr 8 '18 at 17:45
8
\$\begingroup\$

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

Colour-coded spiral diagram

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Testet 1 bilion examples, id to coordinates and coordinates to id with your formula - its perfect and runs fast! :) \$\endgroup\$ – mansim Apr 9 '18 at 5:30
  • \$\begingroup\$ 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.... \$\endgroup\$ – DMGregory Apr 9 '18 at 10:52

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.