Usage
Include either the source or the minified JavaScript file in your HMTL, no libraries are required for the calculation, but you will need to running on ECMAScript 5/ JavaScript 1.6 capable browsers.
The below code is how to get the convex hull points array from your source points.
//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();
The examples use Google Maps, so take a look at those to see how the hull works together with the service.
About
The solution is based on the following formal algorithm taken from Rashid Bin Muhammad's Kent State University site.
GRAHAM_SCAN(Q)
1. Find p0 in Q with minimum y-coordinate
(and minimum x-coordinate if there are ties).
2. Sort the remaining points of Q
(that is, Q − {p0}) by polar angle in
counterclockwise order with respect to p0.
3. TOP [S] = 0 ▷ Lines 3-6 initialize the stack
to contain, from bottom to top, first three
points.
4. PUSH (p0, S)
5. PUSH (p1, S)
6. PUSH (p2, S)
7. for i = 3 to m ▷ Perform test for each
point p3, ..., pm.
8. do while the angle between NEXT_TO_TOP[S],
TOP[S], and pi makes a non-left turn
▷ remove if not a vertex
9. do POP(S)
10. PUSH (S, pi)
11. return S