Are there any algorithms out there that can do a FFT of 2D or XY data (not sure of the exact terminology here), I don't mean XY data like in a graph I mean XY/2D data points like a circle or a smiley face for example.



  • $\begingroup$ If you are asking about taking the Fourier Transform of N-dimensional signals, such as images then yes, it is a widely known approach -> click $\endgroup$ – jojek Sep 2 '14 at 11:57
  • $\begingroup$ This is a 2D case of the 1D FFT, I mean the FFT of X,Y Cartesian coordinate data, that can be plotted in a graph ie. (X,Y) (1,1) (1,2) (2,2) (2,1) (1,1) $\endgroup$ – ejectamenta Sep 2 '14 at 12:21

If there is a notion of "time" or order in your data - for example, if your points are acquired as coordinates on a touch-screen or stylus as someone draws the figure, you can treat your X and Y coordinates as the real and imaginary part of a complex number. Then, this is just an instance of a 1D FFT with complex-valued input.

(In response to the comment that any kind of data could be processed this way, without the need for an explicit "time axis" or "order" in the data)

Data order matters! For example, if you take your data and sort it according to the X coordinate, the real part of your signal (corresponding to the X coordinate) will be an irregularly increasing line - I expect the spectrum to be roughly that of a sawtooth wave. However, if you randomly shuffle your data, the real part of your signal will be like white noise. So the exact same plot will lead to totally different spectra.

  • $\begingroup$ that's a very useful idea, I was more thinking of static data, however there is a kind of time since the coordinates exist as a list or array so the index into the array is a kind of time property $\endgroup$ – ejectamenta Sep 2 '14 at 13:38
  • $\begingroup$ Beware! I have modified my reply to explain why the technique I have mentioned does not work all the time. $\endgroup$ – pichenettes Sep 2 '14 at 14:29
  • $\begingroup$ I was thinking of data derived from image processing anyway, such as object boundaries, these are based on region growing from a local neighbourhood so I don't thing that it will have the problem that you mention $\endgroup$ – ejectamenta Sep 2 '14 at 14:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.