title: Algorithm to rotate an image 90 degrees in place? (No extra memory)
body: <p>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 <a href="http://www.cs.nott.ac.uk/~smx/IVIPracticals/exercise1.html" rel="noreferrer">algorithm</a> 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?</p>
  
  <p>Edited to add clarification, because people are asking:</p>
  
  <p>I store an image in the usual format:</p>
  
  <pre><code>// Images are 16 bpp
  struct Image {
      int width;
      int height;
      uint16_t * data;
  };
  
  uint16_t getPixel(Image *img, int x, int y)
  {
      return img-&gt;data[y * img-&gt;width + x];
  }
  </code></pre>
  
  <p>I'm hoping to move the contents of the <code>data</code> array around, then swap over the <code>width</code> and <code>height</code> 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.</p>