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

Jun 06, 2021
(bell rings) - Hello, welcome to a

## coding

### challenge

. I actually just finished this

## coding

### challenge

and I'll be back to re-record a little intro. And what I made in this coding challenge is a

### drawing

machine. Maybe we'll call this a Fourier

## transform

### drawing

machine. There are a few more things we want to do with it. There will be some follow-up videos. But this very, very long video, if you can bear to watch it, has, as part of it, at the end, this. This is the final result. I'm using an algorithm called Fourier Transform to take an arbitrary signal, in this case a sequence of X and a sequence of Y, the Coding Train logo path, thanks to Tom Fevrier.
I'll link to the Twitter of Tom Fevrier, who provided the path for this particular logo, to trace the logo's path through this type of sequence of rotating circles, sometimes called

#### epicycles

. Well, what's going on here? So the first thing I should mention is that this is a continuation of my Fourier Series coding challenge. 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 had to write that. But in this video, I'm going to do something different: I'm going to use the Fourier

algorithm.

## coding challenge 130 1 drawing with fourier transform and epicycles...

And these are different concepts. I somehow combined them in my previous video. The idea of ​​the Fourier transform. Now, where I know this algorithm, where I learned about this algorithm first, learning about coding and creative coding and new media and sound and video is with the FFT terminology, and in fact, if you go into the p5 sound library, you'll see that there are 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. By the way, the algorithm I am going to implement is the discrete Fourier transform.
Why is this the case with the FFT and where is it typically used? Well, it's typically used in signal processing, but a familiar place it can be found is in audio signal processing. So let's say you have an arbitrary sound wave that maybe looks like this, and it has a very high-pitched, horrible, screeching sound. How would you filter that? Well, if you could take this pattern of sound waves and split it into a bunch of smaller sound waves, a bunch of sound waves that have different amplitudes and frequencies, then you could take, you could eliminate the one that has the add a high-pitched sound and then come back.
Add them all and get a new sound wave. So the idea of ​​a Fourier transform, I think I said it in the Fourier Series, but it's a non-liquefied shake. If we could take a smoothie made with blueberries, mango, and strawberries, take it apart, 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 audio, it's going to be a series of X values ​​or a series of Y values ​​and finally, there's a way to do it with the together I will reach.
So, I'm not going to go too deep into the math in this particular video. I am not going to derive the algorithm from the Fourier Transform. I'm not going to talk about the Fast Fourier Transform. I'm just going to use a very crude Discrete Fourier Transform implementation to make everything work. However, if you want to know more about mathematics, let me reference some really key references. The video by 3blue1brown, But what is the Fourier Transform? It will give you an infinitely better understanding of what the Fourier Transform algorithm is and what it does, and even how it works, much better than if you tried to ramble on about it on the whiteboard.
I would also highly recommend this video from GoldPlatedGoof, Fourier Analysis for the Rest of Us, which goes into the details of the mathematics in a much more in-depth way, and then there is this wonderful video from Mathologer, Epicycles, Complex Fourier Series and the Orbit by Homer Simpson. That will give you the full story of everything I'm trying to do. But I hope what's useful to you and what's different in my video than these is that I'm just going to sit here and try to code it. And I know 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'll get the code, make your own variation, and share it with me. You can go to thecodingtrain.com, to the particular coding challenge page, and then you'll find instructions on how to submit a variation to the user community there. Okay, bye, enjoy it, or not, or whatever. I'm ready to start coding, finally. Now, this is where I left off earlier in my Fourier Series coding challenge, and the difference now is that what I want to do is be able to have an arbitrary signal and then calculate what all of these amplitudes, frequencies, and phases should be.
So the way I'm going to do that is, let's think about this. Actually, this is a bunch of Y values ​​that I'm calculating. So let's make an array called something like Y, and this will be the signal, this is my signal. This could be audio, it could be Y positions, any digital signal/arbitrary set of numbers. So what I want to do is have the Fourier transform of that particular signal. So I mean,

Y =

#### fourier

Transform, or maybe like dft, discrete Fourier transform, of the value Y. So this is the idea. The first thing I need to do is calculate the discrete Fourier transform of an arbitrary signal.
Now I need some kind of signal. So I think what I'm going to do absurdly is encode the signal. In fact, let's do it as a square wave and then we'll know if it worked. What then is the square wave? The square wave would be something like 100, 100, 100, - 100, -100, -100, and then do it a few times. So this will be my arbitrary signal, which I'm simply encoding as a square wave. And we'll do some interesting things that we could, maybe I'll try a Perlin noise signal or just a sine wave signal. We'll try different things, random numbers and see what it does.
So this actual code here can stay largely the same, because in theory the difference is that now, instead of following the Fourier series specific to the square wave, I just need to take the results of my discrete Fourier transform. So this would be a loop that will loop through the length of that transformation, how many different wave patterns there are that I'm adding together, and ultimately I'll have to figure it out. So let's talk about this right now, and there's a little problem where I have these x and y as local variables here. But I think this will be fine.
So let's update this and DFT is not right. Okay, first step, let's write the discrete Fourier transform algorithm. So, I'll start by creating a function called dft. It will have a series of values ​​and now 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 of things. One is the one I highly recommend, if you want to pause this video right now and read this particular article on James Schloss's Algorithm Archive or the LeIOS YouTube channel. This is a really good article on Fourier transforms and the discrete Fourier transform algorithm, and this particular algorithm for FFT.
But what I'm going to do is 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 transformation is capital X sub k. So I need to write a function that calculates 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 to work with Fourier transforms, I need to understand something called a complex number. Now, if I remember correctly, the last time a complex number appeared on this YouTube channel was probably in my Mandelbrot set coding challenge, where I visualized the famous Mandelbrot fractal, and made reference to something called an imaginary number, and I was too.
Casual, relaxed and joking about how I talked about imaginary numbers being something imaginary that doesn't exist, which is absolutely incorrect. The reason the term imaginary is used is because there is no real number solution for the square root of negative one, but in mathematics the square root of negative one is referred to as i. I is a complex number. A complex number is a number that has a real component, a, plus an imaginary one. So they are two real values, one real value and another real value multiplied by i, the square root of negative one. This is the idea of ​​a complex number, and by the way, another way I refer to a complex number is by its position in the complex plane.
So if this was the real axis and this was the imaginary axis, this would be a, and this would be b, and this is a vector representation, wow, of this particular complex number. So why do I mention this? The reason I mention this is that the Fourier Transform algorithm, even if I start with a series of real numbers, simple numbers, I will apply the Fourier Transform and I will get a complex number. What I'm going to return from that function are a and b, also known as the real component, which is often written in code as re, and the imaginary component, which is often written as im.
This is something I really need to understand before working with this formula. So now it's 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 doing some kind of visualization, and you just you want to stop. But together, you and I, we won't stop. Let's figure out how to translate all this notation, symbols and so on into JavaScript code. Now, again, it will be very interesting to delve into the drift of all these formulas and the background of how the Fourier transform works, but I'm not going to do that.
If you look at the video description, there are several great videos and resources linked that will give you that information. But I do want to mention one thing, which is quite important, and that is that this particular formula at the top for the discrete Fourier transform uses this symbol e, the Euler number or the basis of natural law. This is a very famous number in mathematics, very similar to pi, but there is also a very well-known formula called Euler's formula, which looks like this: e to the power of i, which, complex number i, x, is equal to the cosine of x plus i times sine of x.
Really interesting, it looks like a transformation from polar to Cartesian coordinates. This is all interrelated, right? But that's where, if I go back here, this is where we get the second line, using the Euler formula from the particular formula above. But this is the one I want to implement and I've written the formula here so we can unpack it a bit. What are the components we need to understand? Now, really, if this were a math lesson on the Fourier Transform, we wouldn't be using addition; we would be using integration. But since we are working on a computer and I need to write a loop, and I don't have infinity as a tool I can use, I need, instead of doing integration, to do addition, and that's why this is also called discrete transform of Fourier, because I'm doing it in this kind of discrete space.
Okay, so this means sum. So this should give you an idea of ​​what I can do as a for loop, going from zero to n. And by the way, n will be the length, the number of values ​​that I have in my signal, that is, the length of that original array. Oh, and then the other thing that's really important is that basically what I can do is break away. This is the real component and this is the imaginary component. So even though this is all written as a formula, I'm going to summarize all the real components and all the imaginary components together.
And by the way, as Simon, who's been watching this live, pointed out to me, there are just complex numbers. The term imaginary, it's really a shame that it's called imaginary, because it's very misleading. But a real number is simply a complex number with the imaginary component equal to 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, because I called it Y, but these are just the values, the waltzes. This n is waltz.length in my code, and then k, we're going to have to figure out what k is.
I know what cosine is, two pi and all that stuff. So let's find out what k is. Oh boy, I'm so stupid. What is K? Actually, this should, this is, this is, I completely forgot to write what is possibly the most important part of this formula (instructor laughs) here, which is capital X, big X, sub k equals. So this is what I'm trying to calculate. I am trying to create an array of k elements. In each element k, I'm going to summarize n from zero to the end. So there's a little nested loop here. I want to loop through each k, which goes from zero to n, and then also summarize.
So k will remain constant within each of these, and k is actually the frequency, we'll see, the frequency of the particular wave pattern at thatcosine of, this is so dumb, 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 is very recognizable, so I know if it's working or not, and then Y will be the core of that. So we can see, okay, this looks promising, right? Now we can see here are the Epicycle Calculations for the on your side?
This HALF_PI is really like the rotation of everything, how I want to display it. So let's make that an argument here and we'll call it rotation. And then the Y, oh, that's when I, do I want it? Yeah, I think I can do that when I draw it, okay. Where is this now? (instructor laughs) The Ys should have a HALF_PI offset and the Xs should not. And now look at this. Well, in theory now (the instructor laughs) we are getting somewhere, don't worry. What I want to do is place this here and then place it a little bit more here.
And now what I want to do is there, where the mouse pointer is, I want to take the Y from here and the X from there and draw the path. So instead of a wave I was drawing a wave pattern, now I want an array that is the full path. Basically I want to get the final result. So let's make this

#### epicycles

function return, it should return a value which is a vector. createVector with x and y. So whatever the end result is, like the last point x and y, the end of that epicycle sequence, and then, I have vx is this, that's the vector for the .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. Instead of drawing this wave, I'm going to iterate over the path. I don't know if I've done it, this is a bit of a weird refactoring of what I had before, but I think it'll make sense to you in a second.
We'll see. I may have to go back and explain this. (instructor laughs) Let's put this here. And the wave is not defined, because it is a path, a path. I'm not going to worry about this now. Let's put that aside. Alright, it's over there. Oh, it's in the wrong place. (Instructor laughs) So, this is actually correct. I just put the, now I realize, like, (bell sounds) this is right; I just put them in strange places. I want the one who does the Y here and the one who does the X there. I don't know why he 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 in a strange way. Here we go. (the instructor laughs) So I wanted to see them like that. Now you can see, those are the Fourier transforms for this particular circle, and let's add a line now, which is basically this. So I also want to draw a line from vx.vy, oh, so vx.x, vx.y, to v.x, v.y. I just want to draw these two lines, and the same of y.x and y.y. Wow, my naming is wildly confusing here.
So this could definitely use some refactoring, but. Here we go. Now we can see those lines. So this is good. Now, I don't like the way this is spaced, so one way to fix it would be to make this smaller, and that helps me a little. But this can change. I don't know why I put it up there. Let's move this to 300. Okay, this is a little bit better. Now, let's do 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 an arbitrary amount, and we can see, look at this.
So you can see this works, and let's give it, let's make the amplitude bigger, and let's give it like 500 values, wow! And there is no reason for it either. This is very silly. These should just be in a loop. But let's give it more values ​​and say, you know, I divided it by 50. I'm just doing arbitrary things, because the point of this is to make a drawing. Okay, but we can see how this will now take any arbitrary signal and calculate the Fourier transform for the X's and Y's and draw that path. (instructor applauds) Now, the cool thing about this is that I'm about to do something almost instantly to make it a lot more interesting.
I'm going to go and take the Coding Train logo route. The point of this is to forget about calculating a route. I want to have a known path, a drawing. (bell rings) I went back and brought a JavaScript file that just has a bunch of X's and Y's all in a variable called drawing, which is the continuous path of the Coding Train logo. Thanks, 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 this work by now. (Instructor laughs) Oh wow, it better work that way.
I'm so excited. I'm going to go here, of course, and now, I'm going to say, I mean, it's a little silly, the way I'm doing this, by drawing.length, i++. I'm going to pass, right? Remember, this variable, drawing, is just an array of X and Y, and I'm going to make the X drawing.x and the Y drawing.y. Now, here's the thing. I happen to know that the complexity of that drawing is much more detailed than I need and that it will run very, very slowly. So in fact, I'm going to add a variable called skip, and I'm going to 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 just do every five vertices of the drawing. I'm doing this ahead of time, because I already know, looking at it, I don't need that many points. So this should now give me all the points, all the X's and Y's, of that particular drawing. (instructor laughs) (drum roll) I'm about to update and I hope this works. (instructor laughs) There it is! (dramatic fanfare) So there it is. Now, this doesn't look as beautiful as it could, and there are a couple of reasons for that. Right now, one thing is that they certainly look like these strange alien creatures, but it would be very nice if the epicycles were represented in order of amplitude.
Right now, they're rendering in order of frequency, and it's like this weird machine, almost like a drawing machine. It would be great if someone could physically build this. But what I'm going to do is organize them. So, I'm going to say fourierX.sort and fourierY.sort. Now, the JavaScript sort function allows you to pass a callback, which is essentially a function that tells you how to compare each element, and I want to compare them by breadth. So I can say any two arbitrary elements and I'll use the ES6 syntax for this. If you haven't seen my arrow syntax or higher order array videos, this is something that will give you some insight into this.
And then I can say, I think a.amp - b.amp, right? Because if I get a positive number, it will put one in front of the other. If I get a negative number I will enter the other one. If they are the same, he will leave them. So this is sorting each of them by width, and if I update 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 hand it over too, let's clean up some things here. Let's make this 800 by 600.
Let's set the offsets to width divided by two, 100, height divided by two, oops, sorry, 100, height divided by two. Let's establish these offsets a little further. Let's refresh, wow, let's reduce this and bring this down a little bit. will this work? (the instructor laughs) Very good! (bell rings) (train whistles) This is finished! 72 hours later, there it is. Oh, it's off the bottom. Oh no, it's sitting there perfectly. How did my calculations come out? That was totally accidental, by the way. Now you'll just draw it over and over again. But I want to do a couple more things.
One thing I want to do is if the time makes a complete cycle, then I want to make the time equal to zero again and the path, clear the path. Alright, that concludes this particular coding challenge, where I took a discrete Fourier transform, this particular mathematical function, applied it to an arbitrary signal, two signals X and Y. Then I represented them as rotating epicycles and I had to draw the way. Wow, I'm so excited to have accomplished this. So there are two things I want to do, probably more than two, and they will come in separate videos, if you managed to finish this one.
First, I'm going to take a break, come back and have the user draw something and then calculate the Fourier transform. That really, by the way, you should do yourself right now. So take this code I posted, find the link in the video description and make a version where the user draws something and then does the Fourier transform. It's a fun exercise. I'm going to do that in the next video, and then, I'm going to rewrite this to have the Fourier transform done with the X and Y together as a complex number, and I just have a set of epicycles that represent the full path.
But I like these two machines X and Y. It's kind of cool. Oh yeah, and Melvin in the chat says, oh, they could use the Quick, Draw dataset. So I'll leave that to you, the viewer. Please do this, share it widely. Make a version of this that represents random drawings from the Quick, Draw data set. It would be very fun. I'd love to see that, okay? If you make any of these exciting, fun, beautiful, weird, ugly, whatever variations of this particular coding challenge, go to the codingtrain.com link, look for the instructions on how to submit your variation, and submit it. yours, and if you're having trouble doing that, file a GitHub issue or something that says, I want to submit mine, but I don't know how, and we'll help you, okay?
Goodbye everybody. (bell sounds) (train whistles) And I'll leave you with something that really needs to happen with this code. (upbeat disco music) ♪ I'll refactor this later ♪ ♪ You know I'll refactor this later ♪ ♪ I'll refactor ♪ (upbeat pop music) (bell sounds)