Spiral algorithm needed

Matt Jacobs

Hi,

I need an algorithm that will overlay a spiral on a square array. Basically, an x/y position is stored with respect to this square array, and if given an offset, the position will be moved in a clockwise spiral direction.

eg. a 3x3 square array will have the spiral pattern as:
012
783
654

saying the position was 2,0 then giving an offset of 3 will move it to position 5, giving it an offset of 6 will move it to position 8 etc

I've wracked my brains trying to figure this one out, and I can't seem to find any algorithms out there on the net. Any help would really be appreciated.

Josh Code

[b][red]This message was edited by Josh Code at 2002-9-9 18:15:8[/red][/b][hr]
[b][red]This message was edited by Josh Code at 2002-9-9 18:12:41[/red][/b][hr]
: Hi,
:
: I need an algorithm that will overlay a spiral on a square array. Basically, an x/y position is stored with respect to this square array, and if given an offset, the position will be moved in a clockwise spiral direction.
:
: eg. a 3x3 square array will have the spiral pattern as:
: 012
: 783
: 654
:
: saying the position was 2,0 then giving an offset of 3 will move it to position 5, giving it an offset of 6 will move it to position 8 etc
:
: I've wracked my brains trying to figure this one out, and I can't seem to find any algorithms out there on the net. Any help would really be appreciated.
:


Here is a way you could do it:
[b]Variables[/b]

let c = a counter variable (integer) that counts the value of the number stored in the array at a given point

let x,y = the coordinates of the current point being being processed in the array

let dx,dy = the change in x and y

let dir = the direction of motion (up, down, left, right). This is used to set the dx and dy values

let s = the length of the sides of a particullar "square" within the array. I am talking about the smaller "squares" that would be inside the parimiters of the array that approach the centre of the square. I hope this makes some sence.

let z = a counter for the loop along a straight line on one of the sprial's sides


[b]code segment[/b]

s = the length of the square array (3 for the example you provided)
dir = 0
// direction is initially right
x = 0
y = 0
// top left corner of the array

c = 0
// start the spiral at 0

Loop while the x,y is not the coordinates of the centre of the array

case dir of
0: dx = 1
dy = 0
1: dx = 0
dy = 1
2: dx = -1
dy = 0
3: dx = 0
dy = -1
s = s -1
dir = -1
end of case statement

// now the direction would be updated

add 1 to dir

z = 0

loop while z<s

set array[x,y] to c

if z=0 and dir=1 then subtract 1 from s
add dx to x
add dy to y
add 1 to z
add 1 to c

end of z-loop

end of coordinate loop

I haven't tested that but try that algorithm out. If it doesn't work, tell me about it.

Anjuna Moon

The code below creates the array "position()", which is used to
transform ordinary matrix positions to spiral positions.

123 position(p) 123
456 -> 894
789 765

Matrix position p is (row*n+col) where n is the sidelength of the square matrix. position(p) will give the

To move the value from position 6 (2,1) spiralwise 3 steps, get the new position from position(6+3)

I tried this last night and it works for all matrixes with n>0. Sorry I couldn't put this in proper algorithm terms.

' n is the sidelength of the matrix
n=
For t = 1 To n: position(t) = t: Next
turnfactor(0) = -1 / n: turnfactor(1) = n
toggle = 0
ds = n
cnt = n - 1
cnt_start = n - 1

For t = n + 1 To n * n
position(t) = position(t - 1) + ds
cnt = cnt - 1
If cnt = 0 Then
ds = ds * turnfactor(toggle)
cnt_start = cnt_start - toggle
cnt = cnt_start
toggle = toggle Xor 1
End If
Next

laguna

: The code below creates the array "position()", which is used to
: transform ordinary matrix positions to spiral positions.
:
: 123 position(p) 123
: 456 -> 894
: 789 765
:
: Matrix position p is (row*n+col) where n is the sidelength of the
: square matrix. position(p) will give the
:
: To move the value from position 6 (2,1) spiralwise 3 steps, get the
: new position from position(6+3)
:
: I tried this last night and it works for all matrixes with n>0.
: Sorry I couldn't put this in proper algorithm terms.
:
: ' n is the sidelength of the matrix
: n=
: For t = 1 To n: position(t) = t: Next
: turnfactor(0) = -1 / n: turnfactor(1) = n
: toggle = 0
: ds = n
: cnt = n - 1
: cnt_start = n - 1
:
: For t = n + 1 To n * n
: position(t) = position(t - 1) + ds
: cnt = cnt - 1
: If cnt = 0 Then
: ds = ds * turnfactor(toggle)
: cnt_start = cnt_start - toggle
: cnt = cnt_start
: toggle = toggle Xor 1
: End If
: Next
:
:

Here is a Java version of the above algorithm. However, I put
the array in reverse order for my own purpose.

private static int[] spiralArray(int dimension){

int numberOfItem = dimension*dimension;
int[] spiralArr = new int[numberOfItem];
byte toggle = 0;
int ds = dimension;
int cnt = dimension - 1;
int cntStart = dimension - 1;
for (int i = 1; i <= dimension; i++){
spiralArr[numberOfItem-i] = i;
}

for (int i = numberOfItem - dimension ; i > 0 ; i--){
spiralArr[i - 1] = spiralArr[i] + ds;
cnt = cnt - 1;
if (cnt == 0){
ds = (int)(ds * turnFactor(toggle, dimension));
cntStart = cntStart - toggle;
cnt = cntStart;
toggle = (byte)(toggle^1);
}
}
return spiralArr;
}

/**
*
* @param arg
* @param n
* @return
*/
private static float turnFactor(int arg, float n){
if (arg == 0){
return -1/n;
}else {
return n;
}
}