es6-convex-hull.js

gistfile1.txt

// code by https://www.nayuki.io/res/convex-hull-algorithm/convex-hull.js
// Returns a new array of points representing the convex hull of
// the given set of points. The convex hull excludes collinear points.
// This algorithm runs in O(n log n) time.
// eslint-disable-next-line import/prefer-default-export
export const makeHull = (points) => {
    const newPoints = points.slice();
    newPoints.sort(comparePoints);
    return makeHullPresorted(newPoints);
};

// Returns the convex hull, assuming that each points[i] <= points[i + 1]. Runs in O(n) time.
const makeHullPresorted = (points) => {
    if (points.length <= 1) {
        return points.slice();
    }

    // Andrew's monotone chain algorithm. Positive y coordinates correspond to "up"
    // as per the mathematical convention, instead of "down" as per the computer
    // graphics convention. This doesn't affect the correctness of the result.

    const upperHull = [];
    for (let i = 0; i < points.length; i++) {
        const p = points[i];
        while (upperHull.length >= 2) {
            const q = upperHull[upperHull.length - 1];
            const r = upperHull[upperHull.length - 2];
            if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x)) {
                upperHull.pop();
            } else {
                break;
            }
        }
        upperHull.push(p);
    }
    upperHull.pop();

    const lowerHull = [];
    for (let i = points.length - 1; i >= 0; i--) {
        const p = points[i];
        while (lowerHull.length >= 2) {
            const q = lowerHull[lowerHull.length - 1];
            const r = lowerHull[lowerHull.length - 2];
            if ((q.x - r.x) * (p.y - r.y) >= (q.y - r.y) * (p.x - r.x)) {
                lowerHull.pop();
            } else {
                break;
            }
        }
        lowerHull.push(p);
    }
    lowerHull.pop();

    if (
        upperHull.length === 1
        && lowerHull.length === 1
        && upperHull[0].x === lowerHull[0].x
        && upperHull[0].y === lowerHull[0].y
    ) {
        return upperHull;
    }

    return upperHull.concat(lowerHull);
};

const comparePoints = (a, b) => {
    if (a.x < b.x) {
        return -1;
    }
    if (a.x > b.x) {
        return +1;
    }
    if (a.y < b.y) {
        return -1;
    }
    if (a.y > b.y) {
        return +1;
    }
    return 0;
};