2D DFT of Hexagonally Sampled Grid

Question

Is there a good way to perform a 2D FFT of discrete data on a hexagonally sampled grid? The best method I've got so far involves oversampling the hex grid to a rectangular grid, and performing the 2D FFT on the oversampled grid.

data is stored like

01 02 03 04
05 06 07 08
09 10 11 12

Which represents a hex grid of staggered rows:

01 -- 02 -- 03 -- 04 --
-- 05 -- 06 -- 07 -- 08
09 -- 10 -- 11 -- 12 --

The oversampling is performed in the frequency domain.

1. Calculate 1D FFT of each row
2. Perform the oversampling in the frequency domain by doubling the number of frequency components for each row, padding with zeros.
3. Phase shift alternate rows to shift them in space (multiply by $e^{-\Delta x*\omega}$)
4. Perform 1D FFT of each new column

The result is "correct" except for the fact that I've now oversampled the data by a factor of two. Is there a better way to use existing FFT codes like FFTW to do this without oversampling the data? I thought about going along two diagonals instead, but since they aren't orthogonal, their transforms wouldn't be, either.

Is there a way to turn the real-valued hex grid into a complex-valued rectangular grid of half the resolution, taking advantage of the midpoint properties of the alternating rows?

Answer 1

You should look at how to compute a Fourier series on an arbitrarily lattice. Your data grid needs to be skew-shifted slightly and zero padded so that your data grid corresponds to the non-orthogonal lattice vectors of a triangular lattice. An ordinary 2D FFT on this grid of data produces the Fourier series coefficients corresponding to the data, where each term in the series corresponds to a reciprocal lattice vector.