Spiral algorithm needed - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Spiral algorithm needed

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.

Comments

  • Josh CodeJosh Code Posts: 675Member
    [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 MoonAnjuna Moon Posts: 89Member
    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

  • lagunalaguna Posts: 1Member
    : 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;
    }
    }



Sign In or Register to comment.