[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.
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,
I'm sorry, left.x and left.y--
I should see that the left point is green.
So there you can see that.
And every time I run it, whichever point is most
to the left is going to be green.
Great.
[CLAPPING HANDS]
Now I need to find the next point on the convex hull.
And remember, I want to animate this.
So really if I were to just go back to the Wikipedia page
and look at the pseudocode, you're
going to see everything happens in just a set of nested loops.
I don't want any loops to happen because I want--
every time through draw, I want to--
the p5 draw loop, I want to draw the next stage.
So I'm going to need another array, which
will be the points that I'm placing along the hull.
I want to say a left can be kind of--
I think I want the original, left like the leftmost.
I'll call this leftmost.
And then I'm going to call this current hull, current vertex,
like that's the current vertex that I'm checking with.
And then I want to say, let, and then current point.
So vertex, I'm going to use that term, when it's basically
a vertex along the hull.
And point is the current point that I'm checking
to see if it's the next vertex.
So maybe I also need next vertex.
So I think these are what I need.
And so leftmost is this.
And that's also the current vertex
is going to start as the leftmost.
And then, actually, the current point is really an index.
So let me call that, index.
And this is next vertex.
And index it's going to start at 0.
And this is leftmost.
We can make the leftmost point a little bigger.
Let's also do current vertex as blue.
So we don't see the green one anymore
because the current vertex-- and I should make these brighter.
So let's just do that.
The current vertex is now being drawn over the leftmost vertex.
So I'm going to make a guess that the next vertex is just
points index 1.
I'm going to make a guess when I'm
starting that the next vertex is whatever it happens to be
the next point in the array.
It's could be by coincidence, but it's probably not
going to be.
And then actually the one that I want to check is, then, at 2.
So the leftmost point is 0.
The one that I'm guessing is going
to be the next point is at 1.
And then I got to start comparing everything at 2.
So just for the sake of argument here,
I want to draw a line from current vertex to next vertex.
And let's say stroke, 255, stroke weight, 2.
So we can see-- look at that.
Oh, no, because they're sorted.
So of I actually get lucky a lot of the time,
because they're sorted.
But you can see, in this case, that's
not-- it's really got to pick, probably, this one or that one.
So that's where it's starting.
Now what I need to do is I also want
to draw a line with the one that I'm checking.
So I'm going to say checking is points index.
Then I also want to draw a line to the one that I'm checking.
So we can see those are the two that I'm comparing.
So these are the two that I'm comparing.
And let's make this stroke--
so this one's going to be green.
And the one that I'm checking will just be white.
So this is what's happening right now.
I need to compare these two.
I need to figure out which one is to the left.
And by to the left, I mean basically
like counterclockwise rotation.
And guess what, there's a really nice way that I can do that.
And the way that I could do that is with the cross product.
The cross product is a particular vector operation
that you can apply on a 2D vector--
two vectors that are in the same plane.
And it will return to you a vector pointing perpendicularly
in the third dimension, away.
And so what's interesting about this is--
let me let me show you what I mean.
And I can never remember which is which,
but it doesn't really matter because we just
need to know that it's one or the other.
If this is vector a and this is vector b,
the cross product of these two vectors
will give me a vector pointing out this way.
This would be in like a left-handed system, I guess,
because that's my left hand.
No no no, left-handed would point the other way,
right handed, I'm pointing out.
I think that's how you do it.
The point is, it's pointing out.
But if I were to say, this one is b so I'm doing a cross b,
and this one is a, then I'm going
to get the cross product pointing in the other way.
So I just need to test, is the z-value of a cross product b,
is it greater than 0 or less than 0?
If, by the way, they were colinear or along
the same path, you'll get 0.
And we're just going to assume, for this case,
that when I'm picking random points, none of them
are going to be colinear.
It will probably sort of work out anyway.
But so if b is to the left of a if z is less than 0,
it's to the right of a if z is greater
than 0-- or the other way around, but I'll just test it.
And it's flipped, anyway, in a computer graphics system,
so it'll work itself out.
Let's go try that.
So let's write the code for that.
So what I need is I need those two vectors.
So a is a vector that points-- so I can use the subtraction
function, because I can point from what is currently
the next vertex to the current vertex.
That will be vector a.
And then B will be pointing from what I'm
checking to the current vertex.
And then the cross product is a.cross b.
So I can implement the math for the cross product,
but it's actually just there in the p5 library for me.
And then I just want to say, if cross is greater than 0,
then probably something like--
So let me not do anything right now.
Let's just see.
Let's just console.log the cross product.
So let's see.
We got-- oh, cross.z, the z-component.
We got a negative-- oh, come on, it's becoming more obvious.
All right, so we got a negative number.
So the one that I'm checking is white.
The one that it currently thinks is green.
So is that right?
The current one is green.
So if it's less than 0, then that's to the left.
So if cross.z is less than zero, then nextVertex
should actually be the one that I'm checking.
And then I just want to say index equals index plus 1.
There we go.
So you can see, as it goes through,
it's always going to find the correct one.
It's checking them all.
Let's make a lot of points so it takes longer.
Ooh, that was weird.
Why did that mess up?
It found it, like, instantly, but it's checking them all.
Yeah, it's going to find it pretty close because they're
sorted.
But I think it's doing it correctly now.
Something that I want to add that I think will just
make this a little visually easier to follow
is, let me make a little variable called buffer.
And I'm going to say, pick a point between buffer
and width minus buffer, and the height also between buffer
and height minus buffer.
And let's make that buffer even bigger.
So now the points won't get picked super close to the edge.
So clearly I need an exit condition.
So I'm going to say, if index equals
points.length, that means I've gotten to the end of the array.
Let me at least say, no loop here.
So I'm going to just stop it from animating
once it gets to the end.
And let me just go back to many fewer points.
I'll just go back to 20.
We'll do that pretty quickly.
And so what should happen is hull should
get the next vertex.
Did I put the current vertex into--
so hull should get the current vertex.
So now there are two points in the hull.
The current vertex should equal next vertex.
And then I need to reset index back to something.
So let's also now add something where I draw the hull.
So I'm going to say beginShape, stroke--
let's have the hull be blue.
beginShape-- I'm going to draw a let p of hull.
And I'm going to draw all the hull points and shape.
And I'm not going to say close, but I am going
to give it a really light fill.
So I'm going to say fill, also have it be blue,
but with a lot of alpha.
Then I need to add vertex.
And I don't think I'm going to see the hull yet.
Because I've only drawn two points so far,
and I've stopped the loop from looping.
So let's see what happens.
What if I just reset index back to zero and turn off no loop?
OK, it got stuck.
So I don't want to-- oh, first of all, that's two equals.
That should be equals.
Oh, interesting-- so even though you
see that it's doing it over and over again,
it's stuck just picking the same vertex over and over again
because that one is one of the ones I'm checking.
So one way I could approach it is remove that one.
So the easiest way to do that would be with splice.
So I also would want to pick the--
I'm going to say, the next vertex,
I also should keep track of that next index.
[? Let me ?] just set that equal to negative 1
as an initial value.
And then when I find it, I want next index
to be that index value.
And then I can say, points.splice nextIndex,
and just take that [? 1 ?] value out.
Now I'm still stuck.
So the reason why I'm still stuck
is because nextVertex that it's comparing everything to
is still that same one that it got before.
So what I should do is just reset nextVertex
to something else.
I'll just put it back to be that leftmost one.
There we go.
So now you can see it's working.
Now it's stuck when it gets to the end.
But guess what?
The reason why is--
I know when I'm done, right?
I am done if it actually picks nextVertex
as the same as the leftmost.
So when it finds that one, then I
can say console.log done, noLoop,
and then, otherwise, do all of this other stuff
that I'm doing.
So let's see how this goes.
(SINGING) Voila.
So the chat actually is pointing out to me, and rightfully so,
that this splicing-out of the one that I saved
is problematic because I've corrupted the data itself.
I don't have that original array of points anymore,
and the context that I might be doing this in,
that might actually be important.
So I could keep that in a separate array,
I could add it back in.
But actually it turns out-- and I've just discovered this
through some debugging-- that I don't even need to delete it.
The problem was really the fact that nextVertex was not
reset back to the leftmost.
So it's actually going to work just fine every single time
without splicing that out, as long as I reset the next vertex
back to, like, leftmost, so that it sort of skips getting stuck.
So let's just make sure this-- let's watch this happen now
with like 200 points.
And I will speed this up for you.
[ISLAND MUSIC PLAYING]
[BELL DINGING]
OK, we can see that it's done, and it looks correct.
I'm pretty sure I did this correctly,
because it seems to be working.
Of course, this is less efficient
because I'm checking extra points
that I don't need to check because they're already
part of the convex hull array.
So I could add something to skip those.
But this isn't even the most efficient algorithm
in the first place.
But I just want to get this idea to work.
So you could see that it doesn't actually connect at the end
because I don't have close as one of the--
in endShape.
So I could add that in.
Let me just put that in for you.
You'll see what this does differently.
[JAZZ MUSIC PLAYING]
All right, so you can see what it's doing now.
It is always closing the shape with whatever the latest
vertex is.
But really, while I have implemented this and gotten
this working, I have not picked nice colors
or been really thoughtful about the stroke weight,
or how-- this takes a very long time to animate,
so it's nice that I'm kind of animating
every single possibility.
But I think you could probably make something pretty
interesting out of this by changing the way you draw it,
or thinking about how you might make this interactive,
or maybe the user can add points.
There's a lot of possibilities.
But this will be a nice building block, a foundation
to hopefully do more computational geometry coding
challenges.
In particular, eventually, I want
to build a triangulation around all these points,
and then figure out how to make a Delaunay triangulation, which
has to do with a way of having all the triangles--
the circle that fits any given triangle
doesn't include any other points.
It's known as a circumcircle.
So I think I will come back and do a coding challenge just
to do the circle that fits any given triangle.
It's a pretty quick thing that I can show you.
But there's a lot more to come with this.
Make your own version of this, share it with me,
go to thecodingtrain.com, to the page with this coding
challenge, and there's instructions there
of how to share your version of this.
Maybe you could tie this to sound or something
else that I can't even possibly imagine now.
I look forward to seeing what you make.
Oh, also, you might want to investigate
one of the other algorithms, in particularly
Graham scan algorithm.
Maybe I'll come back and actually just do
that as a video also.
But if you make a version of that,
please submit that as well.
OK, thanks for watching.
See you soon.
[TOY TRAIN WHISTLE]
[DANCE MUSIC PLAYING]
[BELL DINGING]