Hexagonal fast Fourier transform with rectangular output

摘要

Hexagonal sampling is the most efficient sampling pattern for a two-dimensional circularly bandlimited function. A separable fast discrete Fourier transform (DFT) algorithm for hexagonally sampled data that directly computes output points on a rectangular lattice is reported. No interpolation is required. The algorithm has computational complexity comparable to that of standard two-dimensional fast Fourier transforms.