Fourier curves

Inspired by Cliff Pickovers tweet and powered by my fascination about the Fourier transform, I took the time to derive and implement the Fourier series of a two dimensional piecewise linear parametric curve.

By clicking on the empty canvas you can design your custom shape. If you close the path, the Fourier series will be animated similarly to the video mentioned above. Have fun!

Derivation

The following derivation shows a way to obtain the equations of the Fourier series of a two dimensional piecewise linear parametric curve. Please be aware, that this is certainly not the most efficient way to derive it.

We will treat the \(x\) and \(y\) component of the function separately. Therefore, we calculate the Fourier series for both components separately.

Fourier series

The complex Fourier series is defined as

$$y(t) = \sum \limits_{-\infty}^{\infty} \hat{y}_k e^{ik\omega t}$$

with

$$\hat{y}_k = \frac{1}{T} \int\limits_0^T y(t) e^{-ik\omega t} \,dt .$$

Our component functions \(y(t)\) are piecewise linear and can be defined as

$$y(t) = y_{i} + (t - T_i)\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i} \,\text{ , }\, T_i \leq t < T_{i+1}$$

Let’s calculate the Fourier coefficients. We start with \(k=0\):

$$\hat{y}_0 = \frac{1}{T} \sum_{i=0}^{N-1} \int\limits_{T_i}^{T_{i+1}} \left(y_{i} + (t - T_i)\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) e^{-i0\omega t} \,dt$$ $$\hat{y}_0 = \frac{1}{T} \sum_{i=0}^{N-1} \int\limits_{T_i}^{T_{i+1}} \left(y_{i} + (t - T_i)\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \,dt$$ $$\hat{y}_0 = \frac{1}{T} \sum_{i=0}^{N-1} y_{i}\int\limits_{T_i}^{T_{i+1}} 1 \,dt + \frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\int\limits_{T_i}^{T_{i+1}} t \,dt - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\int\limits_{T_i}^{T_{i+1}} 1 \,dt$$ $$\hat{y}_0 = \frac{1}{T} \sum_{i=0}^{N-1} y_{i}\left[t\right]_{T_i}^{T_{i+1}} + \frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\left[\frac{1}{2}t^2\right]_{T_i}^{T_{i+1}} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\left[t\right]_{T_i}^{T_{i+1}}$$ $$\hat{y}_0 = \frac{1}{T} \sum_{i=0}^{N-1} y_{i}\left[T_{i+1} - T_i \right] + \frac{1}{2}\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\left[T_{i+1}^2 - T_i^2\right] - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\left[T_{i+1} - T_i\right]$$ $$\hat{y}_0 = \frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \left[T_{i+1} - T_i \right] + \frac{1}{2}\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\left[T_{i+1}^2 - T_i^2\right]$$

Now we look at the general case \(k>0\):

$$\hat{y}_k = \frac{1}{T} \sum_{i=0}^{N-1} \int\limits_{T_i}^{T_{i+1}} \left(y_{i} + (t - T_i)\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) e^{-ik\omega t} \,dt$$ $$\hat{y}_k = \frac{1}{T} \sum_{i=0}^{N-1} \int\limits_{T_i}^{T_{i+1}} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) e^{-ik\omega t} \,dt + \frac{1}{T} \sum_{i=0}^{N-1} \int\limits_{T_i}^{T_{i+1}} t\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}e^{-ik\omega t} \,dt$$ $$\hat{y}_k = \frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right)\int\limits_{T_i}^{T_{i+1}} e^{-ik\omega t} \,dt + \frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i} \int\limits_{T_i}^{T_{i+1}} te^{-ik\omega t} \,dt$$

The first term simplifies to

$$\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \int\limits_{T_i}^{T_{i+1}} e^{-ik\omega t} \,dt$$ $$\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \left[ \frac{1}{-ik\omega} e^{-ik\omega t} \right]_{T_i}^{T_{i+1}}$$ $$\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \frac{i}{k\omega}\left[ e^{-ik\omega T_{i+1}} - e^{-ik\omega T_i} \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \frac{i}{k\omega}\left[ \cos(-k\omega T_{i+1}) + i\sin(-k\omega T_{i+1}) - \cos(-k\omega T_{i}) - i\sin(-k\omega T_{i}) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \frac{1}{k\omega}\left[ i\cos(-k\omega T_{i+1}) -\sin(-k\omega T_{i+1}) - i\cos(-k\omega T_{i}) +\sin(-k\omega T_{i}) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \frac{1}{k\omega}\left[ i\cos(k\omega T_{i+1}) +\sin(k\omega T_{i+1}) - i\cos(k\omega T_{i}) -\sin(k\omega T_{i}) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \frac{1}{k\omega}\left[\sin(k\omega T_{i+1}) -\sin(k\omega T_{i}) + i\left[\cos(k\omega T_{i+1}) - \cos(k\omega T_{i})\right] \right]$$

We now look at the second term

$$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i} \int\limits_{T_i}^{T_{i+1}} te^{-ik\omega t} \,dt .$$

Fortunately, we know the identity

$$\int\limits_0^1 x^n e^{-ax}\,dx = \frac{n!}{a^{n+1}}\left[1 - e^{-a}\sum_{i=0}^n \frac{a^i}{i!}\right].$$

We can use it, by applying the coordinate transformation to our integral

$$t = T_i + (T_{i+1} - T_i)x$$ $$dt = (T_{i+1} - T_i)\,dx$$ $$x = \frac{t - T_i}{T_{i+1} - T_i}$$

We obtain

$$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i} \int\limits_{0}^{1} (T_i + (T_{i+1} - T_i)x)e^{-ik\omega (T_i + (T_{i+1} - T_i)x)}(T_{i+1} - T_i) \,dx$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}(T_{i+1} - T_i) e^{-ik\omega T_i} \left[T_i\int\limits_{0}^{1} e^{-ik\omega (T_{i+1} - T_i)x} \,dx + (T_{i+1} - T_i)\int\limits_{0}^{1} xe^{-ik\omega (T_{i+1} - T_i)x} \,dx \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}(y_{i+1}-y_{i}) e^{-ik\omega T_i} \left[T_i\int\limits_{0}^{1} e^{-ik\omega (T_{i+1} - T_i)x} \,dx + (T_{i+1} - T_i)\int\limits_{0}^{1} xe^{-ik\omega (T_{i+1} - T_i)x} \,dx \right]$$

Now we have to integrals of the identity above. The first integral is

$$\int\limits_{0}^{1} e^{-ik\omega (T_{i+1} - T_i)x} \,dx$$

with \(a = ik\omega (T_{i+1} - T_i) \) and \(n=0\). It follows

$$\int\limits_0^1 x^n e^{-ax}\,dx = \frac{0!}{a^{0+1}}\left[1 - e^{-a}\sum_{i=0}^0 \frac{a^i}{i!}\right] = \frac{1}{a}\left[1 - e^{-a}\right] = \frac{1}{ik\omega (T_{i+1} - T_i)}\left[1 - e^{-ik\omega (T_{i+1} - T_i)}\right]$$

The second integral is

$$\int\limits_{0}^{1} xe^{-ik\omega (T_{i+1} - T_i)x} \,dx$$

with \(a = ik\omega (T_{i+1} - T_i) \) and \(n=1\).

It follows

$$\int\limits_0^1 x^n e^{-ax}\,dx = \frac{1!}{a^{1+1}}\left[1 - e^{-a}\sum_{i=0}^1 \frac{a^i}{i!}\right] = \frac{1}{a^2}\left[1 - e^{-a}(1 + a)\right] = \frac{1}{-k^2\omega^2 (T_{i+1} - T_i)^2}\left[1 - e^{-ik\omega (T_{i+1} - T_i)}(1 + ik\omega (T_{i+1} - T_i))\right]$$

We insert the results back into our equation

$$\frac{1}{T} \sum_{i=0}^{N-1}(y_{i+1}-y_{i}) e^{-ik\omega T_i} \left[T_i\frac{1}{ik\omega (T_{i+1} - T_i)}\left[1 - e^{-ik\omega (T_{i+1} - T_i)}\right] + (T_{i+1} - T_i)\frac{1}{-k^2\omega^2 (T_{i+1} - T_i)^2}\left[1 - e^{-ik\omega (T_{i+1} - T_i)}(1 + ik\omega (T_{i+1} - T_i))\right] \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}(y_{i+1}-y_{i}) e^{-ik\omega T_i} \left[-\frac{i T_i}{k\omega (T_{i+1} - T_i)}\left[1 - e^{-ik\omega (T_{i+1} - T_i)}\right] -\frac{1}{k^2\omega^2 (T_{i+1} - T_i)}\left[1 - e^{-ik\omega (T_{i+1} - T_i)}(1 + ik\omega (T_{i+1} - T_i))\right] \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} e^{-ik\omega T_i} \left[-i T_i\left[1 - e^{-ik\omega (T_{i+1} - T_i)}\right] - \frac{1}{k\omega }\left[1 - e^{-ik\omega (T_{i+1} - T_i)}(1 + ik\omega (T_{i+1} - T_i))\right] \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[-i T_i e^{-ik\omega T_i} +i T_ie^{-ik\omega T_i}e^{-ik\omega (T_{i+1} - T_i)} - \frac{1}{k\omega }e^{-ik\omega T_i} + \frac{1}{k\omega }e^{-ik\omega T_i}e^{-ik\omega (T_{i+1} - T_i)}(1 + ik\omega (T_{i+1} - T_i)) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[-i T_i e^{-ik\omega T_i} +i T_ie^{-ik\omega T_{i+1}} - \frac{1}{k\omega }e^{-ik\omega T_i} + \frac{1}{k\omega }e^{-ik\omega T_{i+1}}(1 + ik\omega (T_{i+1} - T_i)) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[-i T_i e^{-ik\omega T_i} +i T_ie^{-ik\omega T_{i+1}} - \frac{1}{k\omega }e^{-ik\omega T_i} + \frac{1}{k\omega }e^{-ik\omega T_{i+1}}+ \frac{1}{k\omega }e^{-ik\omega T_{i+1}}ik\omega (T_{i+1} - T_i) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[-i T_i e^{-ik\omega T_i} +i T_ie^{-ik\omega T_{i+1}} - \frac{1}{k\omega }e^{-ik\omega T_i} + \frac{1}{k\omega }e^{-ik\omega T_{i+1}}+ iT_{i+1}e^{-ik\omega T_{i+1}} - iT_ie^{-ik\omega T_{i+1}} \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[-i T_i e^{-ik\omega T_i} - \frac{1}{k\omega }e^{-ik\omega T_i} + \frac{1}{k\omega }e^{-ik\omega T_{i+1}}+ iT_{i+1}e^{-ik\omega T_{i+1}} \right]$$

We replace the exponential terms with \(\sin\) and \(\cos\)

$$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[ -i T_i (\cos(-k\omega T_{i}) + i\sin(-k\omega T_{i})) - \frac{1}{k\omega }(\cos(-k\omega T_{i}) + i\sin(-k\omega T_{i})) + \frac{1}{k\omega }(\cos(-k\omega T_{i+1}) + i\sin(-k\omega T_{i+1})) + iT_{i+1}(\cos(-k\omega T_{i+1}) + i\sin(-k\omega T_{i+1})) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[ -i T_i\cos(-k\omega T_{i}) + T_i\sin(-k\omega T_{i}) - \frac{1}{k\omega }\cos(-k\omega T_{i}) -i\frac{1}{k\omega }\sin(-k\omega T_{i}) + \frac{1}{k\omega }\cos(-k\omega T_{i+1}) + i\frac{1}{k\omega }\sin(-k\omega T_{i+1}) + iT_{i+1}\cos(-k\omega T_{i+1}) - T_{i+1}\sin(-k\omega T_{i+1}) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[ -i T_i\cos(k\omega T_{i}) - T_i\sin(k\omega T_{i}) - \frac{1}{k\omega }\cos(k\omega T_{i}) +i\frac{1}{k\omega }\sin(k\omega T_{i}) + \frac{1}{k\omega }\cos(k\omega T_{i+1}) -i\frac{1}{k\omega }\sin(k\omega T_{i+1}) + iT_{i+1}\cos(k\omega T_{i+1}) + T_{i+1}\sin(k\omega T_{i+1}) \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[ - T_i\sin(k\omega T_{i}) - \frac{1}{k\omega }\cos(k\omega T_{i}) + \frac{1}{k\omega }\cos(k\omega T_{i+1}) + T_{i+1}\sin(k\omega T_{i+1}) +i\left[-T_i\cos(k\omega T_{i}) +\frac{1}{k\omega }\sin(k\omega T_{i}) -\frac{1}{k\omega }\sin(k\omega T_{i+1}) + T_{i+1}\cos(k\omega T_{i+1}) \right] \right]$$

We now look again at our first term from above and separate it $\frac{1}{T} \sum_{i=0}^{N-1} \left(y_{i} - T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i}\right) \frac{1}{k\omega}\left[\sin(k\omega T_{i+1}) -\sin(k\omega T_{i}) + i\left[\cos(k\omega T_{i+1}) - \cos(k\omega T_{i})\right] \right]$

into

$$-\frac{1}{T} \sum_{i=0}^{N-1} T_i\frac{y_{i+1}-y_{i}}{T_{i+1} - T_i} \frac{1}{k\omega}\left[\sin(k\omega T_{i+1}) -\sin(k\omega T_{i}) + i\left[\cos(k\omega T_{i+1}) - \cos(k\omega T_{i})\right] \right]$$

and

$$\frac{1}{T} \sum_{i=0}^{N-1} y_{i}\frac{1}{k\omega}\left[\sin(k\omega T_{i+1}) -\sin(k\omega T_{i}) + i\left[\cos(k\omega T_{i+1}) - \cos(k\omega T_{i})\right] \right] .$$

We combine the result of the second term with first equation of the separation

$$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[ - T_i\sin(k\omega T_{i}) - \frac{1}{k\omega }\cos(k\omega T_{i}) + \frac{1}{k\omega }\cos(k\omega T_{i+1}) + T_{i+1}\sin(k\omega T_{i+1}) +i\left[-T_i\cos(k\omega T_{i}) +\frac{1}{k\omega }\sin(k\omega T_{i}) -\frac{1}{k\omega }\sin(k\omega T_{i+1}) + T_{i+1}\cos(k\omega T_{i+1}) \right] -T_i\sin(k\omega T_{i+1}) +T_i\sin(k\omega T_{i}) + i\left[-T_i\cos(k\omega T_{i+1}) +T_i \cos(k\omega T_{i})\right] \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[ \underbrace{- T_i\sin(k\omega T_{i}) +T_i\sin(k\omega T_{i}) }_{0} - \frac{1}{k\omega }\cos(k\omega T_{i}) + \frac{1}{k\omega }\cos(k\omega T_{i+1}) + (T_{i+1}-T_i)\sin(k\omega T_{i+1}) +i\left[\underbrace{-T_i\cos(k\omega T_{i}) +T_i \cos(k\omega T_{i}) }_{0} +\frac{1}{k\omega }\sin(k\omega T_{i}) -\frac{1}{k\omega }\sin(k\omega T_{i+1}) + (T_{i+1}-T_i)\cos(k\omega T_{i+1}) \right] \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{y_{i+1}-y_{i}}{k\omega (T_{i+1} - T_i)} \left[ - \frac{1}{k\omega }\cos(k\omega T_{i}) + \frac{1}{k\omega }\cos(k\omega T_{i+1}) + (T_{i+1}-T_i)\sin(k\omega T_{i+1}) +i\left[ \frac{1}{k\omega }\sin(k\omega T_{i}) -\frac{1}{k\omega }\sin(k\omega T_{i+1}) + (T_{i+1}-T_i)\cos(k\omega T_{i+1}) \right] \right]$$

Now we incorporate the second part of the separation.

With the helping variable

$$a = \frac{y_{i+1}-y_{i}}{(T_{i+1} - T_i)}$$

follows

$$\frac{1}{T} \sum_{i=0}^{N-1}\frac{1}{k\omega} \left[ -y_i\sin(k\omega T_{i}) +(y_i+a(T_{i+1}-T_i))\sin(k\omega T_{i+1}) - \frac{a}{k\omega }\cos(k\omega T_{i}) + \frac{a}{k\omega }\cos(k\omega T_{i+1}) +i\left[ - y_i\cos(k\omega T_{i}) +(y_i+a(T_{i+1}-T_i))\cos(k\omega T_{i+1}) +\frac{a}{k\omega }\sin(k\omega T_{i}) -\frac{a}{k\omega }\sin(k\omega T_{i+1}) \right] \right]$$ $$\frac{1}{T} \sum_{i=0}^{N-1}\frac{1}{k\omega} \left[ -y_i\sin(k\omega T_{i}) +y_{i+1}\sin(k\omega T_{i+1}) - \frac{a}{k\omega }\cos(k\omega T_{i}) + \frac{a}{k\omega }\cos(k\omega T_{i+1}) +i\left[ - y_i\cos(k\omega T_{i}) +y_{i+1}\cos(k\omega T_{i+1}) +\frac{a}{k\omega }\sin(k\omega T_{i}) -\frac{a}{k\omega }\sin(k\omega T_{i+1}) \right] \right]$$

The resulting formula is

$$\hat{y}_k = \frac{1}{T} \sum_{i=0}^{N-1}\frac{1}{k\omega} \left[ -y_i\sin(k\omega T_{i}) +y_{i+1}\sin(k\omega T_{i+1}) - \frac{a}{k\omega }\cos(k\omega T_{i}) + \frac{a}{k\omega }\cos(k\omega T_{i+1}) +i\left[ - y_i\cos(k\omega T_{i}) +y_{i+1}\cos(k\omega T_{i+1}) +\frac{a}{k\omega }\sin(k\omega T_{i}) -\frac{a}{k\omega }\sin(k\omega T_{i+1}) \right] \right]$$

We note that we can \(\frac{1}{T}\frac{1}{k\omega} = \frac{1}{2\pi k}\) and finally obtain

$$\hat{y}_k = \frac{1}{2\pi k} \sum_{i=0}^{N-1} \left[ -y_i\sin(k\omega T_{i}) +y_{i+1}\sin(k\omega T_{i+1}) - \frac{a}{k\omega }\cos(k\omega T_{i}) + \frac{a}{k\omega }\cos(k\omega T_{i+1}) +i\left[ - y_i\cos(k\omega T_{i}) +y_{i+1}\cos(k\omega T_{i+1}) +\frac{a}{k\omega }\sin(k\omega T_{i}) -\frac{a}{k\omega }\sin(k\omega T_{i+1}) \right] \right]$$

In the final step, we can express our result as

$$y(t) = \sum_{k=0}^N A_k \sin(k\omega t + \varphi_k)$$

with coefficients

$$A_k = \begin{cases} \hat{y}_0 & k = 0 \\ 2 |\hat{y}_k| & k>0 \end{cases}$$

and

$$\varphi_l = \begin{cases} \frac{\pi}{2} & k = 0 \\ \text{atan2}( \Re(\hat{y}_k), - \Im(\hat{y}_k)) & k>0 \end{cases}.$$