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:


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;
  }
 }
}

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);
}