Rotate a 2D rectangular grid in place

Question

I have a 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} 

i.e. rotate / shuffle it counterclockwise (or clockwise, the algorithm should be similar).

The algorithm should use minimal space. I have to rotate the image in an environment with limited memory, so the less space, the better. Speed ​​is not such a big problem.

Answer 1

You can drag the matrix into place (see http://en.wikipedia.org/wiki/In-place_matrix_transposition ), and then flip the rows that are trivial.

Answer 2

Two-dimensional rotation formula:

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

If you just rotate in 90 ° increments, the final formula will look like this:

 x' = -y y' = x 

Since the array is not square, you have to look for destination loops, i.e. element (0, 0) receives the assigned element (2, 0), which in turn receives the assigned (2, 2), etc. You will need to assign each cycle at the same time.

So in order to rotate the whole array, you will do something like (pseudocode):

 // this function rotates 90 degrees point successor(const point &p) { return (-py, px); } // this function rotates 90 degrees in opposite direction point predecessor(const point &p) { return (py, -px); } 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

No rotation at all can be an option. You just set the flag, which will make it possible to read the matrix.

The disadvantage is that if this image should be provided to any display device or such with a fixed direction, this may not be possible.

Answer 4

You can use xor to use extra memory no .

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

Then you can use a simple for loop to create your entire matrix.