index.js
function fastConvexHull(points) {
    var left = points[0];
    var top = points[0];
    var right = points[0];
    var bottom = points[0];

    // find the leftmost, rightmost, topmost and bottommost points
    for (var i = 0; i < points.length; i++) {
        var p = points[i];
        if (p[0] < left[0]) left = p;
        if (p[0] > right[0]) right = p;
        if (p[1] < top[1]) top = p;
        if (p[1] > bottom[1]) bottom = p;
    }

    // filter out points that are inside the resulting quadrilateral
    var cull = [left, top, right, bottom];
    var filtered = cull.slice();
    for (i = 0; i < points.length; i++) {
        if (!pointInPolygon(points[i], cull)) filtered.push(points[i]);
    }

    // get convex hull around the filtered points
    var indices = convexHull(filtered);

    // return the hull as array of points (rather than indices)
    var hull = [];
    for (i = 0; i < indices.length; i++) hull.push(filtered[indices[i]]);
    return hull;
}
function fastConvexHull(points) {
    var left = points[0];
    var top = points[0];
    var right = points[0];
    var bottom = points[0];

    // find the leftmost, rightmost, topmost and bottommost points
    for (var i = 0; i < points.length; i++) {
        var p = points[i];
        if (p[0] < left[0]) left = p;
        if (p[0] > right[0]) right = p;
        if (p[1] < top[1]) top = p;
        if (p[1] > bottom[1]) bottom = p;
    }

    // filter out points that are inside the resulting quadrilateral
    var cull = [left, top, right, bottom];
    var filtered = cull.slice();
    for (i = 0; i < points.length; i++) {
        if (!pointInPolygon(points[i], cull)) filtered.push(points[i]);
    }

    // get convex hull around the filtered points
    var indices = convexHull(filtered);

    // return the hull as array of points (rather than indices)
    var hull = [];
    for (i = 0; i < indices.length; i++) hull.push(filtered[indices[i]]);
    return hull;
}
function fastConvexHull ( points ) { var left = points [ 0 ] ; var top = points [ 0 ] ; var right = points [ 0 ] ; var bottom = points [ 0 ] ; // find the leftmost, rightmost, topmost and bottommost points for ( var i = 0 ; i < points . length ; i ++ ) { var p = points [ i ] ; if ( p [ 0 ] < left [ 0 ] ) left = p ; if ( p [ 0 ] > right [ 0 ] ) right = p ; if ( p [ 1 ] < top [ 1 ] ) top = p ; if ( p [ 1 ] > bottom [ 1 ] ) bottom = p ; } // filter out points that are inside the resulting quadrilateral var cull = [ left , top , right , bottom ] ; var filtered = cull . slice ( ) ; for ( i = 0 ; i < points . length ; i ++ ) { if ( ! pointInPolygon ( points [ i ] , cull ) ) filtered . push ( points [ i ] ) ; } // get convex hull around the filtered points var indices = convexHull ( filtered ) ; // return the hull as array of points (rather than indices) var hull = [ ] ; for ( i = 0 ; i < indices . length ; i ++ ) hull . push ( filtered [ indices [ i ] ] ) ; return hull ; }
speed up convex hull by filtering out points inside quadrilateral formed by 4 extreme points
speed up convex hull by filtering out points inside quadrilateral formed by 4 extreme points