Subtitles section Play video Print subtitles [TOY TRAIN WHISTLE] Hello, and welcome to a coding challenge. Today, I'm going to tackle the gift wrapping challenge. I'm going to make this code, I'm going to wrap it up as a nice present, and I'm going to hand it over to you. And hopefully you will make something beautiful out of it, or you'll learn something, or all that kind of stuff, that jazz. This is some code that I wrote a long time ago for an example. And this is a demonstration of calculating a convex hull. This, if I did it correctly, is actually using a different algorithm from gift wrapping called the Graham scam. It's not a scam. It's not a scam. The Graham scan. And there are a variety of algorithms for computing a convex hull. There's the Chan algorithm, and more. And they have various different efficiencies. The gift wrapping algorithm is probably the least efficient, but it's a good starter one. So let me talk about what a convex hull is first, and then look at what the algorithm is, and then we'll go and write the code for it. And this, I should say, is an algorithm part of the field of research called computational geometry. And I would really like to do a variety of coding challenges around different computational geometry topics. So if you have an idea for one, write it in the comments. So the idea of a convex hull is, first, we need just a random collection of points. So if we have a two-dimensional space-- and these algorithms typically generalize to higher dimensions. But you know me, I just like to be in two dimensions. Here's my random collection of points. Now, first I need to make the distinction between convex and concave. So here is a shape that is distinctly concave, a Pac-Man-like creature, so to speak. All of these angles that are made out of the vertices of the shape, there is one that is greater than 180 degrees. So a convex shape-- I always get this confused, but now that I know the term convex hull, I won't forget it again. If I wanted to turn this into a convex shape, I would eliminate this point and connect these two points. And now I have a convex shape. And a convex hull is a polygon that you construct that is convex and contains all of the points. So I can eyeball this, and I can say, OK, I'm going to go here, then here, then here, then here. Now, would I go in here? No, I'm going to go down to here, here, here. Am I going to go here? Nope, I'm going to go here. So this is essentially the gift wrap-- I just sort of did my own performance, with my brain, of the gift wrapping algorithm. I'm eyeballing it, you know, I think I got it right. But there's a proper way we can actually calculate it. And the way that you do that is by first starting with a point that we know is exterior to what will be-- that's on the convex hull. The way to start with the point that we know that will be on the convex hull, the vertex of the convex hull, is by picking out the leftmost or the rightmost or the topmost, or the bottommost. So a convention is just to pick the leftmost. So I can see, this is the leftmost point. Now what I want to do is check this point against every other point. And whichever one is furthest to the left-- whichever one is furthest to the left is the next point. So these are going to be in some random order, I'm going to check them in some order, and I'm eventually going to determine that, ah, OK, which vector is most to the left? It's this one. So now I'm going to go here. And now I'm here, and I want to do the same thing. But now I want to pick which one is left of this, relative to this point. And that's going to be this one over here. We can sort of see-- like if I draw a line out to all of the points, if I sort them all along a radial path, the one that's all the way to the left will be this one. And then I just do that over and over and over again, until eventually I get over here. And I find that the one furthest to the left is the one that I started with. And that's going to be my convex hull. Coming back over to the computer, on the Wikipedia page, we can see a nice animation of this playing out. And this, by the way, is one of the reasons why I like to write the code for these algorithms without a library. So ultimately, if, when I'm working on a larger project and I need to compute a complex hull for some reason, having a nice efficient, maintained computational geometry library is most certainly the way to go. And maybe I'll try to find some examples of that. There's plenty in JavaScript that I'll link to in this video's description. But most of those libraries will just compute all of the points all at once and hand them back to you. And if you want to create some type of interactive explanation of the algorithm, some kind of animation, whether it's for artistic purposes or educational purposes, you're going to have to write the algorithm itself. And it actually is harder to write the algorithm and animate it. So I'm going to try to do that as part of this coding challenge. Rather than write the algorithm all at once so that is just calculates it and shows the end result, I want to be able to see something like this animation playing out. That will make this take quite a bit longer. It will be more to figure out. But I think it'll be more satisfying in the end. I also should mention that this 2D case is known as the Jarvis march, invented by R. A. Jarvis. Then the time complexity is O [? nh, ?] n being the number of points, and h being the number of points around the convex hull. And the reason it's that is because, for every point around the convex hull, I have to check all the other points. So that's the number of points around the hull times all of the points. It's a little bit better than o n-squared, but not by much. And again, there are plenty of other more efficient algorithms for doing it, this is just the one that I'm starting with. [BELL DINGING] All right, let's write some code. So I'm just starting with some boilerplate code. I've got an empty array. I'm putting p5 vectors in it. I'm using a p5 vector object to store a point. And then I'm just drawing all the points on the canvas itself. So the first step that I want to do is find-- you could say I could run this over and I'm going to get a random collection of 10 points. And eventually I'll do this with a much higher number of points, but let's start with just 10. So the first thing I want to do is find the leftmost point. And an easy way for me to do that would just be to sort the points. So I can actually go here, and I could say points.sort. And the JavaScript sort function takes a callback function, which is a comparison function which compares two elements. And so I'm going to say a, comma, b. I'm going to use the arrow syntax. If you haven't seen the arrow syntax before, I'll refer you to my video on that. I'll say a.x minus b.x. So what this is doing is it's returning a positive number any time a is to the right of b, and a negative number anytime a is to the left of b. And that should make it such that I can create a global variable. I'll call it left, for like