For functions of an interval (in the case of polynomial spline segments, usually {x(t), y(t)} for 0 ≤ t ≤ 1), what you want for an analog of a Fourier transform is to use Chebyshev polynomials. You can use a discrete cosine transform to convert between values at n points appropriately spaced (w/r/t the parameter) along the curve to and from coefficients of the Chebyshev basis polynomials of the form f(x) = cos(n arccos x), in just the same way you would use a discrete Fourier transform to convert back and forth between equispaced points on a periodic interval [0, 2π) and coefficients of trigonometric polynomials. All the same FFT speedup tricks apply, so you only need O(n log n) floating point operations for a polynomial of degree n.

See http://www.chebfun.org/ATAP/atap-first6chapters.pdf

I feel like there's a pun here.