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/Graham_scan
License
MIT License