While working with a significant amount of medical and sales data that needed to be overlaid on a map, I found myself needing to draw regions that contained sales rep positions – but wanted a nice outer hull to be drawn so that reps inside the area did not need to be joined up as google maps was doing when just feeding in the sorted co-ordinates.

After much internet scouring, I just couldn’t find a JavaScript implementation that I was after (or something that did not come with a complete mapping toolkit!), so I started looking at various implementations in other languages (seemed to be mainly C or Java). Once I had found a good explanation of the article and had (hopefully) grasped the math required via Wikipedia – I set off on creating the algorithm in JavaScript.

The resulting code is quite readable, as I am by no means a mathematician, and fairly well commented with unit testing via QUnit to test my logic is spitting out the expected paths.

Usage is quite simple

//Create a new instance.
var convexHull = new ConvexHullGrahamScan();

//add points (needs to be done for each point,
//a foreach loop on the input array can be used.)
convexHull.addPoint(x, y);

//getHull() returns the array of points that
//make up the convex hull.
var hullPoints = convexHull.getHull();

Head on over to the project page on Github, or have a read through the projects GitHub Pages site to see some live examples.

I have applied a couple of bug fixes thanks to some feedback on GitHub, its great to see code originally just written for yourself, being used by others 🙂