Simple Convex Hull Generation in JavaScript.

I stumbled across this page and decided it would be fun to convert it to run in JavaScript.

Ok it is not the best method for finding the convex hull but given it is really simple idea that results in a small amount of code it can be quite useful.

The basic idea is you find the left most point from the collection of points. If two are equal you take the lowest y value.

Set this to be the end point of the lines that form the convex hull

Then we loop round all the points attempting to find a line segment from the end point to another point that has all the other points to the left of it. This forms the next point of the convex hull and we add it to our convex hull collection as well as setting it as the end point.

Just keep going until the end point that we find is the equal to the first point in our convex hull collection.

Code is often clearer than a written description of it so here's the code.

// Gift wrap method
function convex_hull(pnts){
    var out = [];

    var startIdx = findLeftMostLowestPoint(pnts); 
    var hull = startIdx;
  
    var npts = pnts.length;
    var endpt = 0; 
    do 
    { 
	out.push(pnts[hull]); 
	endpt = 0; 
	for (var j = 1; j < npts; ++j) 
	{
	    if (hull == endpt || isToLeft(pnts[hull], pnts[endpt], pnts[j]))
		endpt = j; 
	}
	hull = endpt; 
    } while (endpt != startIdx); 
    
    out.push(pnts[endpt]); // close the poly
    return out;
}

and here are the helper functions you need.

function findLeftMostLowestPoint(pnts){
  var idx = 0;
  var npts = pnts.length;
  for (var i = 1; i < npts; ++i) 
  {
    var a = pnts[i];
    var b = pnts[idx];
    if(a.x < b.x || (a.x == b.x && a.y < b.y))
      idx = i;
  }
  return idx;
}

function isToLeft(a, b, c){  
    var u1 = b.x - a.x; 
    var v1 = b.y - a.y; 
    var u2 = c.x - a.x; 
    var v2 = c.y - a.y; 
    return u1 * v2 - v1 * u2 < 0; 
} 

That is all you really need.