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,

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.