# brian3kb/graham_scan_js

An implementation of the Graham's Scan Convex Hull algorithm in JavaScript.
Switch branches/tags
Nothing to show
brian3kb Merge pull request #14 from kant/patch-1
`Update URLs`
Latest commit acfc2a9 Jan 12, 2018
 Failed to load latest commit information. example Dec 17, 2015 qunit-lib Jun 17, 2013 src Feb 1, 2017 test Feb 29, 2016 .gitignore Sep 12, 2014 Gruntfile.js Sep 12, 2014 bower.json Jan 10, 2017 graham_scan-qunit.jstd Jun 17, 2013 graham_scan.min.js Feb 1, 2017 license.txt Jun 17, 2013 package.json Jan 10, 2017 readme.md Dec 25, 2017

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

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.)

//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
``````