title: How to perform a 2D Fast Fourier Transform in c++
body: <p>I saw there was a <a href="https://stackoverflow.com/questions/8208974/how-to-perform-fft2d-fast-fourier-transform-2d-r-g-b-color-component">post</a> about this topic, but without any reply.<br>
  How to write a function that performs the <strong>2D Fast Fourier Transform</strong> for a given image f?<br>
  It is possible to assume that the width = 2^m, height = 2^n for some integers m and n, and the input image is already properly padded.<br>
  <strong>Input:</strong> f - An 2D Image represented in Complex Numbers<br>
  <strong>Output:</strong> F - The transformed coefficients, also represented in Complex Numbers</p>
  
  <pre><code>void FFT2D(Complex&lt;double&gt; *f, Complex&lt;double&gt; *F, int width, int height)
  {
  
  }
  </code></pre>
  
  <p>For everyone who think I want you to program it for me:<br>
  I don't. Just want some theoretical explanation of how this should work</p>