Print 2-D Array in clockwise expanding spiral from center

Question

I have an guaranteed to be a perfect square matrix. I want to start at the center of the matrix in this case it would be matrix[2][2], I know how to figure the center (int)(dimensions / 2). I need to output the contents of the array in this following outward spiral pattern. Of course the algorithm should work with any perfect square matrix. I wasn't sure if this algorithm already existed and I didn't want to re-invent the wheel.

int dimensions / 2;

21 22 23 24 25
20 7  8  9  10
19 6  1  2  11
18 5  4  3  12 
17 16 15 14 13

The output for this example should be

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Solution 1

Let's identify the patterns first ..

Even-Size Square Matrix, Example: 4x4

  07 > 08 > 09 > 10
  ^               v
  06  (01)> 02   11
  ^          v    v
  05 < 04 < 03   12
                  v
 [16]< 15 < 14 < 13

Starting Point: [2, 2] ~ [SIZE/2, SIZE/2]

Ending Point: [4, 1] ~ [SIZE, 1]

Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
        + 3 for Count = SIZE-1

Odd-Size Square Matrix, Example: 5x5

  21 > 22 > 23 > 24 >[25]
  ^
  20   07 > 08 > 09 > 10
  ^    ^               v
  19   06  (01)> 02   11
  ^    ^          v    v
  18   05 < 04 < 03   12 
  ^                    v
  17 < 16 < 15 < 14 < 13

Starting Point: [2, 2] ~ [⌊SIZE/2⌋, ⌊SIZE/2⌋]

Ending Point: [1, 5] ~ [1, SIZE]

Chains: Count(K-chain)=2 for K = 1..(SIZE-2)
        + 3 for Count = SIZE-1

Live Code

void print_spiral (int ** matrix, int size)
{
    int x = 0; // current position; x
    int y = 0; // current position; y
    int d = 0; // current direction; 0=RIGHT, 1=DOWN, 2=LEFT, 3=UP
    int c = 0; // counter
    int s = 1; // chain size

    // starting point
    x = ((int)floor(size/2.0))-1;
    y = ((int)floor(size/2.0))-1;

    for (int k=1; k<=(size-1); k++)
    {
        for (int j=0; j<(k<(size-1)?2:3); j++)
        {
            for (int i=0; i<s; i++)
            {
                std::cout << matrix[x][y] << " ";
                c++;

                switch (d)
                {
                    case 0: y = y + 1; break;
                    case 1: x = x + 1; break;
                    case 2: y = y - 1; break;
                    case 3: x = x - 1; break;
                }
            }
            d = (d+1)%4;
        }
        s = s + 1;
    }
}

Solution 2

As this smells like homework then no code or direct answer instead just few hints:

You can look at this as an turtle problem:

Let m be movement by 1 cell and r be rotation by 90 degrees in your spiral direction (CW or CCW). then the spiral can be encoded as series of turtle commands forming this pattern (from the start point):

    m,r,m,r, 
    m,m,r,m,m,r,
    m,m,m,r,m,m,m,r,
    m,m,m,m,r,m,m,m,m,r,
    m,m,m,m,m,r 

As you can see you start with 1x move then rotate after two repetition you switch to 2x move, after 2 moves switch to 3x move,... and so on. This can be done with just few for loops (or just by one with some proper iterations and stopping when matrix number of cells is hit ... or the endpoint corner is hit)

You need to handle even/odd matrix sizes

for odd matrix sizes is the middle point easy. For even sizes it is a bit more complicated. if you use CW rotation then use the rounded down division result of halving the size and start with moving to the right. (if you need different spiral then you need to add +1 to x and/or y and change starting direction) so the spiral will stay centered.

So If you got even sized matrix then the last movement is twice if you got odd size then the last movement is there just once (like in this example)

rotation

Have direction stored as 2D vector. for example d=(+1,0) means right. to rotate 2D vector you just swap coordinates and negate one axis (which one means the CW/CCW). For example (x,y) -> (y,-x)

movement

Store current position as 2D vector too. The movement is just adding current direction vector to it.

Have fun with solving this ...

Comments

[Suman g]

Would some one please explain what does it mean Chains: Count(K-chain)=2 for K = 1..(SIZE-2) + 3 for Count = SIZE-1

[Khaled.K]

@Sumang if you look at where the spiral starts, the number of steps it takes each time before it turns increase by 1 every 2 turns basically.. the formula is how the number of steps in each direction is taken before turning is calculated