Work out co-ordinates in a circular pattern?

Question

In Java, i am trying to create a Grid system, for an in-game town manager. I would like it to fill from a center point, and work its way out in a circular pattern (or even diamond pattern). Is there a formula i can use to help make this easier?

For example, i want to be able to input a number, and get the X and Y co-ordinates of the grid. e.g.

If i input 0, it will give me (0,0)
If i input 1, it will give me (0,1)
2 -> (1,0)
3 -> (0,-1)
4 -> (-1,0)
5 -> (0,2)
6 -> (1,1)
7 -> (2,0)
8 -> (1,-1)
9 -> (0,-2)
10 -> (-1,-1)
11 -> (-2,0)
12 -> (-1,1)
13 -> (0,3)
etc

I just have no idea where to start with it.

Thanks in advance, Dan

Answer 1

Why iterate all the way from 0 to n just to compute the coordinates, when you could use ... math!

Here's the sequence of squares visited by your spiral:

         13
      14  5 24
   15  6  1 12 23
16  7  2  0  4 11 22
   17  8  3 10 21
      18  9 20
         19

This can be divided into "rings". First, the number 0. Then a ring of size 4:

          1
       2     4
          3

Then a second ring of size 8:

          5
       6    12
    7          11
       8    10
          9

Then a third ring of size 12:

         13
      14    24
   15          23
16                22
   17          21
      18    20
         19

And so on. The r-th ring has size 4r, and contains the numbers from 2(r − 1)r + 1 to 2r(r + 1) inclusive.

So which ring contains the number n? Well, it's the smallest r such that 2r(r + 1) ≥ n, which can be found using the quadratic formula:

2r(r + 1) ≥ n
∴ 2r² + 2r − n ≥ 0
∴ r ≥ (−2 + √(4 + 8n)) / 4
∴ r ≥ ½(−1 + √(1 + 2n))

So the r we want is

 r = ceil(0.5 * (−1.0 + sqrt(1.0 + 2.0 * n)))

And that's enough information to compute the coordinates you want:

public spiral_coords(int n) {
    if (n == 0) { 
        return Coords(0, 0);
    }
    // r = ring number.
    int r = (int)(ceil(0.5 * (-1.0 + sqrt(1.0 + 2.0 * n))));
    // n is the k-th number in ring r.
    int k = n - 2 * (r - 1) * r - 1;
    // n is the j-th number on its side of the ring. 
    int j = k % r;
    if (k < r) {
        return Coords(-j, r - j);
    } else if (k < 2 * r) {
        return Coords(-r - j, -j);
    } else if (k < 3 * r) {
        return Coords(j, -r - j);
    } else {
        return Coords(r - j, j);
    }
}

Answer 2

This considers the pattern as a series of concentric shells. First you quickly enumerate over the inner shells. Then step through the outer shell, starting at the right hand side and going counter-clockwise.

int tot = 1, r=0; // r is "radius", tot is # of points so far
// since each "shell" has 4r points, quickly find the desired radius
while(tot + 4*r < i){tot += 4*r; r++;}
// enumerate the boundary counter-clockwise
int x = r; y = 0, j;
for(j=0; j<r && tot<i; j++, x--, y++, tot++);
for(j=0; j<r && tot<i; j++, x--, y--, tot++);
for(j=0; j<r && tot<i; j++, x++, y--, tot++);
for(j=0; j<r && tot<i; j++, x++, y++, tot++);
// answer in x,y

Answer 3

you can do

for (int n=1; n < max; n++) {
    for(int x = -n; x < n; x++)
        process(x, n);
    for(int y = n; y > -n;y--)
        process(n, y);
    for(int x = n; x > -n;x--)
        process(x, -n);
    for(int y = -n; y < n;y++)
        process(-n, y);
}