# graham_scan

Implementation of the Graham Scan algorithm to calculate a convex hull from a given array of x, y coordinates.

## Stats

StarsIssuesVersionUpdatedCreatedSize
graham_scan
11101.0.56 months ago9 years ago

## JavaScript Graham's Scan Convex Hull Algorithm

I required a simple implementation to calculate a convex hull from a given array of x, y coordinates, the convex hull's in js I found either were a little buggy, or required dependencies on other libraries. This implementation just takes the x,y coordinates, no other libraries are needed. These four examples show how to utilise with Google Maps: Example 1 Example 2 Example 3 Example 4 View GitHub pages

### Building

This produces `graham_scan.min.js`:
``npm install``
``grunt build``

### Testing

The source is tested with qUnit, tests executed with Google's JS Test Driver.

### Usage

``//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();``

### Algorithm

``GRAHAM_SCAN(Q)``
``Find p0 in Q with minimum y-coordinate (and minimum x-coordinate if there are ties).``
``Sort the remaining points of Q (that is, Q − {p0}) by polar angle in counterclockwise order with respect to p0.``
``TOP [S] = 0                ▷ Lines 3-6 initialize the stack to contain, from bottom to top, first three points.``
``PUSH (p0, S)``
``PUSH (p1, S)``
``PUSH (p2, S)``
``for i = 3 to m             ▷ Perform test for each point p3, ..., pm.``
``do while the angle between NEXT_TO_TOP[S], TOP[S], and pi makes a non-left turn  ▷ remove if not a vertex``
``do POP(S)``
``PUSH (S, pi)``
``return S``

### References

• http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/ConvexHull/GrahamScan/grahamScan.htm
• http://en.wikipedia.org/wiki/Grahamscan