JSPM – graham_scan@1.0.5

Package Exports

graham_scan
graham_scan/graham_scan.min.js

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (graham_scan) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

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

License

MIT License