Pattern Guide
Convex Hull
"Smallest convex polygon enclosing all points. Graham scan O(n log n). Andrew's monotone chain."
A convex hull is the smallest convex polygon containing all given points. Two O(n log n) algorithms: Graham scan (sort by polar angle, stack-based) and Andrew's monotone chain (sort by x then y, build upper and lower hulls). Applications: largest triangle/polygon area, farthest pair of points, computational geometry queries, convex hull trick for DP.
Problems you can solve with this pattern
4 problems · click any to start solving
// 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;
}Andrew's monotone chain: sort points by x (tie-break by y). Build lower hull left to right: maintain a stack where each new point makes a left turn — if it would make a right turn (or be collinear), pop the stack. Build upper hull right to left same way. Concatenate. Cross product of vectors AB and AC: (B-A) × (C-A) > 0 means left turn, < 0 means right turn, = 0 means collinear.
// 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;
}- cross(O, A, B) = (A-O) × (B-O)
- Positive: left turn (counter-clockwise)
- Negative: right turn (clockwise)
- Zero: collinear
Convex hull algorithms:
- Andrew's monotone chain: sort + two-pass O(n log n), simplest to code
- Graham scan: sort by polar angle, O(n log n)
- Jarvis march (gift wrapping): O(nh) where h = hull size — good when h << n
Key property: Largest triangle must have all 3 vertices on convex hull. Rotating calipers finds it in O(h²) after O(n log n) hull computation.