graham_scan
    DefinitelyTyped icon, indicating that this package has TypeScript declarations provided by the separate @types/graham_scan package

    1.0.4 • Public • Published

    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

    Keywords

    Install

    npm i graham_scan

    DownloadsWeekly Downloads

    1,189

    Version

    1.0.4

    License

    MIT

    Last publish

    Collaborators

    • brian3kb