Discussion:
Spiral positions in cartesian coordinates
Ludovicus
2010-06-01 20:10:43 UTC
Raw Message
Is there an algorithm to transform the numbers of an Ulam
spiral to its integer cartesian coordinates? Example:
The origin of coordinates is the same zero of spiral.

________________________________________
| | |
| | |
| 16 | 15 | 14 |
13 | 12 |
| | |
| | |

---------------------------------------------------------------------
| | |
| | |
| 17 | 4 | 3 |
2 | 11 |
| | |
| | |

---------------------------------------------------------------------
| | |
| | |
| 18 | 5 | 0 |
1 | 10 |
| | |
| | |

---------------------------------------------------------------------
| | |
| | |
| 19 | 6 | 7 |
8 | 9 |
| | |
| | |

---------------------------------------------------------------------
Ludovicus
2010-06-01 20:40:15 UTC
Raw Message
Post by Ludovicus
Is there an algorithm to transform the numbers of an Ulam
The origin of coordinates is the same zero of spiral.
_______________________________________________________________________
| |         |             |             | |
|         |         |         | | |
| 16     |     15     | 14 | 13 | 12 |
| |              |             |             | |
|             |             | | | |
---------------------------------------------------------------------
|             |             | | | |
|             |             | | | |
|     17    |      4      |      3     | 2 | 11 |
|         | | | | |
|             |             | | | |
-----------------------------------------------------------------------|
| | | | | |
| | | | | |
|     18      |      5      | 0 | 1 | 10 |
|             |             | | | |
|         |           |           | | |
-----------------------------------------------------------------------
|             |             | | | |
|             |             | | | |
| 19 | 6 | 7 | 8 | 9 |
| | | | | |
|             |             | | | |
-----------------------------------------------------------------------|
|         |           |           | | |
|           | | | | |
|     20      |     21      | 22 | 23 | 24 |
|             |             | | | |
| | | | | |
---------------------------------------------------------------------
JEMebius
2010-06-01 22:27:23 UTC
Raw Message
Post by Ludovicus
Is there an algorithm to transform the numbers of an Ulam
The origin of coordinates is the same zero of spiral.
_______________________________________________________________________
| | | | | |
| | | | | |
| 16 | 15 | 14 | 13 | 12 |
| | | | | |
| | | | | |
---------------------------------------------------------------------
| | | | | |
| | | | | |
| 17 | 4 | 3 | 2 | 11 |
| | | | | |
| | | | | |
-----------------------------------------------------------------------|
| | | | | |
| | | | | |
| 18 | 5 | 0 | 1 | 10 |
| | | | | |
| | | | | |
-----------------------------------------------------------------------
| | | | | |
| | | | | |
| 19 | 6 | 7 | 8 | 9 |
| | | | | |
| | | | | |
-----------------------------------------------------------------------|
| | | | | |
| | | | | |
| 20 | 21 | 22 | 23 | 24 |
| | | | | |
| | | | | |
---------------------------------------------------------------------
Of course there is such an algorithm. If it is ever to be caught in a single formula, this
formula necessarily involves Floor and/or Ceiling functions.

Hint:
Departing from 0 in the upward left (NW) direction one has the even integral squares.
Departing from 1 in the SO direction one has the odd integral squares.
Departing from 0 in the SW direction one has 0 = 0*1, 6 = 2*3, 20 = 4*5, 42 = 6*7 etc.
Departing from 0 in the NE direction one has 0 = -1*0, 2 = 1*2, 12 = 3*4, 30 = 5*6 etc.

Good luck: Johan E. Mebius
James Waldby
2010-06-02 16:56:04 UTC
Raw Message
Post by JEMebius
Is there an algorithm to transform the numbers of an Ulam spiral to
its integer cartesian coordinates? Example: The origin of
coordinates is the same zero of spiral.
[snip big version of
16__15__14__13__12
17___4___3___2__11
18___5___0___1__10
19___6___7___8___9
20__21__22__23__24 ]
Post by JEMebius
Of course there is such an algorithm. If it is ever to be caught in a
single formula, this formula necessarily involves Floor and/or Ceiling
functions.
...
Post by JEMebius
Departing from 0 in the upward left (NW) direction one has the even
integral squares. Departing from 1 in the SO direction one has the odd
integral squares. Departing from 0 in the SW direction one has 0 = 0*1,
6 = 2*3, 20 = 4*5, 42 = 6*7 etc. Departing from 0 in the NE direction
one has 0 = -1*0, 2 = 1*2, 12 = 3*4, 30 = 5*6 etc.
Thanks for that information. But the question was: If I have the
number on the spiral which are the cartesian coordinates?.
Otherwise, having the coordinates which is the number?. [...]
[Eg
n X Y
11 2 1
19 -2 -1
24 2 -2 ]

The rules that Johan mentioned allow calculating such coordinates,
and are clear enough (except for the 'SO' typo that should be 'SE').
From the rules: Given n, compute s = floor(sqrt(n)).
Case 0, s even: let b = s/2.
Case 0.a, n < s*(s+1): x,y = -b, b-n+s^2.
Case 0.b, n >= s*(s+1): x,y = -b+n-s*(s+1), -b.
Case 1, s odd: let b = (s+1)/2.
Case 1.a, n < s*(s+1): (etc)

Two example calcs:
If n=19, s=4, b=2, and 19 < 4*5. By case 0.a,
x = -b = -2, y = b-n+s^2 = 2-19+16 = -1; x,y = -2,-1.

If n=24, s=4, b=2, and 24 > 4*5. By case 0.b,
x = -b+n-s*(s+1) = -2+24-20 = 2, y = -b = -2; x,y = 2,-2.

For the other question, coordinates-to-number, you could
also have 4 cases, N-S-E-W, like (|x| > |y|: x>0; x<0)
and (|y| >= |x|: y>0; y<0).
--
jiw
Rob Johnson
2010-06-03 19:10:13 UTC
Raw Message
Post by Ludovicus
Is there an algorithm to transform the numbers of an Ulam
The origin of coordinates is the same zero of spiral.
_______________________________________________________________________
| | | | | |
| | | | | |
| 16 | 15 | 14 | 13 | 12 |
| | | | | |
| | | | | |
---------------------------------------------------------------------
| | | | | |
| | | | | |
| 17 | 4 | 3 | 2 | 11 |
| | | | | |
| | | | | |
-----------------------------------------------------------------------|
| | | | | |
| | | | | |
| 18 | 5 | 0 | 1 | 10 |
| | | | | |
| | | | | |
-----------------------------------------------------------------------
| | | | | |
| | | | | |
| 19 | 6 | 7 | 8 | 9 |
| | | | | |
| | | | | |
-----------------------------------------------------------------------|
| | | | | |
| | | | | |
| 20 | 21 | 22 | 23 | 24 |
| | | | | |
| | | | | |
---------------------------------------------------------------------
Index to position
-----------------
n -> (x,y)

0 -> (0,0)

for n > 0,

sqrt(n)+1
m = floor( --------- )
2

k = n - 4m(m-1)

1 <= k <= 2m -> (x,y) = (m,k-m)

2m <= k <= 4m -> (x,y) = (3m-k,m)

4m <= k <= 6m -> (x,y) = (-m,5m-k)

6m <= k <= 8m -> (x,y) = (k-7m,-m)

Position to index
-----------------
(x,y) -> n

m = max(|x|,|y|)

x = m -> n = 4m(m-1) + m + y except if y = -m

y = m -> n = 4m(m-1) + 3m - x

x = -m -> n = 4m(m-1) + 5m - y

y = -m -> n = 4m(m-1) + 7m + x

Rob Johnson <***@trash.whim.org>
take out the trash before replying
to view any ASCII art, display article in a monospaced font
c***@gmail.com
2018-02-12 22:55:40 UTC
Raw Message
float ulam_spiral(vec2 p)
{
float x = abs(p.x);
float y = abs(p.y);
bool q = x > y;

x = q ? x : y;
y = q ? p.x + p.y : p.x - p.y;
y = abs(y) + 4. * x * x + 1.;
x *= 2.;

return q
? (p.x > 0. ? y - x - x : y)
: (p.y > 0. ? y - x : y + x);
}

vec2 inverse_ulam(float u)
{
float r = sqrt(u);
float m = mod(r, 1.);
float p = mod(r * .5, 1.) > .5 ? 1. : -1.;
float s = p * 1.5 - m * p * 2.;
float x = m < .5 ? r * .5 * p : r * s;
float y = m > .5 ? r * .5 * p : r * p - r * s;

return vec2(x, y);
}

I wrote such a thing, though I’ve not made use of it yet. This code is in GLSL, a simple c subset for GPU. You can copy and paste this on glslsandbox.com to test it out.

Rob’s solution looks more numerically stable and elegant than my hacks, although I do enjoy my application of the residual for the inverse.

What are you using this for, Rob?