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.
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();
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 🙂