Algorithm to rotate an image 90 degrees in place? (No extra memory)

Question

This might help: In-place matrix transposition.

(You might also have to do some mirroring after the transposition, as rlbond mentions).

If you read the image from memory in "the wrong order", it's essentially the same as rotating it. This may or may not be suitable for whatever you're doing, but here goes:

image[y][x] /* assuming this is the original orientation */
image[x][original_width - y] /* rotated 90 degrees ccw */
image[original_height - x][y] /* 90 degrees cw */
image[original_height - y][original_width - x] /* 180 degrees */

Not sure what processing you will do after the rotation, but you can leave it alone and use another function to read rotated pixel from the original memory.

uint16_t getPixel90(Image *img, int x, int y) 
{
    return img->data[(img->height - x) * img->width + y];
}

Where input parameter x and y has swapped dimension from original

This problem took me quite some time but if you have the right approach it is very simple.

Note this only works for a square matrix. A rectangle will require you to use the other algorithm (transpose and flip). If you want to do it in place, that may need you to temporarily resize the array.

Simplifying the problem

Consider the following matrix:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

Rotate 90 degrees, and look only at the corners (numbers 1, 4, 16 and 13). If you have problems visualizing it, help yourself with a post-it note.

Now, let's consider the following one:

1 - - 2
- - - -
- - - -
4 - - 3

Rotate it 90 degrees, and notice how the numbers get rotated in a circular manner: 2 becomes 1, 3 becomes 2, 4 becomes 3, 1 becomes 4.

Rotating corners

In order to rotate corners, it is necessary to define all corners in terms of the first corner:

• 1st corner would be (i, j)
• 2nd corner would be (SIZE - j, i)
• 3rd corner would be (SIZE - i, SIZE - j)
• 4th corner would be (j, SIZE - i)

Note that arrays are 0 based, therefore SIZE will need to be 0 based as well. (meaning, you will need to subtract 1).

Now that you understood the idea of rotating corners, we will expand the idea of "rotating corners" to "rotating quadrants". The same principle holds.

Code

You will need to make sure no number if overwritten. Meaning, you will need to rotate 4 numbers at a time simultaneously.

#include <algorithm>
#include <numeric>
#include <vector>

using std::iota;
using std::swap;
using std::vector;

// Rotates 4 numbers.
// e.g: 1, 2, 3, 4 becomes 4, 1, 2, 3
// int& means numbers are passed by reference, not copy.
void rotate4(int &a, int &b, int &c, int &d)
{
   swap(a, b);
   swap(b, c);
   swap(c, d);
}

void rotateMatrix(vector<vector<int>>& m) {
    int n = m.size();

    // NOTE: i and j from 0 to n/2 is a quadrant
    for (int i = 0; i < n/2; i++) {
    // NOTE : here + 1 is added to make it work when n is odd
    for (int j = 0; j < (n + 1)/2; j++) {
        int r_i = (n - 1) - i;
        int r_j = (n - 1) - j;

        rotate4(
             m   [i]   [j],
             m [r_j]   [i],
             m [r_i] [r_j],
             m   [j] [r_i]
        );
    }
    }
}

void fillMatrix(vector<vector<int>>& m) {
    int offset = 0;

    for (auto &i : m) {
        iota(i.begin(), i.end(), offset);
        offset += i.size();
    }
}

// Usage:
const int size = 8;
vector<vector<int>> matrix (size, vector<int>(size));
fillMatrix(matrix);
rotateMatrix(matrix);

Printing

To print the matrix you can use:

#include <algorithm>
#include <iostream>
#include <iterator>

using std::copy;
using std::cout;
using std::ostream;
using std::ostream_iterator;
using std::vector;

ostream& operator<<(ostream& os, vector<vector<int>>& m) {
    for (auto const &i : m) {
        copy(i.begin(), i.end(), ostream_iterator<int>(os, " "));
        os << "\n";
    }

    return os;
}

// Usage
cout << matrix;

the real answer: no, u can't without allocating some memory.

or you have to use recursion, which will fail with large images.

however there are methods that require less memory than the image itself

for example, you could take point A (x from 0 to width, y from 0 to height), calculate it's new location, B, copy B to it's new location (C) before replacing it with A, etc..

but, that method would require to keep track of what bytes have already been moved. (using a bitmap of one bit per pixel in the rotated image)

see the wikipedia article, it clearly demonstrates that this cannot be done for non square images: here is the link again: http://en.wikipedia.org/wiki/In-place_matrix_transposition