## Subtitles section Play video

• [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.

• 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,

• 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,

• 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 the leftmost point.

• Left equals points index .

• Zero and now if I were to say, stroke 0, 255, 0,

• and say point p.x, p.y, I should see that the left point-- oh,