A convex hull is where a convex polygon is constructed to bound a set of points on a 2D plane. So, given all points in the set P, what is the smallest convex polygon we can construct that bounds all points in P.

Pseudo code:

- Randomly place n points on a 2D plane.
- Find the leftmost point/the point with the smallest x value. Called `gamma`.
- Find the vector which is the
*most left*which connects `gamma` to point q in set P. - Store `gamma` and q in a list and repeat until q = `gamma`.

This canvas starts off by generating a set amount of points, placing them at random locations around the screen and adding them to an array. It then finds the index of the point in the array - `vertices[]` - with the lowest x value. It then loops through the array finding all vector's originating from `gamma`, `vec(gammaP(i))`.

We then examine each vertex and evaluate which one is the *leftmost* from the perspective of point `gamma`. Say in this case `P(q)` is the leftmost vector so we push q onto the stack.

Stack: `((q), (gamma))`

We then repeat until we reach our starting point, which in this case means our starting point is the same as the next point (`q=gamma`)

Now the question of how to calculate the *leftness* of a vector compared to another. We can use the cross product in 2D.

`vecu times vecv = u`_{`x`}`*v`_{`y`}` - u`_{`y`}`*v`_{`x`} If the cross product is greater than 0, the vector is to the left. If it is equal to 0 then the vectors are colinear

**Note:** to convert coordinates to a vector, find the difference between your origin point and your target point

for (var i = 0; i < vertices.length; i++){

if (i != originPoint){

x1 = vertices[recordLeftVector].x - vertices[originPoint].x;

y1 = vertices[recordLeftVector].y - vertices[originPoint].y;

x2 = vertices[i].x - vertices[originPoint].x;

y2 = vertices[i].y - vertices[originPoint].y;

if ((y2 * x1) - (y1 * x2) <= 0){

recordLeftVector = i;

}

}

}

if (i != originPoint){

x1 = vertices[recordLeftVector].x - vertices[originPoint].x;

y1 = vertices[recordLeftVector].y - vertices[originPoint].y;

x2 = vertices[i].x - vertices[originPoint].x;

y2 = vertices[i].y - vertices[originPoint].y;

if ((y2 * x1) - (y1 * x2) <= 0){

recordLeftVector = i;

}

}

}

Now we just have to add in a little piece of code at the bottom of this function to: increment the iteration number so we don't recurse until eternity, add our leftmost vector to the route stack and call the function again with the next point as a parameter.

if (originPoint != recordLeftVector && iterations < 75){

route[iterations] = recordLeftVector;

iterations += 1;

findLeftLine(recordLeftVector);

}

route[iterations] = recordLeftVector;

iterations += 1;

findLeftLine(recordLeftVector);

}