Convex Hull

# Convex Hull - Jarvis' Marsh

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 = ux*vy - uy*vx 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

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.