2
$\begingroup$
+---------------+---------------+---------------+---------------+---------------+
| 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.

$\endgroup$
3

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This helped a lot. I did 4 a little different but it worked out. $\endgroup$
    – Justin808
    Commented Mar 24, 2018 at 3:33
0
$\begingroup$

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);
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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