Convex layers algorithm

js

function cross(o, a, b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }

function sortPoint(points) {
    points.sort(function(a, b) {
        return a.x == b.x ? a.y - b.y : a.x - b.x;
    });
}

function convexHull(points, animation, animationConvex) {
    var lower = [], upper = [];
    for (var i = 0; i < points.length; i++) {
        while (lower.length >= 2 && cross(lower[lower.length - 2], lower[lower.length - 1], points[i]) < 0) {
            lower.pop();
        }
        lower.push(points[i]);
    }

    for (var i = points.length - 1; i >= 0; i--) {
        while (upper.length >= 2 && cross(upper[upper.length - 2], upper[upper.length - 1], points[i]) < 0) {
            upper.pop();
        }
        upper.push(points[i]);
    }
    
    upper.pop();
    lower.pop();
    var convex = lower.concat(upper), remove = [], newPoints = [];

    for (var i = points.length - 1, j = 0; i >= 0; i--) {
        if (points[i] == upper[j]) {
            remove[i] = true;
            j++;
        } else {
            remove[i] = false;
        }
    }
    for (var i = 0, j = 0; i < points.length; i++) {
        if (points[i] == lower[j]) {
            remove[i] = true;
            j++;
        }
    }
    for (var i = 0; i < points.length; i++)
        if (!remove[i])
            newPoints.push(points[i]);            
    return [convex, newPoints];
}