9

What is an algorithm to get the nth element of a rectangular tiled spiral?

Here is n:

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

and here are the corresponding coordinates for n:

[-2,2 ][-1,2 ][ 0,2 ][ 1,2 ][ 2,2 ]
[-2,1 ][-1,1 ][ 0,1 ][ 1,1 ][ 2,1 ]
[-2,0 ][-1,0 ][ 0,0 ][ 1,0 ][ 2,0 ]
[-2,-1][-1,-1][ 0,-1][ 1,-1][ 2,-1]
[-2,-2][-1,-2][ 0,-2][ 1,-2][ 2,-2]

If given n, how to calculate the coordinates?

Jonathan M
  • 17,145
  • 9
  • 58
  • 91
MaiaVictor
  • 51,090
  • 44
  • 144
  • 286

6 Answers6

15

Here's a short and sweet answer using just simple math in pseudocode. No conditionals and no iteration. Given tileNum for the tile number:

intRoot=int(sqrt(tileNum));

x=(round(intRoot/2)*(-1^(intRoot+1)))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)-abs((intRoot*(intRoot+1))-tileNum))/2);

y=(round(intRoot/2)*(-1^intRoot))+((-1^(intRoot+1))*(((intRoot*(intRoot+1))-tileNum)+abs((intRoot*(intRoot+1))-tileNum))/2);

Here's a fiddle to see it in action.

Jonathan M
  • 17,145
  • 9
  • 58
  • 91
  • 2
    Beautiful. Like @Viclib, I'd also like to see an explanation. – sudo make install Jul 22 '14 at 17:04
  • Where do you look at the size of the matrix? – Andrew Paul Simmons Jun 17 '16 at 03:14
  • Hi, @AndrewPaulSimmons, I'm not sure what you're asking. I never really look at the size of the matrix because I don't need to. The x and y values are calculated from the tile number, which naturally increases as you spiral out from the center. – Jonathan M Jun 17 '16 at 21:43
  • so you are saying that if I had a 100 element matrix or a 10000 element matrix, element 100 would have the same x, y? I'm not convinced. Also, why does element 100 have x, y values of -5, -5 in your fiddle? – Andrew Paul Simmons Jun 18 '16 at 01:51
  • I think you misunderstand the original question. The start of the spiral is always (0,0), so, yes, the 100th element is always going to have the same x,y. If you trace the spiral around 100 places, you'll see that the 100th element has the coordinates (-5,-5). – Jonathan M Jun 21 '16 at 18:58
  • @JonathanM did you came up with the formula using trial and error or is there any specific theory behind that? – jonathancardoso Nov 04 '16 at 01:20
  • 1
    Hi, @JCM. Thanks for asking. No trial and error. Once you look at the addresses, especially the corner addresses of the spiral, the correlations between addresses and element numbers become pretty clear. Algebraic reduction then yields the formula. – Jonathan M Nov 07 '16 at 17:19
5

Here is an code in JavaScript. It calculates position for 2D matrix starting with number 1 in a middle (0, 0)

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

/**
 * Finds coordinates (position) of the number
 * 
 * @param {Number} n - number to find position/coordinates for
 * @return {Number[]} - x and y coordinates of the number
 */
function position(n) {
    const k = Math.ceil((Math.sqrt(n) - 1) / 2);
    let t = 2 * k + 1;
    let m = Math.pow(t, 2);

    t -= 1;

    if (n >= m - t) {
        return [k - (m - n), -k];
    }

    m -= t;

    if (n >= m - t) {
        return [-k, -k + (m - n)];
    }

    m -= t;

    if (n >= m - t) {
        return [-k + (m - n), k];
    }

    return [k, k - (m - n - t)];
}
Vlad Bezden
  • 83,883
  • 25
  • 248
  • 179
2

First, find out which ring your desired element is in (hint: until you get to the outer ring, your spiral is made up of nested squares), then which side (of the 4) it is on, then you're just left with its position on that side.

Scott Hunter
  • 48,888
  • 12
  • 60
  • 101
1

Similar questions exist already... See my non-looping version. You may need to swap and/or negate X/Y coordinates and change the 100's to 0's depending on what orientation and origin you want.

There's also more canonical looping versions.

Community
  • 1
  • 1
Kaganar
  • 6,540
  • 2
  • 26
  • 59
  • So can we say this is dup of any of them? they all refer to the same point. – gbianchi Apr 10 '12 at 19:09
  • Probably, but it's a common question that doesn't seem to be easy to search for, so the wider the net, the more likely it'll catch future searches. It's not all bad. -- although, I admit, it doesn't seem THAT hard to search for. – Kaganar Apr 10 '12 at 19:10
1

As nobody answered, there is a solution: 

def square_spiral(total_steps):
    position = (0,0)
    direction = (1,0)
    turn_steps = [floor(((x+2)**2)/4) for x in range(n+2)]
    for step in range(total_steps):
        if (step in turn_steps):
            direction = (-direction[1],direction[0])
        position = tuple(a+b for a,b in zip(position,direction))
    return position

This simulates a walk through the desired path. You start at position (0,0), walk 1 step to the right, 1 step down, 3 steps left, 3 steps up, and so on, following the spiral. To code this, notice that we are changing our direction on steps of numbers 1, 2, 4, 6, 9, 12, 16, 20 and so on. https://oeis.org/ reveals this is the quarter-square integer sequence. So all we need is a loop where each iteration simulates a step, adding the direction to the position and turning it 90º when the step count is part of the sequence.

MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
1

Here's my solution in javascript using inverse sum of 8 and edge numbering

Complexity : O(1) no iteration loop

function spiral(n) {
    // given n an index in the squared spiral
    // p the sum of point in inner square
    // a the position on the current square
    // n = p + a

    var r = Math.floor((Math.sqrt(n + 1) - 1) / 2) + 1;

    // compute radius : inverse arithmetic sum of 8+16+24+...=
    var p = (8 * r * (r - 1)) / 2;
    // compute total point on radius -1 : arithmetic sum of 8+16+24+...

    en = r * 2;
    // points by edge

    var a = (1 + n - p) % (r * 8);
    // compute de position and shift it so the first is (-r,-r) but (-r+1,-r)
    // so square can connect

    var pos = [0, 0];
    switch (Math.floor(a / (r * 2))) {
        // find the face : 0 top, 1 right, 2, bottom, 3 left
        case 0:
            {
                pos[0] = a - r;
                pos[1] = -r;
            }
            break;
        case 1:
            {
                pos[0] = r;
                pos[1] = (a % en) - r;

            }
            break;
        case 2:
            {
                pos[0] = r - (a %en);
                pos[1] = r;
            }
            break;
        case 3:
            {
                pos[0] = -r;
                pos[1] = r - (a % en);
            }
            break;
    }
    console.log("n : ", n, " r : ", r, " p : ", p, " a : ", a, "  -->  ", pos);
    return pos;
}

Demo : Fiddle

davidonet
  • 660
  • 4
  • 17