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,