(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 < N; k++,
and then I'm going to be saying fourier[K] = something.
So, this, by the way, I mean, I could call this capital X
if I wanted to be, and maybe I will,
just to follow this notation exactly.
So this is capital X; this is lowercase x.
So let's actually, as silly as this might be,
let's change this to x so I can use
all the same notation as that formula.
So, I'm trying to calculate this.
Now, in order to do this, I need to,
for each one, go through N.
So this is where the nested loop comes in.
To calculate each element of capital X[k],
I need to sum up n going from zero to the n, okay?
And then, I'm going to start doing this formula, okay.
So, I need to sum up what?
I need to sum up both a real component
and an imaginary component.
So let's make a real component and an imaginary component.
The real component is going to go up by some amount,
and the imaginary component, ooh, I do not want to ask Siri.
Actually, Siri, please, could you help me
with this Fourier transform problem?
Just write the code for me.
So I'm going to sum up the real and imaginary components,
and then, I'm going to make some object,
which is basically just, what's that thing called
where, but I'm not going to worry about it right now,
the fancy ES6 way of making an object, if I'm doing this.
So then I'm going to make an object that has the real
and imaginary components, and I'm going to return it.
There we go.
So this is the process, whoo.
I could use, HollowBrian in the chat
is saying use a p vector.
I could certainly use a vector object,
but I'm going to write it this way.
Okay, so here we are, good, good, good, good, good.
That's my, I've got this and this.
Now I just need to add this stuff in there.
So let's do the real component first.
Now, one thing you might notice, this appears twice.
So if anything ever appears twice,
that might give you a hint to just put that in a variable.
So let's do that.
So let's say, I don't know what to call that.
I'm going to just call that something.
(instructor laughs)
Somebody give me an idea what to call it.
I'm going to say TWO-PI times k times n divided by n.
All right, so the chat's telling me to call it angle
or some angle name, but actually, phi is a good one,
'cause it's the value that's going into cosine and sine,
which is like an angle, or a Greek letter phi is often used.
So I'm going to call it phi, and then I'm going to say,
the real component equals, and I'm looking over there
'cause that's where my formula is written,
is going to say x[n] times cosine of phi.
Boy, this should look strangely
like a lot of code that I write a lot.
And then, x[n] times, and this should say cosine,
times sine of phi, but one thing you'll notice here
is that this, there is a minus here.
This minus here is not, is quite an important detail.
So, what I'm going to do is I don't know the best way
to handle this, but I could just say minus equals,
but maybe I'll, yeah, let's just say minus equals.
Let's do that, okay.
And then, this is called enhanced
object literals, thank you.
I can just say this.
So this will give me that, and there, okay.
So, (instructor laughs)
all of that explanation, wow, and here we are,
discrete Fourier transform.
All right, so thank you to the chat for asking
a couple key questions and for pointing out some errors.
For example, I forgot to actually define what n is,
which is x.length.
You know, I should probably get in the habit
of using the variable declaration const when I know it's
something that's going to stay a constant like this,
so I will attempt to use that here.
These cannot be const, because I'm adding them up together.
Now, another thing that is typically done
with discrete Fourier transform is to take the sum,
and then average its contribution over n.
So I would also say the real component equals
the real component divided by n.
The imaginary component is
the imaginary component divided by n.
So I'm going to add that in.
And then someone asked me, well, oh, but this is
another question that came in, which was
the question, oh, there's i here.
Why don't I see i in your formula, in your code?
Where is i in your code?
And so, i isn't explicitly in here,
but what I'm doing, I'm referencing i
by separating out the real and imaginary components.
So, the imaginary component is always paired with i,
and the real component is in the form a + bi.
So this is a, that's b, but I don't actually
have to put i in the equation itself.
So, let's save this.
Let's feel happy that we completed something.
I'm going to refresh, I'm going to go back to my code page.
So let's just see if that function dft does something,
it doesn't actually produce an error.
So I have the y array, which is my hardcoded square wave,
and if I call dft on y, here in the console,
we can see, I get, right, I had 12 values in my signal.
I get 12 complex numbers back,
each one with a real and an imaginary component.
So this looks good, in the sense
that there are numbers here.
I don't see an error, no red, no not a number.
So hopefully, we're in the right place.
Now, the question is, what, what, what do I do
with these real and imaginary components?
How do those things actually become circular epicycles?
For a circular epicycle, what do I need?
I need an amplitude, right.
That's basically the radius of that circle.
I need a frequency, which is how many cycles
through the circle does it rotate per unit of time,
and then I also need, this is what's called a phase.
And the phase, another way is think of it as an offset.
So where does the cycle begin?
Where does that circular wave pattern begin?
That's the phase.
So I need these three things.
So, somehow, what I need to be able to do is I need to be
able to say right here, well, the frequency is something,
the amplitude is something, and the phase is something.
And the secret to this lies in the fact that a complex
number is like a vector, and in fact, here we go.
The amplitude is the length of that vector,
and the phase, is the angle of that vector.
Well, so that's amplitude and phase, but what's frequency?
Well, guess what?
I don't know if there as a clue to this on that
Wikipedia page, but the frequency is actually just k.
Frequency, yeah, discrete frequency components.
So the whole point of doing this is to take the signal
and divide it into a bunch of discrete frequency components,
zero, one, two, three, four, et cetera.
So, here we go, frequency is k, and that's a little bit
redundant, but I might do something with sorting later,
so I'm going to need to keep track of that.
Amplitude is the square root of the real times real
plus imaginary times imaginary.
This is basically the magnitude of a vector,
the square root of each component squared.
This is Pythagorean's theorem at play.
And then the phase is that angle, which I can use the atan2,
and the y would be the imaginary?
I think it's this.
I'm going to just reference the code that I wrote before.
(instructor laughs) Yes, I got it right.
So this would be the phase.
So now, I can add frequency, amplitude, and phase here.
And I can refresh this page, I can say dft(y),
and let's take a look at any one of these,
and we can see all right, I've got an amplitude,
I've got a frequency, I've got a phase.
Whoo!
We are ready.
We are ready to start actually
now putting this into our code.
And the good news is, we have the code
for drawing these epicycles already.
I commented it out.
It was right here.
So, if, in fact, I have this fourierY array,
I have this code from before that
was drawing the results of those epicycles.
So, I can comment this all back in, but now,
it's not a specific Fourier series for the square wave;
it's whatever's come out of my Fourier transform.
And in this case, n is actually,
it's confusing that I'm using n here, but I'm actually
going to just call this frequency, is fourierY.freq,
and the radius is fourierY times amplitude,
and now, not times, is the amplitude.
So the frequency is the frequency,
the radius is the amplitude, and now I can say
multiply time times frequency plus that phase.
So, and I know I could have, I could get these things
out into a variable in like, one line,
but I'm just going to write this in here, phase.
So, all the code remains the same.
The difference is what I'm going to do.
Time is the that's moving forward, right?
It's the angle, and if the frequency is one, it takes
one unit of time for it to rotate a full rotation around.
Phase is the offset and radius is the amplitude.
So, one thing that I have to be very careful about here
is that I can't just arbitrarily have this 0.05 thing here.
What I need to do is I need to have like, the value dt.
What is the amount of time I move each frame of animation?
This would be TWO_PI being a full cycle
divided by how many frequency values I have.
So now, time goes up by this, and we should see now,
dare I say, (instructor laughs)
nothing?
(bell dings)
Oops, I have a terrible error here, ah!
I forgot to put index i here.
I've got to pull out, right, I'm getting the frequency,
amplitude, and phase of each element of the array fourierY.
Whoops, sorry about that.
There we go, all right.
So this looks kind of like maybe it's right,
but it doesn't look right at all.
Like, something's happening
that's pretty decent, but it's wrong.
So here's the one thing that's
a little bit unfortunate. (instructor laughs)
I'm off my 90 degrees here, I'm pretty sure.
So let's just add HALF_PI in here, because, and there we go.
Now, (instructor laughs)
this is actually correct!
This is sort of crazy, though, 'cause it's kind of like,
is this really, what we're doing?
The thing is I have so, I have so few values.
So it would make more sense for me to actually count,
to precompute some kind of more interesting signal.
So, let's forget about hardcoding the signal for a second,
and let's just say I'm going to have a signal with a hundred
values, and let's just make them all random numbers.
This is going to be a little bit insane, probably,
but let's pick a number between negative 100 and 100.
So you can see, look at this.
This, there it is!
This is the crazy set of epicycles
to draw these random numbers! (instructor shouts)
I could also now do Perlin noise instead,
and like, just have it increased by some arbitrary amount.
All right, so there we go.
I'm kind of doing nonsense here.
But the point is, any arbitrary signal that I have,
I can now compute the Fourier.
And you can see, by the way,
this is it cycling back to the beginning.
That's why it almost looks like this crazy heartbeat,
and there's this extra bit here of it,
like the first one not rotating at all,
just with this offset up, because the values itself
don't perfectly average a round zero.
But this is not the point.
This is not the point of what I want to do.
The point of what I want to do,
and let me just show you to be clear.
If I just made this like i, like a linear function,
you can see this, look at this.
These are all the epicycles for basically now,
I've got the triangle wave, 'cause it's going down and then
back up at the top and down repeating over and over again.
Okay, (instructor claps and laughs)
We are getting somewhere.
Okay, deep breath.
First thing is, in my excitement and exuberance over what
I've accomplished, I was calling this a triangle wave.
You know, there's kind of a triangle there.
This is a sawtooth wave,
which is what I've recreated right here.
But, I need to take a breath here
and talk about what the next step is going to be.
The idea now is what I want to do is I want
to be able to draw an arbitrary path, which,
in addition to having Y's, I want to have X's as well.
So I need to do the Fourier transform twice.
Now, ultimately, there's another way of doing this
where I do one Fourier transform on a set of complex numbers
where the real and imaginary components
are the X's and the Y's, but I'm going to stick
into this sort of like, simple place that I am right now,
and I am going to add two signals now, an X and a Y.
So I need the transform for both the X and the Y.
I'm just going to like, in a sort of silly way,
have the X's and the Y's be the same,
and then I'm going to apply the same exact
Fourier transform to both the X's and the Y's.
And now, here's the complicated part.
This loop here is visualizing the results
of the Fourier transform as a sequence
of rotating circles, epicycles.
So what I want to do though is, I think what's going to be good
is to refactor this, not later, but now.
(upbeat disco music)
♪ I will refactor this later ♪
- And put this in a function.
♪ You know I will refactor this later ♪
- Let's call it epicycle.
♪ I will refactor this later ♪
♪ You know I will refactor this later ♪
- So the idea is that maybe I would get an X and a Y.
Like, what's where it's going to start, and then,
I get the set of epicycles, and I draw them all.
So this is a generic fourier[1].
So in other words, the idea being that I could say,
and I'm going to get rid of this translate, and I'm going to say,
basically, what I want to be able to say
is like, draw, what did I call it?
Draw Fourier?
No, I called it epicycles.
Epicycles, like 100, comma, what's the size of this?
Windmill at 200, a fourierX, and the epicycles,
you know, 300, 200, fourierY.
So we should see both of these now.
Let's take a look.
Epicycles is not defined.
Oh, I don't know why I did this capital C.
That's probably unnecessary.
Okay, great.
So we can see, look.
So those are, and now, the epicycles are the same,
'cause they have the same values.
Let's give them different values.
So let's actually, let's do something kind of goofy.
Let's make it draw a circle.
So this is going to be 100 times cosine of, this is
so silly, of an angle, and that angle is map(i),
which goes from zero to 100 to zero to TWO_PI.
This is just so I can have some kind of path to work
with that's like, very recognizable,
so I know whether it's working or not,
and then Y will be the sine of that.
So we can see, okay, this looks promising, right?
Now we can see here are the epicycle calculations
for the X's and the Y's.
Now, one thing that's off, though, is that,
remember how I had to like, I kind of like, glossed
over this, but I was like, had the thing on its side?
This HALF_PI is really like the rotation
of the whole thing, of how I want to display it.
So let's make that an argument here,
and we'll call that rotation.
And so the Y's, oh, that's when I, do I want it?
Yeah, I think I can just do that
when I draw it, that's fine.
Where is this now? (instructor laughs)
The Y's should be off by HALF_PI, and the X's should not be.
And so now look at this.
Okay, so in theory now, (instructor laughs)
we're getting somewhere, don't worry.
What I want to do, let's position this over here, and then
let's position this a little bit further over in here.
And now what I want to do is over there, where that
mouse pointer is, I want to take the Y from here
and take the X from there and draw the path.
So, instead of wave, I was drawing a wave pattern,
I now want an array that is the full path.
I want to basically get the end result.
So let's have this epicycles function return,
it should return a value which is a vector.
createVector with x and y.
So whatever the end result, like the last x and y point,
the end of that epicycle sequence, and then, so I have
vx is this, that's the vector for the X's,
and vy is that, and now I want to say, path.unshift.
Okay, so I want to create a new vector.
This is like, where I want
to draw the thing, I need a vector,
which is the x component of vx and the y component of vy,
and then I want to put that in the path, and then this,
let's get rid of this line for a second.
I'm going to, instead of drawing this wave,
I'm going to iterate over the path.
I don't know if I've, this is a little bit
of a strange refactoring of what I had before,
but I think it's going to make sense to you in a second.
Let's see.
I might have to come back and explain this.
(instructor laughs) Let's put this in here.
And wave is not defined, because it is path, path.
I'm not going to worry about this right now.
Let's kick that out.
All right, it's over there.
Oh, it's in the wrong spot. (instructor laughs)
So, this is actually correct.
I just put the, now I realize, like,
(bell dings)
this is correct; I just put these in weird places.
Like, I want the one that's doing the Y over here
and the one that's doing the X over there.
I don't know why it just like intuitively
didn't put them in the right place.
So this should be 400, 50, and this should be like, 50, 200.
This has nothing to do with Fourier transforms.
It's just the weird way.
There we go. (instructor laughs)
So, I wanted to see them like this.
So now you can see, those are the Fourier transforms
for this particular circle, and let's add
a line back in now, which is basically this thing.
So I also want to draw a line from the vx.vy,
oh, so, vx.x, vx.y, to v.x, v.y.
Like, I just want to draw these two lines,
and the the same thing from the y.x and the y.y.
Wow, my naming is wildly confusing here.
So this could definitely use some refactoring, but.
There we go.
Now we can see those lines.
So this is good.
Now, I don't like the way this is spaced out,
so let's, one way to fix that would just be to make this
thing smaller, and that sort of helps me a little bit.
But this can move over.
I don't know why I put it all the way over there.
Let's move this over to 300.
Okay, this is a little bit better.
Now, let's make something more interesting here,
which is, (instructor laughs)
let's start using Perlin noise again.
So I'm going to say noise and noise,
plus some arbitrary amount, and we can see, look at this.
So you can see that this works, and let's give it,
let's make the amplitude bigger, and let's give it like,
500 values, whoops, and there's also no reason why.
This is very silly.
These should just be in one loop.
But let's give it more values, and let's just say,
you know, i divided by 50.
I'm just doing arbitrary stuff,
'cause the whole point of this is to do a drawing.
All right, but we can see how this now will take
any arbitrary signal and compute the Fourier transform
for the X's and Y's and draw that path.
(instructor claps) Now, the nice thing about this
is I'm about to almost instantaneously
do something to make this much more interesting.
I am going to go and grab the Coding Train logo path.
The whole point of this is forget about computing a path.
I want to have a known path, a drawing.
(bell dings)
I am back, and I have brought in a JavaScript file
that just has a big array of X's and Y's,
all in a variable called drawing, which is
the continuous path of the Coding Train logo.
Thank you to, I'll link to Tom Fevrier on Twitter
for sending me this particular path.
So what I'm going to do now is if I go to the code,
we've done all of this work for this moment.
(instructor laughs) Oh boy, this better work.
I'm so excited.
I'm going to go here, right, and now, I'm going to say,
I mean, this is a little bit silly,
the way I'm doing this, by drawing.length, i++.
I'm going to go through, right?
Remember, this variable, drawing, is just an array of X's
and Y's, and I'm going to make the X's drawing[i].x,
and the Y's, drawing[i].y.
Now, here's the thing.
I happen to know that the complexity of that drawing
is way more detailed than I need,
and it's going to run very, very slow.
So I'm actually going to add a variable called skip,
and I'm going to like, skip every 10, and I'm going to say
+= skip, and then I'm going to change this to push.
So I'm going to skip and only do
every five vertices of the drawing.
I'm doing this in advance, 'cause I already know,
looking at that, I don't need that many points.
So this should now give me all of the points,
all of the X's and Y's, from that particular drawing.
(instructor laughs)
(drum roll)
I'm about to go hit refresh, and hope that this works.
(instructor laughs) There it is!
(dramatic fanfare)
So there it is.
Now, this doesn't look as beautiful as it possibly could,
and there's a couple reasons for that.
Right now, one thing is, these look like these
weird alien creatures, by the way,
but it would be really nice to have the epicycles
render in order of amplitude.
So right now, they're rendering in order of frequency,
and it's like this strange machine,
almost like, drawing machine.
It would be amazing if someone could build this physically.
But what I'm going to do is sort them.
So, I'm going to say fourierX.sort, and fourierY.sort.
Now, the JavaScript sort function allows you
to pass in a callback, which is essentially a function
that tells you how to compare each element,
and I want to compare them by amplitude.
So I can actually say, any two arbitrary elements,
and I'm going to use ES6 syntax for this.
If you haven't watched my arrow syntax
or higher order array videos, this is something
that will give you background for this.
And then I can just say, I think a.amp - b.amp, right?
Because if I get a positive number,
it'll put one in front of the other.
If I get a negative number, it'll put the other one.
If they're equal, it'll leave them.
So this is sorting each one of those by amplitude,
and if I refresh this, oops, sorry,
the smallest one is, I sorted it in reverse order.
So let's put b there, b here, a here,
and let's also give myself, let's clean up some stuff here.
Let's make this 800 by 600.
Let's set the offsets to width divided by two, 100,
height divided by two, whoops, sorry, 100,
height divided by two.
Let's set these offset a little bit more.
Let's refresh, whoops, let's shrink this up,
and let's move this down a little bit.
Will this work? (instructor laughs)
All right!
(bell dings)
(train whistle toots)
This is the thing finished!
72 hours later, there it is.
Oh, it's off the bottom.
Oh no, it's kind of sitting right there perfectly.
How did my math, that was totally accidental, by the way.
Now it's just going to draw it again over and over again.
But I want to do a couple other things.
One thing I want to do is if time does a full cycle,
then I want to set time back equal to zero,
and path, clear the path.
All right, this concludes this particular coding challenge,
where I took a discrete Fourier transform,
this particular math function, I applied it
to an arbitrary signal, two signals of X's and Y's.
Then I rendered those as rotating epicycles,
and I had to draw the path.
Whoo, I'm very excited that I accomplished this.
So, there are two things that I want to do, probably
more than two, and those are going to come in separate videos,
if you made it through this one.
I am going to, first, I'm going to take a break, and I'm going to
come back, and I'm going to make it so that the user draws
something, and then it computes the Fourier transform.
That really, by the way,
you should go do that yourself right now.
So take this code that I've released,
find the link in the video description,
and go make a version where the user draws something
and then do the Fourier transform.
That's a fun exercise.
I'm going to do that in the next video, and then,
I am going to rewrite this so that I have
the Fourier transform done with the X and Y's together
as a complex number, and I just have
one set of epicycles rendering the full path.
But I kind of like these two X and Y machine things.
It's kind of cool.
Oh, yes, and Melvin in the chat is saying,
oh, you could use the Quick, Draw dataset.
So I'm going to leave that to you, the viewer.
Please make this, share it widely.
Make a version of this that renders random drawings
from the Quick, Draw data set.
That would be super fun.
I would love to see that, okay?
If you make any of these exciting, fun, beautiful,
strange, ugly, whatever they are, variations
on this particular coding challenge, please go to the link
to codingtrain.com, look for the instructions
on how to submit your variation, and submit yours,
and if you have trouble doing that, file a GitHub issue
or something saying, I want to submit mine,
but I don't know how, and we will help, okay?
Goodbye, everybody.
(bell dings)
(train whistle toots)
And I will leave you with something
that really needs to happen to this code.
(upbeat disco music)
♪ I will refactor this later ♪
♪ You know I will refactor this later ♪
♪ I will refactor ♪
(upbeat pop music)
(bell dings)