Convex Hull

// Cross product of vectors OA and OB
function cross(O, A, B) {
    return (A[0] - O[0]) * (B[1] - O[1]) - (A[1] - O[1]) * (B[0] - O[0]);
}

// Returns convex hull in counter-clockwise order
// Include collinear: use cross(...) < 0, Exclude: use cross(...) <= 0
function convexHull(points) {
    points.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]);
    const n = points.length;
    if (n < 3) return points;

    const hull = [];
    // Build lower hull
    for (const p of points) {
        while (hull.length >= 2 && cross(hull.at(-2), hull.at(-1), p) <= 0) hull.pop();
        hull.push(p);
    }
    // Build upper hull
    const lower = hull.length + 1;
    for (let i = n - 1; i >= 0; i--) {
        while (hull.length >= lower && cross(hull.at(-2), hull.at(-1), points[i]) <= 0) hull.pop();
        hull.push(points[i]);
    }
    hull.pop(); // Remove last point (same as first)
    return hull;
}

// Area of convex hull using shoelace formula
function polygonArea(hull) {
    let area = 0;
    for (let i = 0; i < hull.length; i++) {
        const [x1, y1] = hull[i];
        const [x2, y2] = hull[(i + 1) % hull.length];
        area += x1 * y2 - x2 * y1;
    }
    return Math.abs(area) / 2;
}