## 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