Maths Spiral grid co-ordinates formula
Hello,
I am working on a "simple" google map and have occasionas where my markers are at the same latlng. I have ( with the help of experts here) now got a nice piece of code which looks for markers in my output table with the same latlng and moves them according to a grid.
I want to change this to a spiral where the inital marker is at co-ord 0,0 - and the next marker is one square above, the next is one up one right etc.... here are the co-rds:
Figure 1:
so the grid looks like:
Figure 2:
currently i use sql to update the x/y coords of the subsequent markers by a portion of the map by having a hard coded table
So my question is two fold,
how do you work out the formla for calculating x and y from i... and what is that formula?
We looked at all sorts of interesting mathy websites but nothing really showed how to get the co-ords of a square inside a "square-based" spiral.
From reading about fibonnaci series and stuff i assume the formula has something to do with n and n-1 or the sum of (n-1) + (n-2)
I am working on a "simple" google map and have occasionas where my markers are at the same latlng. I have ( with the help of experts here) now got a nice piece of code which looks for markers in my output table with the same latlng and moves them according to a grid.
I want to change this to a spiral where the inital marker is at co-ord 0,0 - and the next marker is one square above, the next is one up one right etc.... here are the co-rds:
Figure 1:
i x y
0 0 0
1 0 1
2 -1 1
3 -1 0
4 -1 -1
5 0 -1
6 1 -1
7 1 0
8 1 1
9 1 2
10 0 2
11 -1 2
12 -2 2
13 -2 1
14 -2 0
15 -2 -1
16 -2 -2
17 -1 -2
18 0 -2
19 1 -2
20 2 -2
21 2 -1
22 2 0
23 2 1
24 2 2
25 2 3so the grid looks like:
Figure 2:
12 11 10 9 24 | 2
13 2 1 8 23 | 1
14 3 0 7 22 | 0
15 4 5 6 21 |-1
16 17 18 19 20 |-2
-----------------------------------------
-2 -1 0 1 2currently i use sql to update the x/y coords of the subsequent markers by a portion of the map by having a hard coded table
So my question is two fold,
how do you work out the formla for calculating x and y from i... and what is that formula?
We looked at all sorts of interesting mathy websites but nothing really showed how to get the co-ords of a square inside a "square-based" spiral.
From reading about fibonnaci series and stuff i assume the formula has something to do with n and n-1 or the sum of (n-1) + (n-2)
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
TommySzalapski
Note that each "side" of each loop has 2*(level+1) numbers on it (counting each corner as being in only one side).
ASKER
that looks cool! not sure i understand it, but its the end of a long day for me in the UK, i'll have a look tomorrow...
all i will have is the integer 1-n... but that can be used to calculate the position number of each loop?
I will be using Tsql but it has most of the functions you mentioned :)
Many thanks for your help so far, i look forward to co-ords version .
all i will have is the integer 1-n... but that can be used to calculate the position number of each loop?
I will be using Tsql but it has most of the functions you mentioned :)
Many thanks for your help so far, i look forward to co-ords version .
ASKER
also, if it helps the equation, i need the first position to be point 1, as ID's in the data table start as 1,
i am using rownumber() to calculate the ID of set of markers who share the same latlng coords.
i am using rownumber() to calculate the ID of set of markers who share the same latlng coords.
In the graphic you posted, the middle was 0. Is that not the case? Should it be 1?
ASKER
its going to be one when i have finished and need to use the this to update the record set, but i was working using 0, as (0,0) seemed to make more sense...
it can be either really. ! as first position would be easier in the end.
it can be either really. ! as first position would be easier in the end.
ASKER
what i mean is, if you are working with 0 then its cool,
but if it makes it easier to start from 1, then that, too, is cool :)
but if it makes it easier to start from 1, then that, too, is cool :)
ASKER
this is excellent, many thanks. I came back to it awake and got quite far with the SQL... had aproblem for a while because FLoor in SQL converts -0.5 to 0... not -1
so something is not quite right in my code...
using round(x,0) gives the correct value...
here is my code so far to mimic your pseudo c++ code:
and hereis the data it outputs
so something is not quite right in my code...
using round(x,0) gives the correct value...
here is my code so far to mimic your pseudo c++ code:
and hereis the data it outputs
ASKER
actually neither round(x,0) or floor give the correct position 0 when ID is 16.... i get position =16
ASKER
i've got the same in excel... id8 position is 0, but item 24 position is 16, item 48 position is 24....
Hi there,
Yesterday was Australia Day public holiday so I have only now opened up your question.
TommySzalapski has started along the correct path, but it may be easier to track down the solution by noting
1/ each level starts with a perfect square of a odd integer, (1, 9, 25, 49, 81, ...) being
(1 3 5 7 9)^2.
2/ this starting number is just square of ((level*2)-1)
3/ each level is divided up into 4 sides, each side being made up of (level*2) positions (make sure we don't double count the corners). Hence level 1 has four sides of length 2 using up 8 positions so that level 1 uses positions 1 - 8. The first position on the next level is 1 + (4 * 2) which is the 9 or 3^2 for level 2.
4/ The (x, y) coord moves along each side from the coord position at the corners. These corners have coords of (+/- level, +/- level) where there are 4 combinations for the 4 corners.
5/ the direction of movement along each side is for x and y given by
(left, 0) top side or side 0;
(0, down) left side or side 1;
(right, 0) bottom side or side 2; and
(0, up) right side or side 3.
6/ Putting all this together (and starting the count at 0 for the origin and 1-8 for level 1 (because it works better);
corner <= 4 x 2 matrix
1 1
_1 1
_1 _1
1 _1
Note. this is X and Y coords of the corner which starts the 4 sides (for level 1,
coords for other levels are just level * corner).
incr <= 4 x 2 matrix
_1 0
0 _1
1 0
0 1
Note this is X and Y direction of movement along the 4 sides
level <= floor ( (1 + sqrt(counter))/2)
posnInLevel <= counter - (( (level*2) - 1) ^ 2)
side <= floor (posnInLevel / length)
posnInSide <= 1+ posnInLevel - (side * length)
Note need to add one as the first item in a side is next to the corner,
and not in the corner - that is it is one along.
XY (as a vector) <= (level * dirn[side;]) + (posnInSide*incr[side;])
I have set this out in "J" together with an example run for first 52 numbers.
Ian
Yesterday was Australia Day public holiday so I have only now opened up your question.
TommySzalapski has started along the correct path, but it may be easier to track down the solution by noting
1/ each level starts with a perfect square of a odd integer, (1, 9, 25, 49, 81, ...) being
(1 3 5 7 9)^2.
2/ this starting number is just square of ((level*2)-1)
3/ each level is divided up into 4 sides, each side being made up of (level*2) positions (make sure we don't double count the corners). Hence level 1 has four sides of length 2 using up 8 positions so that level 1 uses positions 1 - 8. The first position on the next level is 1 + (4 * 2) which is the 9 or 3^2 for level 2.
4/ The (x, y) coord moves along each side from the coord position at the corners. These corners have coords of (+/- level, +/- level) where there are 4 combinations for the 4 corners.
5/ the direction of movement along each side is for x and y given by
(left, 0) top side or side 0;
(0, down) left side or side 1;
(right, 0) bottom side or side 2; and
(0, up) right side or side 3.
6/ Putting all this together (and starting the count at 0 for the origin and 1-8 for level 1 (because it works better);
corner <= 4 x 2 matrix
1 1
_1 1
_1 _1
1 _1
Note. this is X and Y coords of the corner which starts the 4 sides (for level 1,
coords for other levels are just level * corner).
incr <= 4 x 2 matrix
_1 0
0 _1
1 0
0 1
Note this is X and Y direction of movement along the 4 sides
level <= floor ( (1 + sqrt(counter))/2)
posnInLevel <= counter - (( (level*2) - 1) ^ 2)
side <= floor (posnInLevel / length)
posnInSide <= 1+ posnInLevel - (side * length)
Note need to add one as the first item in a side is next to the corner,
and not in the corner - that is it is one along.
XY (as a vector) <= (level * dirn[side;]) + (posnInSide*incr[side;])
I have set this out in "J" together with an example run for first 52 numbers.
Ian
NB. monad spiral
NB. returns x, y coords for given index into a sequence which
NB. is to be put into a "square" spiral.
spiral =: monad define
NB. direction of level expansion
dirn =. 1 1, _1 1, _1 _1,: 1 _1
NB. direction of increment for next square
incr =. _1 0, 0 _1, 1 0,: 0 1
NB. count of levels (0 1 3 5 7)^2
level =. <. -: >: %: y
NB. side within level and position in side
'side posnInSide' =. 0 1 + |: (0,.+:level)#: y - *: <: +: level
NB. x,y position
(level * side{dirn) + posnInSide*side{incr
)
NB. Ask for coords of various counters
spiral 3
_1 0
spiral 10
0 2
spiral 47
3 2
NB. Provide a header and do the first 52 (starting from 0)
'counter X Y' , (] 6 3 3&":@:,. spiral) i.52
counter X Y
0 0 0
1 0 1
2 _1 1
3 _1 0
4 _1 _1
5 0 _1
6 1 _1
7 1 0
8 1 1
9 1 2
10 0 2
11 _1 2
12 _2 2
13 _2 1
14 _2 0
15 _2 _1
16 _2 _2
17 _1 _2
18 0 _2
19 1 _2
20 2 _2
21 2 _1
22 2 0
23 2 1
24 2 2
25 2 3
26 1 3
27 0 3
28 _1 3
29 _2 3
30 _3 3
31 _3 2
32 _3 1
33 _3 0
34 _3 _1
35 _3 _2
36 _3 _3
37 _2 _3
38 _1 _3
39 0 _3
40 1 _3
41 2 _3
42 3 _3
43 3 _2
44 3 _1
45 3 0
46 3 1
47 3 2
48 3 3
49 3 4
50 2 4
51 1 4
NB. first position in each level for first 15 levels (0, 1 - 14)
'counter X Y' , (] 6 3 3&":@:,. spiral) 0, *: >: +: i. 14
counter X Y
0 0 0
1 0 1
9 1 2
25 2 3
49 3 4
81 4 5
121 5 6
169 6 7
225 7 8
289 8 9
361 9 10
441 10 11
529 11 12
625 12 13
729 13 14
Hi there again,
If you prefer SQL, here is the result in SQL (without and comments because they are included in previous answer). Note the extra work because my SQL doesn't have arrays and indexing.
Note also that the SQL statements fail on counter=0 (ie the center).
If you want it to work on the center - level=0, then you need to insert some max(0, ---) and max(1, ---) to ensure you dont do dived by zero etc.
Also if you want to use this so that the center counter is 1, it is best left as is and just subtract 1 from counter before using this soln. I suspect it you try to modify the algorithm for a 1 index origin and not a zero index origin all hell will break loose. :-)
Ian
If you prefer SQL, here is the result in SQL (without and comments because they are included in previous answer). Note the extra work because my SQL doesn't have arrays and indexing.
Note also that the SQL statements fail on counter=0 (ie the center).
If you want it to work on the center - level=0, then you need to insert some max(0, ---) and max(1, ---) to ensure you dont do dived by zero etc.
Also if you want to use this so that the center counter is 1, it is best left as is and just subtract 1 from counter before using this soln. I suspect it you try to modify the algorithm for a 1 index origin and not a zero index origin all hell will break loose. :-)
Ian
select counter,
X,
Y
from (
select
counter,
floor(0.5 *(1 + sqrt(counter))) as level,
counter - (((2 * calculated level) - 1)**2) as posnInLevel,
floor((calculated posnInLevel) / (2 * calculated level)) as side,
1 + ((calculated posnInLevel) - (calculated side) *
(2 * calculated level) ) as posnInSide,
(floor((calculated side - 1.5)**2) - 1) as dirnX,
1 - (2 * floor(0.5 * calculated side)) as dirnY,
(-0.5) * ((calculated dirnX) + (calculated dirnY)) as incrX,
0.5 * ((calculated dirnX) - (calculated dirnY)) as incrY,
((calculated level) * (calculated dirnX)) +
((calculated posnInSide) * (calculated incrX)) as X,
((calculated level) * (calculated dirnY)) +
((calculated posnInSide) * (calculated incrY)) as Y
from counters
)
order by counter;
which producers the following listing from a table with rows containing counter 1 - 52.
counter X Y
----------------------------
1 0 1
2 -1 1
3 -1 0
4 -1 -1
5 0 -1
6 1 -1
7 1 0
8 1 1
9 1 2
10 0 2
11 -1 2
12 -2 2
13 -2 1
14 -2 0
15 -2 -1
16 -2 -2
17 -1 -2
18 0 -2
19 1 -2
20 2 -2
21 2 -1
22 2 0
23 2 1
24 2 2
25 2 3
26 1 3
27 0 3
28 -1 3
29 -2 3
30 -3 3
31 -3 2
32 -3 1
33 -3 0
34 -3 -1
35 -3 -2
36 -3 -3
37 -2 -3
38 -1 -3
39 0 -3
40 1 -3
41 2 -3
42 3 -3
43 3 -2
44 3 -1
45 3 0
46 3 1
47 3 2
48 3 3
49 3 4
50 2 4
51 1 4
52 0 4
Hi there,
just a typo
If you want it to work on the center - level=0, then you need to insert some max(0, ---) and max(1, ---) to ensure you dont do dived by zero etc.
=>
If you want it to work on the center - level=0, then you need to insert some max(0, ---) and max(1, ---) code to ensure you dont do divide by zero etc.
just a typo
If you want it to work on the center - level=0, then you need to insert some max(0, ---) and max(1, ---) to ensure you dont do dived by zero etc.
=>
If you want it to work on the center - level=0, then you need to insert some max(0, ---) and max(1, ---) code to ensure you dont do divide by zero etc.
ASKER
I am still working on this, converting to T-SQL...
still need help with logic for this as my X,Y are not coming out correctly.
Got to do some major upgrade work over next two days, so will come back on weds with updates of my code so far, and outputs
still need help with logic for this as my X,Y are not coming out correctly.
Got to do some major upgrade work over next two days, so will come back on weds with updates of my code so far, and outputs
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Excellent work from both experts,
I have replicated the logic and plan to write a function which can calculate the offset from center.
Thanks both for your help.
I have replicated the logic and plan to write a function which can calculate the offset from center.
Thanks both for your help.