Placeholder Image

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.

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