# Coding Challenge #130.1: Drawing with Fourier Transform and Epicycles

(bell dings) – Hello, welcome to a coding challenge. I actually just finished

this coding challenge, and I’m coming back to

re-record a little intro to it. And what I made in this coding challenge is a drawing machine. Maybe let’s call this a Fourier

transform drawing machine. There’s a few more things

we want to do with it. There’s going to be some followup videos. But this very, very long

video, if you can stand to watch it, has, as part

of it, at the end, this. This is the end result. I am using an algorithm

called Fourier Transform to take an arbitrary signal,

in this case, a sequence of X’s and a sequence of Y’s, the

path of the Coding Train logo, thank you to Tom Fevrier. I will link to Tom Fevrier’s

Twitter, who provided the path for this

particular logo, to trace the path of the logo through

this sort of sequence of rotating circles, sometimes

referred to as epicycles. Okay, so what’s going on here? So, first thing I should

mention is this is a continuation of my coding

challenge Fourier Series. And so, what I did in that

particular coding challenge, which was inspired by a Smarter

Everyday video on the same topic, was create the Fourier

series for a square wave. I don’t know why I just had to write that. But in this video, I’m going

to do something different, which is I’m going to use the

Fourier transform algorithm. And these are different concepts. I somewhat conflated these

in my previous video. The idea of the Fourier transform. Now, where I know this

algorithm from, where I learned about this algorithm first in

like, learning about coding and creative coding and new

media and sound and video is with the terminology FFT, and actually, if you go into the p5

sound library, you’ll see there is a class or

function called p5.FFT. I don’t remember exactly what it’s called, but something like that. The F here stands for fast,

Fast Fourier Transform. The algorithm I’m going to implement, by the way, is discrete Fourier transform. Why is this FFT thing,

where is it typically used? Well, it’s typically used in,

it’s in signal processing, but a familiar place

where you might find that is in audio signal processing. So let’s say you have

some arbitrary sound wave that maybe looks like

this, and it has a really high-pitched, awful,

screeching sound in it. How would you filter that out? Well, if you could take

this sound wave pattern and break it into a bunch

of smaller sound waves, a bunch of sound waves that have varying amplitudes and frequencies,

then you could take, you could sort of remove the one that has the high-pitched sound in it and then add them all back together

and get a new sound wave. So the idea of a Fourier

transform, I think I said this in the Fourier Series, but

it’s unsmoothie-ing a smoothie. If we could take a smoothie

that’s made with blueberry, mango, and strawberries,

and like, separate it out and then put it back together

without the strawberries, this is essentially what

happens in signal processing. But in this video, what I’m going to do is instead of the signal being

an audio, it’s going to be a series of X values or

a series of Y values, and eventually, there

actually a way to do that with the X, Y values

together that I will get to. So, I am not going to go

too deep into the math in this particular video. I’m not going to derive the

Fourier Transform algorithm. I’m not going to talk about

Fast Fourier Transform. I’m just going to use a very

crude, discrete Fourier Transform implementation just to

get the thing working. If you want to know more

about the math, though, let me reference a few

really key references. The 3blue1brown video, But

what is the Fourier Transform? will give you an infinitely

better understanding of what the Fourier Transform algorithm is and what it does, and even how

it works, way better than my trying to ramble through

that over on the whiteboard. I would also highly recommend

this GoldPlatedGoof video, Fourier Analysis for the

Rest of Us, which goes through the details of the

math in a much deeper way, and then there’s this wonderful

video from Mathologer, Epicycles, complex Fourier

series and Homer Simpson’s orbit, which will give you the

full story of everything that I’m trying to do. But hopefully, what’s useful

to you that’s different in my video than from these

is I’m just going to sit here and attempt to code the thing. And I know that it’s going to

work, because I already did it, and here is the result. So enjoy. This is a very long video. I hope that if you watch

it, you get the code, you make your own variation of

it, please share it with me. You can go to thecodingtrain.com,

to the particular coding challenge page, and

then there’s instructions on how to submit a user

community variation thingy there. Okay, goodbye, enjoy, or not, or whatever. I am ready to start coding, finally. Now, this is where I left off

before in my Fourier Series coding challenge, and

the difference now is what I want to do is be able

to have an arbitrary signal and then compute what

all of these amplitudes and frequencies and phases should be. So, the way that I’m going to do that is, so let’s think about this. This is really a bunch of Y

values that I’m calculating. So let’s make an array

called something like Y, and this is going to be the

signal, this is my signal. This could be audio, it

could be Y positions, any arbitrary digital

signal/array of numbers. Then what I want to do is I want to have like, the Fourier transform

of that particular signal. So I want to say, fourierY

=fourierTransform, or maybe like dft, discrete Fourier

Transform, of the Y value. So this is the idea. The first thing that I

need to do is compute the discrete Fourier transform

of an arbitrary signal. Now I need some kind of signal. So I think what I’m going to absurdly do is hardcode the signal. Let’s actually make it the square wave, and then we’ll know if it kind of worked. So what is the square wave? Square wave would be

something like 100, 100, 100, – 100, -100, -100, and then

like, do that a few times. So this is going to be

my arbitrary signal, which I’m just hardcoding the square wave. And we’ll do some interesting

things that we might, maybe I’ll try a Perlin noise signal or just a sine wave signal. We’ll try different things, random numbers, and see what that does. So then, this actual code here

can largely stay the same, ’cause in theory, the difference is now, instead of following the

specific Fourier Series for the square wave, I just need to take the results of my discrete

Fourier transform. So this would be a loop that’s going to go through the length of

that transform, how many different wave patterns are

there that I’m adding together, and then this ultimately, I’m

going to have to figure out. So let’s comment this out right now, and there’s a little bit

of an issue where I have this x and y as like,

local variables here. But let’s, I think this will be okay. So let’s refresh this,

and DFT is not fine. Okay, step one, let’s write the discrete Fourier Transform algorithm. So, I’m going to start by

making a function called dft. It’s going to have some

array of values, and now, I need to, at the end, I

need to return something. (laughs) The idea is that I will return the discrete Fourier

transform of those values. So, a couple things. One is I highly recommend,

if you want to pause this video right now and

read this particular article on the Algorithm Archive by James Schloss or the

LeIOS YouTube channel. This is a really nice article

about Fourier transforms and the discrete Fourier

Transform algorithm, and this particular algorithm for FFT. But what I’m going to do

is I’m just going to follow exactly what’s here on the Wikipedia page. So, my signal is x sub n, lowercase xn. So what I need to do is basically, and the transform is capital X sub k. So I need to write a

function that computes this exact equation and

returns it as an array, and this is exactly what I’m going to do. This is exciting. Now, one thing I should mention is that in order to work with Fourier transforms, I need to understand something

called a complex number. Now, if I recall correctly,

the last time a complex number came up on this YouTube

channel was probably in my Mandelbrot set coding

challenge, where I visualized the famous Mandelbrot fractal,

and I referenced something called an imaginary number,

and I was way too informal and loosey goosey and jokey about how I talked about imaginary numbers being this pretend thing

that doesn’t exist, which is absolutely incorrect. The reason why the term imaginary is used is because there is no

real number solution to the square root of negative

one, but the square root of negative one is referred

to in mathematics as i. I is a complex number. A complex number is a

number with both a real, a, plus an imaginary component. So it’s two real values, a real value and another real value

kind of multiplied by i, the square root of negative one. So, this is the idea of a

complex number, and by the way, another way for me to

refer to a complex number is by its position on the complex plane. So if this were the real axis, and this were the imaginary

axis, this would be a, and this would be b, and this

is a vector representation, whoa, of this particular complex number. So, why do I bring this up? The reason why I bring this up

is that the Fourier Transform algorithm, even if I start

with an array of real numbers, single numbers, I’m going to

apply the Fourier Transform and get out a complex number. What I’m going to return

from that function is both a’s and b’s, otherwise

known as the real component, which is often written in code as re, and the imaginary component,

which is often written as im. So this is one bit that I

really need to understand before working with this formula. So now is this moment, this

moment that happens to you in life, where you see

one of these formulas on a Wikipedia page or in a math textbook, and you’re a creative coder making some kind of visualization thing,

and you just want to stop. But together, you and me,

we’re not going to stop. We’re going to figure out

how to translate all this notation and symbols and

stuff into JavaScript code. Now, again, it’ll be super

interesting to go down the rabbit hole of deriving all these

formulas and the background for how Fourier transform works,

but I’m not going to do that. If you look in the video description, there are several excellent

videos and resources linked to that will give

you that background. But I do want to mention one

thing, which is quite important, which is that this particular

formula in the top here for the discrete Fourier

transform uses this symbol e, Euler’s number, or the

base of natural law. This is a very famous number

in mathematics, much like pi, but there’s also a very well known formula called Euler’s formula,

which looks like this: e to the i, which, complex

number i, x, equals cosine of x plus i times sine of x. Really interesting,

kind of looks like polar to Cartesian coordinate transformation. All this stuff is interrelated, right? But so, that is where,

if I come back to here, this is where we get the

second line here, using Euler’s formula from the

particular formula that’s up top. But this is the one that

I want to implement, and I have written the

formula out right over here so we can unpack it a little bit. What are the components

we need to understand? Now, really, if this were a math lesson about Fourier Transform,

we wouldn’t be using summation; we would be using integration. But because we’re working on a computer, and I need to write a loop,

and I don’t have infinity as a tool that I can just use, I need to, instead of doing integration,

do summation, and that’s why also this is called

discrete Fourier transform, ’cause I’m doing it over this

sort of like, discrete space. Okay, so this means summation. So this should give you

clue that I can just do like a for loop, going from

zero all the way up to n. And by the way, n is

going to be the length, the number of values I have in my signal, so the length of that original array. Oh, and then the other thing

that’s really important is that basically what I

get to do is separate out. This is the real component, and this is the imaginary component. So even though this is all

written as one formula, I’m going to sum up

all the real components and all the imaginary components together. And by the way, as Simon, who

has been watching this live, pointed out to me, there

are only complex numbers. The term imaginary, it’s

really too bad that it’s called imaginary, ’cause it’s very misleading. But a real number is just a complex number with the imaginary component as zero. Okay, so, I should be able to start writing the

code for this now, right? This is my signal. It’s a little confusing

that this is called X, ’cause I called it Y, but this

is just the values, the vals. This n is vals.length

in my code, and then, k, we’re going to have to work out what k is. I know what cosine is, two

pi, and all these things. So we’re going to work out what k is. Oh, boy, I’m so silly. What is k? This should actually, this is, this is, I completely forgot to

write what is quite possibly the most important part of this formula (instructor laughs)

over here, which is capital X, big X, sub k equals. So, this is what I’m trying to calculate. I’m trying to create

an array of k elements. At each element k, I’m going to sum up n from zero to the end. So there’s a little bit of

a nested loop going on here. I want to loop through

every k, which is going from zero all the way up

to n, and then also sum up. So k is going to stay constant

within each one of these, and k is actually really the

frequency, we’ll see that, the frequency of the particular

wave pattern in that slot. Okay, all right, so let me

write the code for this. The first thing that I want to

do is create an empty array. This is where I’m going to

store all of the results. Then I need to write a loop,

which is let k=0; k

it was more fun to watch the live series 😀

Looks like a 3D printer 😂

Although this video's sophistication only adds to its glory, I miss the time when your videos used to be based on p5.js and were so simple that I would start coding straight away!

Don't joke about imaginary numbers Daniel! This is VERY serious business.

I'm watching Daniel's channel since about 50k subs, every time he creates some amazing project, but this is maybe the most amazing thing I've ever seen here 😀 I heard about FT long time ago, but I've never been interested until now. Great job 😉

whattttt. How did u do that…. my mind is blown

I'm bit confused rn, isn't still a fourier series?

This is epic! How can you make it like that, but with only one set of circles? (3:28)

If you had a link or something I have to search, that's more than enough.

Jesus this is insane! I remember having to draw a image with piecewise functions in 10th grade and thought that was impressive.

really really amazing!!

Every time you say "DFT", in my mind I keep adding "BA". ._.

Cool one!!!!!!

Im so glad that you uploud new videos! There was a little break that made me worry

video ends at 5:05

Sir,i am one of your subscriber please its my humble request to you that please make a video on how we give a birthday gift though we are programmer my friend birthday is on 26th of jan

FFT if I remember correctly can be used to simulate sea waves in videogame graphics very efficiently

Also, as a way to teach complex numbers, have you ever considered making a "complex number library"? You can then refer to it when you do videos like this that build on top of it.

I am giving you this message on your recent video so you notice this please sir its my humble request

i love how well you can explain topics, especially complex topics such as Fourier Transform! you’re definitely able to explain them in a really simple, but effective manner. great video as always!

You are the best coding teacher ever!

Keep up the math related codes.

I would love to learn how the Coding Train logo path was generated.

Sweet. I was only able to see a part of the stream 🙂

Awesome, like always!

Brilliant work! One of your best ones.. Thank you 🙂

You should do a video on the trapped knight sequence by numberphile. I think this would fit in a coding challenge. ( https://youtu.be/RGQe8waGJ4w )

Impressive, but can you draw One Punch Man?

Sad i missed this stream!

Hello, please can you do Einstein gravitational lensing ?

This is spectacular!

3:06 I’m just glad you don’t put bananas in your smoothies.

Thanks for making this!

Hello Trainbow

4:03. infinitely better, that hit the mathematician in me so hard

"Lets make an array, called "y" and this is signals"

how about naming it "signals"?

i squared is -1, your definiton is flawed

How does it still draw the same thing after sorting? I can't wrap my head around that.

Oh yeah yeah

Can u do the cristian ilies vasile visualization of pi it's so awesome !!

Hello Daniel,

I'm now following your tutorial videos about Java, after i saw you making cool things i wanted to make my own sort of minigame. The thing is i want the bal to bounce back after that the ball hits the pedal, but the problem is i don't know how. Here is the thing i tried following the whole script.

ellipse(x,y,24,24);

if ((x==mouseX) && (y==300));{

x+=9;

}

rect(mouseX, 300, 94, 24);

float x=width/2;

float y=height/2;

float kleur1;

float kleur2;

float kleur3;

int xspeed = 2;

int yspeed = 2;

boolean xgaan = false;

boolean ygaan = false;

boolean xwaar = false;

boolean ywaar = false;

void setup()

{

size (640,360,P2D);

background(kleur1,kleur2,kleur3);

}

void draw() {

background(kleur1,kleur2,kleur3);

fill(0,255,0);

ellipse(x,y,24,24);

// if ((x==mouseX) && (y==300));{

//x+=9;

//}

rect(mouseX, 300, 94, 24);

kleur1 += 0.8;

kleur2 += -0.8;

kleur3 += 3;

x += xspeed;

if (x > width){

xspeed *= -1;

xwaar= true;

}

if (x < 0){

xspeed *= -1;

xwaar =false;

}

if(mousePressed == true) {

xspeed = 0;

}

if(mousePressed==false){

if(xwaar == false){

xspeed=2;

}

}

if(xwaar == true){

xspeed=-2;

}

y += yspeed;

if (y > height){

yspeed *= -1;

ywaar= true;

}

if (y < 0){

yspeed *= -1;

ywaar =false;

}

if(mousePressed == true) {

yspeed = 0;

}

if(mousePressed==false){

if(ywaar == false){

yspeed=2;

}

if(ywaar == true){

yspeed=-2;

}

}

}

What's your theme color please? I asked this question during the live (you were so great!) and some people answered Dracula but it does not seem to be this and I'd really like to have your theme color

Great. Thx .

Tip: Don't use "const" when you know you don't want to change a variable – just always use "const" except when it's

reallynot possible. You'll write different code that way because automatically you try to avoid "let" by using functions like .map() and stuffI made it! https://github.com/CobaltXII/boiler/blob/master/experimental/fourier_transform_2.cpp

Can you please make a particle cellular automata like this : http://www.ventrella.com/Clusters/

I tried making this and when I finished, wanted to try with different paths, but I cannot find any online. Do you know how can I find some?

Try shrödingers wave function visulation with p5 js

no oh yeah yeah?

Yo that's awesome

😨 Amazing

This video makes me very happy. I have a smile that fills my face.

Muchas gracias!

The square root of -1 doesn't exist, i is defined as i^2 = -1 what is not exactly the same…

So… he basically reinvented the Gcode?

FFT must means FULL of FRUSTRATING TRANSFORMATION. i had to watch more videos about fourier transform to catch up your 1 hour video. and more time to ponder. but only got glimpse of it. I only could start actual coding after i stop to try understand everything mathmatically. it was shame but when I finally reconstructed a straight line with x,y sin waves in my own code I am so satisfied. all my struggle was not in vain. thank you!

i like how this relates to alternating current

Hey Daniel! I'm a huge fan of your channel, and I always learn a lot from your videos. Although I do not do JavaScript or p5.js, by going through the algorithm step-by-step one can build and expand on the code in any modern language. More importantly, one can not only replicate the code, but also understand it! Combining math, code and graphics is so much fun! In fact, I've been interested in Fourier since ever, but the standard math has always daunting to me, a biologist without strong background in math. Your recent videos on FT are not only amusing, but also expanded the horizon of possibilities in my research. Keep up the GREAT work! Best!

how would you do this with processing, due to the fact that Java arrays are different than javascript arrays? would you use an ArrayList?

Hello, good morning. Is it possible to create more than one canvases on a single page? Like createCanvas(w,h) createCanvas(w,h) that could result two canvases. Please tell me how I can do this if it is possible.

Man i can tell you. I hate javascript and still love your channel. This is gold

This is basically Etch-a-sketch, but cooler!!

A crude attempt at reducing the number of points in the drawing (to 375 in this case) instead of skipping 7 out of 8 points which gives 625 points, while keeping most of the details of the original 5000 point drawing:

function simplifyDrawing(drawing) {

const maxHeadingDiff = 0.4;

const maxStrokeLength = 16;

let newDrawing = [];

let headingDiff = 0;

let strokeLength = 0;

let prevVec = null;

for (let i = 0; i < drawing.length -1; i++) {

let vec = createVector(drawing[i+1].x – drawing[i].x, drawing[i+1].y – drawing[i].y);

if (prevVec == null) {

newDrawing.push(drawing[0]);

} else {

headingDiff += vec.heading() – prevVec.heading();

if (abs(headingDiff) > maxHeadingDiff/8) {

strokeLength += vec.mag();

} else {

strokeLength += vec.mag()/128;

}

if (headingDiff > maxHeadingDiff || headingDiff < -maxHeadingDiff || strokeLength > maxStrokeLength) {

newDrawing.push(drawing[i+1]);

headingDiff = 0;

strokeLength = 0;

}

}

prevVec = vec;

}

if (strokeLength > 0) {

newDrawing.push(drawing[drawing.length-1]);

}

print('Simplified drawing from ' + drawing.length + ' to ' + newDrawing.length + ' points.');

return newDrawing;

}

I feel bad for the like. I've destroyed 1024 with +1.

Great video sir ji

hey i'm trying to make the one where the person draws the shape so that it keeps tracing the path but as it continues to trace it the path disapears at the start so the shape keeps being drawn without the line overlaping at all.

Great work. Only problem: it's wrong. Well sort of. It's hard to explain but:

The reason it works is that you have dt set as 2*PI/N (or an integer multiple) and k going all the way to N, so what you're doing is essentially sampling the function every period which means that actually all you're doing is reparametrizing your drawing in polar coordinates dependent on time. If you try to have a smaller (or bigger) dt you'll see that what is actually happening is that the circles are actually going round at random and just coming back to the point when you sample with your dt.

To have it work you need to have also negative frequencies (i.e. sum from -k to k), this way you'll see the actual Fourier transform (which incidentally is worse that what you have). This way you can also vary k as you please (number of circles = 2*k+1).

I have made a code based on yours which I'll be happy to provide.

Thanks and keep up the great work.

What a beautiful challenge…it's fanstastic…unbelivable to see!

23:57 didn't know Jim Carrey could code!

How i get those x and y values for my specific shape or my own draw? (Drawing Array)

So, I'm a bit late, but with this code, you can then simply concatenate the arrays of the fourier transforms, and then make a single epicycle draw the entire train, by drawing the trail of the tip !

I did it here if anyone want to try

https://github.com/GuillaumeClementPolytech/Code_Challenge_130_plus

So, I use Processing exclusively, and when I downloaded the code fro the Coding Challenge site for this lesson, I get an error that the circle () function is not found. I am using Processing 3.4 . If I use the reference page off of the SW, that does not include a circle() function reference, but if I search for Processing Circle(), I can find a page. Any idea what I an missing?

Fun additional challenge: have the epicycles draw their final position when the drawing is finished.

Dude I loved it! ❤❤

i bet u must have got best sleep after completing this challenge

Why do you have 2 functions?

Your videos are good, but for me sometimes you act way beyond acceptable stupid, meaning is that you should consider stop being dumb piece of shit garbage and change narrative in those moments. Love

You don't have to calculate the phase. It's already calculated. It's phi.

How can we take the drawing and calculate the x,y points?

yea but can you do it like 3blue1brown and make the picture from just one set of circles?

Sqrt(-1)=i is false because the real equation is i^2=-1

So basically you've created the most complicated etch-a-sketch of all time

this CNC in Computer 🙂

Why k goes from 0 to N

What would happen if it goes up to 2N

This is where 3blue1brown found his algorithm

the ultimate quesion is:

how to make a path

If you have a set of x,y coordinates why you don´t just prints it? What you see if you print that set of numbers?

I know this video is kind of old but, what program and how can I make an array of x and y cords of an image?

Tnx bro, now I understand it.

greatest and most complicated programe ever created by a Youtuber

most helpful source for people who don't understand math functions but understand js 😀

Awesome ! Really awesome !

But how did the guy to generate the logo ????

I think he has "scanned" the logo with a vertical line, then, for all points intersecting that line, he has summed up their y coordinates returning him a value, a kind of signal value.

Then he has processing that signal as any signal with an FFT giving him all the values needed for the drawing.

Isn't there a more elegant way of writing the SUM function by taking advantage of Javascript ?

I tried the something like the following but there's a little problem with passing parameters to the callback function for the real example of your video, I need help, but I tried this and it works fine :

//this one is valid for ANY sum you want to implement

const Sigma = (start, end, callback) => {

sum=0;

for (let n=start; n < end; n++)

sum += callback(n);

return sum;

};

//Then, write the callback function you want, like:

const f = (n, obj = {"x" : -5}) => {

return Math.cos(2*Math.PI*n) * obj.x;

};

//And call Sigma from the main code, passing it the f function.Well, roughly speaking of course…

X = Sigma(0, N-1, f);

How can we make path from own drawing?

ok, we dont get the fourier complex equation, let play with parametric equation instead

https://en.wikipedia.org/wiki/Parametric_equation

https://www.desmos.com/calculator

copy/paste on the left

Mr who signature: (cos t-(cos(2t)*sin(3t)),(2*sin(4t))-sin(5t)) ;Range of t: -30 0

LoveYou: ((3*sin(pi t))-3cos(.4t),(tan.7t-3cos(8t)*sin(.3t))) ; t range -2.15 2.14

Zorro: ((1.8*sin(t))-sin(12t),(cos.9t-cos(1.1t)*sin(4t))) ; -1.3 .5

B: (cos2t-(cos(2t)*sin(4t)),(3*sin(2t))-sin(5t)) ; -33 -29

A: ((1*cos(3t))-3cos(t),(sin t+sin(5t)*sin(3t))) ; -1.4 .5

S: ((1.8*sin(t))-sin(12t),(cos.9t-cos(1.1t)*sin(6t))) ; -1 0

Q: (cos.8t-(cos(.9t)*sin(4.3t)),(2*sin(2t))-sin(6t)) ; 0 2

Tree: (cos t-(cos(22t)*sin(333t)),(2*sin(3t))-sin(5t)) ; -23 0

NB:

Asin(B+Ct) ; or A*sin(B+C*t)

A = change amplitude

B = change phase (B = -π)

C =change frequency

Horizontal mirror: minus in front

oh there he goes…

17 guys from accounting department dislike imaginary numbers

How is it?, GOKU using Fourier Series https://www.youtube.com/watch?v=55y13PF0uSg&feature=share

I love this mad guy 😍

Hello! Here, I did according to your lesson)

vk.com/construct.classic?w=wall-175846527_217

Why is there a statement in the code that says "re = re / N" and "im = im / N"? Why is the average needed even if it was not obtained from the DFT equation?

– me as a noob coder

This isn't epicycles. Using the Fourier transform that works with complex numbers, this would have used actual epicycles.

Beautiful – interaction between x- and y-axes. Put a similar wiper setup on the z-axis and you can make a 3D drawing.

I did it with one epicycle

The drawing would be much nicer if you would only skip like 3 points of 4 and delete the smallest circles…