Rotate 2D rectangular array in-place

Question

I have an non-square array like this:

const int dim1 = 3, dim2 = 4;
int array[12] = { 1, 2, 3, 
                  4, 5, 6,
                  7, 8, 9,
                 10,11,12};

and I need to convert it to:

{3,6,9,12,
 2,5,8,11,
 1,4,7,10}

that is, rotate/shuffle it counter-clockwise (or clockwise, the algorithm should be similiar).

The algorithm should use a minimal amount of space. I have to rotate an image in an extremely memory-constrained environment, so the less space the better. Speed is not as big an issue.

Answer 1

You can transpose the matrix in-place (see http://en.wikipedia.org/wiki/In-place_matrix_transposition) and then reverse the rows which is trivial.

Answer 2

The 2D rotation formula is:

x' = x cos f - y sin f
y' = y cos f + x sin f

If you only rotate in 90° steps, the resulting formula becomes:

x' = -y
y' =  x

Since the array isn't square you'll have to look for assignment cycles, i.e. element (0, 0) gets assigned element (2, 0) which in turn gets assigned (2, 2) etc. You'll need to assign each cycle at the "same" time.

Thus to rotate the whole array you'll do something like (pseudo-code):

// this function rotates 90 degrees
point successor(const point &p)
{
  return (-p.y, p.x);
}

// this function rotates 90 degrees in opposite direction
point predecessor(const point &p)
{
  return (p.y, -p.x);
}

void replace_cycle(const point &start)
{
  int data = get_data(start);
  point x = predecessor(start);
  while(x != start)
  {
    set_data(successor(x), get_data(x));
    x = predecessor(x);
  }
  set_data(successor(start), data);
}

void rotate_in_place()
{
  list<point> l;
  find_cycles(l);
  foreach(c in l)
  {
    replace_cycle(c);
  }
}

Answer 3

Not rotating at all may be an option. You just set a flag that would give the way the matrix should be read.

The drawback is that if that image must be provided to some display device or such with fixed direction, that may not be possible.

Answer 4

You can use xor to use no additional memory.

// Switch a and b
int a;
int b;
a ^= b;
b ^= a;
a ^= b;

Then you can use a simple for loop to make your whole matrix.