Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.