# On a two dimensional grid is there a formula I can use to spiral coordinates in an outward pattern?

I don't know exactly how to describe it, but in a programmatic way I want to spiral outward from coordinates 0,0 to infinity (for practical purposes, though really I only need to go to about +/-100,000:+/-100,000)

So if this is my grid:

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


I want to spiral in an order sort of like:




etc...


Is there a formula or method of doing this?

Here’s a recipe for finding the coordinates of your position after $n$ steps along the spiral.

It’s simpler to number the positions on the spiral starting at $0$: position $0$ is $\langle 0,0\rangle$, the origin, position $1$ is $\langle 1,0\rangle$, position $2$ is $\langle 1,-1\rangle$, and so on. Using $R,D,L$, and $U$ to indicate steps Right, Down, Left, and Up, respectively, we see the following pattern:

$$RD\,|LLUU\,\|\,RRRDDD\,|LLLLUUUU\,\|\,RRRRRDDDDD\,|LLLLLLUUUUUU\;\|\dots\;,$$

or with exponents to denote repetition, $R^1D^1|L^2U^2\|R^3D^3|L^4U^4\|R^5D^5|L^6U^6\|\dots\;$. I’ll call each $RDLU$ group a block; the first block is the initial $RDLLUU$, and I’ve displayed the first three full blocks above.

Clearly the first $m$ blocks comprise a total of $2\sum_{k=1}^mk=m(m+1)$ steps. It’s also not hard to see that the $k$-th block is $R^{2k+1}D^{2k+1}L^{2k+2}U^{2k+2}$, so that the net effect of the block is to move you one step up and to the left. Since the starting position after $0$ blocks is $\langle 0,0\rangle$, the starting position after $k$ full blocks is $\langle -k,k\rangle$.

Suppose that you’ve taken $n$ steps. There is a unique even integer $2k$ such that $$2k(2k+1)<n\le(2k+2)(2k+3)\;;$$ at this point you’ve gone through $k$ blocks plus an additional $n-2k(2k+1)$ steps. After some straightforward but slightly tedious algebra we find that you’re at

$$\begin{cases} \langle n-4k^2-3k,k\rangle,&\text{if }2k(2k+1)<n\le(2k+1)^2\\ \langle k+1,4k^2+5k+1-n\rangle,&\text{if }(2k+1)^2<n\le 2(k+1)(2k+1)\\ \langle 4k^2+7k+3-n,-k-1\rangle,&\text{if }2(k+1)(2k+1)<n\le4(k+1)^2\\ \langle -k-1,n-4k^2-9k-5\rangle,&\text{if }4(k+1)^2<n\le2(k+1)(2k+3)\;. \end{cases}$$

To find $k$ easily, let $m=\lfloor\sqrt n\rfloor$. If $m$ is odd, $k=\frac12(m-1)$. If $m$ is even, and $n\ge m(m+1)$, then $k=\frac{m}2$; otherwise, $k=\frac{m}2-1$.

• Yikes that is a bit more complex than I expected, hopefully I can put it to use! Jun 26, 2012 at 2:40
• Is there a generalization/extension of this to an $d$-dimensional outward spiral? Oct 16, 2017 at 14:10
• @phdmba7of12 It doesn't seem obvious how this spiral would go. Could you provide an example for a 3x3x3 cube? Nov 29, 2018 at 21:36
• @Kaligule ... i agree. not at all obvious. thus my question Nov 30, 2018 at 19:14

Here is some code that finds the $n$-th point in the spiral. Unfortunately it spirals the other way but perhaps it helps anyway.

function spiral(n)
k=ceil((sqrt(n)-1)/2)
t=2*k+1
m=t^2
t=t-1
if n>=m-t then return k-(m-n),-k        else m=m-t end
if n>=m-t then return -k,-k+(m-n)       else m=m-t end
if n>=m-t then return -k+(m-n),k else return k,k-(m-n-t) end
end

• I think it would be alright to negate the y coordinate (y *= -1), given that the first element is located at (0,0), in order to make it spiral the other way around as the question has requested. Dec 14, 2017 at 16:08

If you are looking for a no-if solution and a formula, I was able to find this one:

$$A = ||x| - |y|| + |x| + |y|;$$

$$R = A^2 + sgn(x + y + 0.1)*(A + x - y) + 1;$$

$$x, y \in \mathbb{Z}$$

$$sgn$$sign function

<?php

$$n = 4;$$from = -intval($$n / 2) - 1;$$to = -$$from + ($$n % 2) - 2;

for ($$x =$$to; $$x >$$from; $$x--) { for (y = to; y > from; y--) { result = pow((abs(abs(x) - abs(y)) + abs(x) + abs(y)), 2) + abs(x + y + 0.1) / (x + y + 0.1) * (abs(abs(x) - abs(y)) + abs(x) + abs(y) + x - y) + 1; echo$$result . "\t";
}
echo "\n";
}


which prints

7   8   9   10
6   1   2   11
5   4   3   12
16  15  14  13


https://repl.it/repls/DarkslategraySteepBluebottle

As you can see from Brian's answer, the formula for it is complex. But there is a very simple recursive algorithm you can use:

• for n = 0, start at (0,0), facing east
• for n = 1, the spiral is (0,0): east; (0,1): east
• for n > 1, calculate the spiral for n-1. Look to your right.
• if the space is occupied by a point of the spiral, take a step forward
• if the space is free, turn right, then take a step forward

It is very easy to extend to other starting orientations, and also to create a left turning spiral. Here is a Scala implementation of the algorithm. I tried to optimize it for readability, not efficiency.

object Orientation extends Enumeration {
val north = Value("north")
val east = Value("east")
val south = Value("south")
val west = Value("west")

val orderedValues = Vector(north, east, south, west)

def turnRight(fromOrientation: Orientation.Value): Orientation.Value = orderedValues(
(orderedValues.indexOf(fromOrientation) + 1) % 4)

def turnLeft(fromOrientation: Orientation.Value): Orientation.Value = orderedValues(
(orderedValues.indexOf(fromOrientation) +3) % 4)

def oneStepOffset(inOrientation: Orientation.Value): (Int, Int) = inOrientation match {
case Orientation.north => (0, 1)
case Orientation.east => (1, 0)
case Orientation.south => (0, -1)
case Orientation.west => (-1, 0)
}
}

object Direction extends Enumeration {
val straight = Value("straight")
val right = Value("right")
val left = Value("left")
}

def spiral(n: Int, initialOrientation: Orientation.Value = Orientation.east, turningDirection: Direction.Value = Direction.right): List[(Int, Int)] = {

if (turningDirection == Direction.straight) throw new IllegalArgumentException("The spiral must turn left or right")
if (n < 0) throw new IllegalArgumentException("The spiral only takes a positive integer as the number of steps")

class Step(
val position: (Int, Int),
val orientation: Orientation.Value)

def nextPosition(lastStep: Step, direction: Direction.Value): (Int, Int) = {
val newOrientation = direction match {
case Direction.straight => lastStep.orientation
case Direction.right => Orientation.turnRight(lastStep.orientation)
case Direction.left => Orientation.turnLeft(lastStep.orientation)
}

val offset = Orientation.oneStepOffset(newOrientation)

return (
lastStep.position._1 + offset._1,
lastStep.position._2 + offset._2)
}

def takeStep(lastStep: Step, occupiedPositions: Seq[(Int, Int)]): Step = {
val positionAfterTurning = nextPosition(lastStep, turningDirection)
val nextStep = if (occupiedPositions.contains(positionAfterTurning)) {
new Step(nextPosition(lastStep, Direction.straight), lastStep.orientation)
} else {
val newOrientation = turningDirection match {
case Direction.left => Orientation.turnLeft(lastStep.orientation)
case Direction.right => Orientation.turnRight(lastStep.orientation)
}
new Step(positionAfterTurning, newOrientation)
}
return nextStep
}

def calculateSpiral(upTo: Int): List[Step] = upTo match {
case 0 => new Step((0, 0), initialOrientation) :: Nil
case 1 => new Step(Orientation.oneStepOffset(initialOrientation), initialOrientation) :: new Step((0, 0), initialOrientation) :: Nil
case x if x > 1 => {
val spiralUntilNow = calculateSpiral(upTo - 1)
val nextStep = takeStep(spiralUntilNow.head, spiralUntilNow.map(step => step.position))
(nextStep :: spiralUntilNow)
}
}

return (calculateSpiral(n).map(step => step.position)).reverse
}

• I don't have the code handy, but this is basically what I ended up doing. By persisting a few variables it's also fairly straightforward to allow for pausing/resuming. Jan 15, 2015 at 16:33

Python implementation of a spiral coordinate generator based on lhf's answer:

def GenSpiral(x, y):
for n in range(numpy.inf):
k = math.ceil((math.sqrt(n) - 1) / 2.0)
t = 2 * k + 1
m = t ** 2
t = t - 1
if n >= m - t:
yield x + k - (m - n), y - k
else:
m = m - t
if n >= m - t:
yield x + -k, y -k + (m - n)
else:
m = m - t
if n >= m - t:
yield x -k + (m - n), y + k
else:
yield x + k, y + k - (m - n - t)