Given a grid, starting at the center and spiraling out, and an Position what is the ID?

Question

Grid:

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

Code:

public static int IDFromPos(int sectionX, int sectionY) {
    int sectionId = 0;
    if (sectionX < 0 && Mathf.Abs (sectionX) >= Mathf.Abs (sectionY)) {
        sectionId = (int)Mathf.Pow (((-2 * sectionX) + 1), 2) - 1 - (-sectionX - sectionY);
    } else if (sectionX > 0 && Mathf.Abs (sectionX) >= Mathf.Abs (sectionY)) {
        sectionId = (int)Mathf.Pow (((2 * sectionX) + 1), 2) - 1 - (4 * sectionX) - (-sectionX - sectionY);
    } else if (sectionY < 0) {
        sectionId = (int)Mathf.Pow (((-2 * sectionY) + 1), 2) - 1 - (2 * sectionY) - (-sectionY + sectionX);
    } else {
        sectionId = (int)Mathf.Pow ((2 * (sectionY - 1) + 1), 2) + (sectionY - 1 + sectionX);
    }

    return sectionId;
}

Test

IDFromPos(-2, -2) = 20
IDFromPos(-2, -1) = 21
IDFromPos(-2, 0) = 22
IDFromPos(-2, 1) = 23
IDFromPos(-2, 2) = 24
IDFromPos(-1, -2) = 27 (should be 19)
IDFromPos(-1, -1) = 6
IDFromPos(-1, 0) = 7
IDFromPos(0, 0) = 0
IDFromPos(0, 1) = 1
IDFromPos(0, 2) = 10
IDFromPos(1, 0) = 5  (should be 3)
IDFromPos(1, 1) = 6  (should be 2)
IDFromPos(1, 2) = 11
IDFromPos(2, 0) = 18 (should be 14)
IDFromPos(2, 1) = 19 (should be 13)
IDFromPos(2, 2) = 20 (should be 12)

I've been staring at this for way to long. I can't see my error(s). Given the (x,y) position what is id? What is wrong with this function?

The grid positions are not normal so please look close. -,- is top left, +,+ is bottom right.

@SeM - I added a few more test & what they should be. I'l just trying to get the `id` for a given `x,y` position — Justin808, Mar 28 '18 at 05:30
@richej - no. The grid is just an example. its size isn't set and can be large. — Justin808, Mar 28 '18 at 05:40
Have a look at this post: https://stackoverflow.com/questions/398299/looping-in-a-spiral — Rob, Mar 28 '18 at 05:44
@SeM - no, its just part of a side project I'm playing around with. I have a job already that I enjoy. — Justin808, Mar 28 '18 at 05:48

GregorMohorko · Answer 1 · 2018-03-28T05:51:26.533

The calculations inside the second and the third else if are wrong. In the second, the last subtraction should actually be an addition. In the third, the middle subtraction should be an addition.

// ...
} else if(sectionX > 0 && Mathf.Abs(sectionX) >= Mathf.Abs(sectionY)) {
    sectionId = (int)Mathf.Pow(((2 * sectionX) + 1), 2) - 1 - (4 * sectionX) + (-sectionX - sectionY);
} else if(sectionY < 0) {
    sectionId = (int)Mathf.Pow(((-2 * sectionY) + 1), 2) - 1 + (2 * sectionY) - (-sectionY + sectionX);
}
// ...

This fixes all your tests.

MBo · Answer 2 · 2018-03-28T06:00:37.533

Divide whole plane into four segments by diagonals and form result for every segment:

x * x >= y * y, x >= 0:
   id = 4 * x * x - x - y
x * x >= y * y, x < 0:
   id = 4 * x * x - 3 * x + y
y * y < x * x, y >= 0:
   id = 4 * y * y - 3 * y + x
y * y < x * x, y < 0:
   id = 4 * y * y - y - x

id(2,1) = 16 - 2 - 1 = 12
id(2,-1) = 16 - 2 + 1 = 15
id(-2,1) = 16 + 6 + 1= 23
id(-1, -2) = 16 + 2 + 1= 19
id(-1, 2) = 16  - 6 - 1= 9

Given a grid, starting at the center and spiraling out, and an Position what is the ID?

2 Answers2