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

In an embedded C app, I have a large image that I'd like to rotate by 90 degrees. Currently I use the well-known simple algorithm to do this. However, this algorithm requires me to make another copy of the image. I'd like to avoid allocating memory for a copy, I'd rather rotate it in-place. Since the image isn't square, this is tricky. Does anyone know of a suitable algorithm?

Edited to add clarification, because people are asking:

I store an image in the usual format:

// Images are 16 bpp
struct Image {
    int width;
    int height;
    uint16_t * data;
};

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

I'm hoping to move the contents of the data array around, then swap over the width and height member variables. So if I start with a 9x20 pixel image, then rotate it, I'll end up with a 20x9 pixel image. This changes the stride of the image, which complicates the algorithm a lot.

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;