'Spiral algorithm needed' Thread RSS Feed

Spiral algorithm needed

Sun, 08 Sep 2002 02:48:45 -0800

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.

Re: Spiral algorithm needed

Mon, 09 Sep 2002 18:06:08 -0800

This message was edited by Josh Code at 2002-9-9 18:15:8

This message was edited by Josh Code at 2002-9-9 18:12:41

: 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:
Variables

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

code segment

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.

Re: Spiral algorithm needed

Tue, 10 Sep 2002 04:57:17 -0800

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

Re: Spiral algorithm needed

Tue, 02 Dec 2008 20:19:42 -0800

: 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;
}
}