Counting Turns in a Rectilinear Spiral Graph

205 Views Asked by At

So consider a rectangular spiral graph which starts at the origin, goes right 1, up 1, left 2, down 2, right 3, ... (in units). How can we tell how many turns there have been given a point? For example, if we give the point $(1,1)$, then there have been a total of $1$ turn to get to that point. If we give $(1,-1)$, there have been $4$ turns to get there. And if it is $(10,10)$ there have been $37$ turns. Additionally, what if we were given points in the middle. For example for the point $(0,1)$ the number of turns would be $ 2$. I calculated these visually, but I am looking for a mathematical solution, possibly a closed form.

I think I have figured out a sort of algorithm that would give me specific points, but this doesn't account for the points in the middle. If $x=0$ and $y=0$ then $0$. If $x>0$ and $y>0$ then $\operatorname{abs}(y)\cdot 4-3$. If $x>0$ and $y<0$ then $\operatorname{abs}(y)\cdot 4$. If $x<0$ and $y>0$ then $\operatorname{abs}(y)\cdot 4-2$. If $x<0$ and $y<0$ then $\operatorname{abs}(y)\cdot 4-1$.

I'm not sure if the works in all cases, but this is my start. However, I am actually looking for a solution that doesn't have these multiple cases. However, if there is one with less cases, I am still interested Also, my algorithm doesn't take into account if the point lies in the middle. For example if the point is $(3,5)$ my solution will give $17$, while the correct result is $18$.

Something I found was https://oeis.org/A242601 which can be used to find the turning points. Not sure how this helps though.

1

There are 1 best solutions below

0
On

Most of the corners lie on circles of radius $k\sqrt 2$, as shown in the diagram below:

enter image description here

There is a set of "rogue corners" (coloured red) that do not lie on these circles.

The value of $(k-1)$ gives you the number of complete turns made around the origin, but this is not the same as the number of "turns" as you describe them. Your "turns" are in fact "right-angle anti-clockwise turns," but we can deal with that.

The well-behaved corners lie on the line $y=x$ or the line $y=-x$. For a well-behaved corner with coordinates $(x,y)$ you can therefore identify the value of $k$ by calculating:

$$k=|x|$$

A more general point $(x,y)$ will lie between two corners, and you can identify the value of $k$ by this simple way:

$$k=\max(|x|,|y|)$$

This procedure, however, gives an incorrect $k$ value for the rogue corners.

Having identified the $k$ value, we then need to find the angle $\alpha$ turned anticlockwise from the positive $x$-axis. Setting $\alpha = \arctan(\frac yx)$ seems obvious, but we need to take more care to identify the quadrant and to avoid problems with division by zero. I therefore suggest the following recipe:

$$\alpha=\begin{cases} 0& x>0, y=0\\ \arctan(\frac yx)& x>0, y>0\\ \frac {\pi}2 & x=0, y>0 \\ \pi+\arctan(\frac yx)& x<0 \\ \frac {3\pi}2& x=0, y<0 \\ 2\pi+\arctan(\frac yx)& x>0, y<0 \end{cases}$$

The total angle turned is given by:

$$\theta = 2\pi(k-1)+\alpha$$

You turn a corner at $\theta=\frac {\pi}4,\frac {3\pi}4,\frac {5\pi}4,...$ etc.

If $n$ is the number of turns we have $\theta=\frac {(2n-1)\pi}4$

Rearrange to get $n = \frac {(\frac {4\theta}{\pi}+1)}2 = \frac {2\theta}{\pi} + \frac 12$

$n = \lfloor {\frac {2\theta}{\pi} + \frac 12 }\rfloor$

I tested this using a spreadsheet and found that this worked for all corners except for the rogue corners. Their $n$ value was exactly 4 more than it should have been (that is 4 right-angle turns or one complete turn).

Now the rogue corners lie between the line $y=-x$ and the $x$-axis. To deal with them I adapted the calculation for $\alpha$ so that points in that region would have their $\alpha$ value reduced by $2 \pi$:

$$\alpha=\begin{cases} 0& x>0, y=0\\ \arctan(\frac yx)& x>0, y>0\\ \frac {\pi}2 & x=0, y>0 \\ \pi+\arctan(\frac yx)& x<0 \\ \frac {3\pi}2& x=0, y<0 \\ 2\pi+\arctan(\frac yx)& x>0, y<0, y \le -x \\ \arctan(\frac yx)& x>0, y<0, y>-x \end{cases}$$

I tested this using a spreadsheet for all points. Although it worked for all the corners (including rogue corners), it did not for the other points in the region between the line $y=-x$ and the $x$-axis.

I adapted the calculation for $\alpha$ further, setting the $\alpha$ of the rogue corners to $-\frac{\pi}4}:

$$\alpha=\begin{cases} 0& x>0, y=0\\ \arctan(\frac yx)& x>0, y>0\\ \frac {\pi}2 & x=0, y>0 \\ \pi+\arctan(\frac yx)& x<0 \\ \frac {3\pi}2& x=0, y<0 \\ 2\pi+\arctan(\frac yx)& x>0, y<0, y \le -x \\ -\frac{\pi}4& x>0, y<0, y=-x+1 \\ \arctan(\frac yx)& x>0, y<0, y>-x+1 \end{cases}$$

Finally I had to adapt the formula for $n$ to a ceiling function rather than a floor:

$n = \lceil {\frac {2\theta}{\pi} + \frac 12 }\rceil$

This now works for all points.