Convex Hull — Collinear Points That Break Hull Detection

Convex hull is the gateway algorithm to computational geometry. It appears in collision detection (is object A inside the convex hull of object B?), pathfinding (compute the hull to find the shortest path around an obstacle), computer vision (shape descriptors), and machine learning (support vector machine margin computation).

Graham scan and Jarvis march solve the same problem with different trade-offs. Graham scan is O(n log n) regardless of hull size — optimal for large point clouds. Jarvis march is O(nh) where h is the hull output size — better when the hull has very few points (h << log n). Knowing this trade-off and when it matters is what distinguishes thorough geometry knowledge.

Why Convex Hull Algorithms Fail on Collinear Points

A convex hull is the smallest convex polygon that encloses a set of points in the plane. The core mechanic: given n points, the hull is the subset that forms the boundary of the convex set — every interior point is a convex combination of hull vertices. The problem is that collinear points (three or more points lying on the same edge) break the strict orientation test most algorithms rely on.

Most hull algorithms — Graham scan, Andrew's monotone chain — use cross-product orientation checks to decide whether a turn is left, right, or collinear. When points are collinear, the cross product is zero. Naive implementations treat zero as either left or right, causing vertices to be incorrectly included or excluded. The result: a hull that is either non-convex, missing boundary points, or includes redundant interior points. The fix is a consistent tie-breaking rule: either include all collinear boundary points (maximal hull) or exclude all but the endpoints (minimal hull).

Use convex hull when you need to compute the outer boundary of a point cloud — collision detection, shape analysis, or geographic clustering. In production, the cost of mishandling collinear points is silent corruption: a hull that looks correct but fails geometric predicates downstream. Always specify your collinear policy explicitly in the comparator.

The Cross Product — Detecting Left Turns

The foundation of both algorithms is the 2D cross product. For three points p1, p2, p3: cross = (p2.x-p1.x)(p3.y-p1.y) - (p2.y-p1.y)(p3.x-p1.x)

• cross > 0: left turn (counterclockwise) ✓ keep
• cross < 0: right turn (clockwise) ✗ remove
• cross = 0: collinear

def cross(O, A, B):
    """Cross product of vectors OA and OB.
    > 0: CCW (left turn), < 0: CW (right turn), = 0: collinear
    """
    return (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0])

print(cross((0,0),(1,0),(0,1)))   # 1 → left turn
print(cross((0,0),(0,1),(1,0)))   # -1 → right turn
print(cross((0,0),(1,1),(2,2)))   # 0 → collinear

Graham Scan — O(n log n)

1. Find the lowest point (by y, then x) as the pivot
2. Sort all other points by polar angle from pivot
3. Process points: maintain a stack — pop whenever the top three points make a right turn

from functools import cmp_to_key

def graham_scan(points: list[tuple]) -> list[tuple]:
    points = list(set(points))
    if len(points) < 3: return points
    # Find bottom-left pivot
    pivot = min(points, key=lambda p: (p[1], p[0]))
    def compare(a, b):
        c = cross(pivot, a, b)
        if c != 0: return -1 if c > 0 else 1
        # Collinear: closer point first
        da = (a[0]-pivot[0])**2 + (a[1]-pivot[1])**2
        db = (b[0]-pivot[0])**2 + (b[1]-pivot[1])**2
        return -1 if da < db else 1
    pts = sorted([p for p in points if p != pivot], key=cmp_to_key(compare))
    pts = [pivot] + pts
    # Graham scan
    hull = []
    for p in pts:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

pts = [(0,0),(1,1),(2,2),(0,2),(2,0),(1,3),(3,1)]
print(graham_scan(pts))

Jarvis March (Gift Wrapping) — O(nh)

Start from the leftmost point. Repeatedly pick the point that is most counterclockwise from the current point. Stop when we return to the start.

def jarvis_march(points: list[tuple]) -> list[tuple]:
    n = len(points)
    if n < 3: return points
    # Start from leftmost point
    start = min(range(n), key=lambda i: points[i])
    hull = []
    current = start
    while True:
        hull.append(points[current])
        next_pt = (current + 1) % n
        for i in range(n):
            if cross(points[current], points[next_pt], points[i]) > 0:
                next_pt = i
        current = next_pt
        if current == start:
            break
    return hull

pts = [(0,0),(1,1),(2,2),(0,2),(2,0),(1,3),(3,1)]
print(jarvis_march(pts))

Collinear Points and Edge Cases

Both algorithms must explicitly handle points that lie exactly on the convex hull edge (collinear with two hull vertices). Common strategies: - Include all collinear hull edge points: results in more vertices but strictly convex shape. - Include only the extreme (farthest) collinear points: prunes interior colinear points, makes hull minimal.

In Graham scan, during sorting, if two points have the same angle from pivot, the closer one should come first. During the stack sweep, collinear points (cross == 0) are usually popped (<= 0 condition) to ensure minimal hull. To include them, change condition to < 0 and handle collinear separately.

In Jarvis March, when multiple candidates have the same cross product sign (collinear), pick the farthest one from the current point to stay on the hull edge.

def graham_scan_include_collinear(points):
    # same as before but using cross(p) < 0 to pop only right turns
    # collinear points are kept on stack
    pivot = min(points, key=lambda p: (p[1], p[0]))
    # ... (sort same)
    hull = []
    for p in pts:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) < 0:
            hull.pop()
        hull.append(p)
    return hull

# For Jarvis March, pick farthest when collinear:
def jarvis_march_collinear(points):
    # ...same start
    while True:
        hull.append(points[current])
        next_pt = (current + 1) % n
        for i in range(n):
            c = cross(points[current], points[next_pt], points[i])
            if c > 0 or (c == 0 and distance(points[current], points[i]) > distance(points[current], points[next_pt])):
                next_pt = i
        current = next_pt
        if current == start: break
    return hull

def distance(a,b): return (a[0]-b[0])**2+(a[1]-b[1])**2

Floating-Point Precision and Robustness

Cross product computations involve subtraction and multiplication of coordinates. With floating-point numbers (float/double), tiny rounding errors can produce a cross product like 2e-16 instead of exactly 0. This can flip the sign and break turn detection.

Jarvis March can also suffer from degenerate cases where all points are collinear — the cross product will be 0 for every triple, resulting in an infinite loop or incorrect hull (no vertices). Guard against this by checking number of distinct points and returning them all if collinear.

EPS = 1e-9

def orient(p, q, r):
    """Return 1 (CCW), -1 (CW), 0 (collinear) using epsilon."""
    val = (q[0]-p[0])*(r[1]-p[1]) - (q[1]-p[1])*(r[0]-p[0])
    if val > EPS: return 1
    if val < -EPS: return -1
    return 0

def graham_scan_robust(points):
    points = list(set(points))
    if len(points) < 3: return points
    # If all points collinear, return the extreme points
    all_collinear = all(orient(points[0], points[1], p) == 0 for p in points[2:])
    if all_collinear:
        xs = [p[0] for p in points]
        min_x = min(points, key=lambda p: p[0])
        max_x = max(points, key=lambda p: p[0])
        return [min_x, max_x] if min_x != max_x else [min_x]
    # rest of Graham scan using orient()
    ...

When to Pick Each Algorithm in Production

Graham Scan (O(n log n)): - Default choice for general 2D convex hull. - Sorting is stable and fast for n up to 10^6. - Needs O(n) extra space for stack. - Preferred in most libraries (shapely, CGAL).

Jarvis March (O(nh)): - When hull size is expected to be tiny (e.g., dynamic points with known hull of ~10). - Simpler to implement from scratch. - Can be competitive for interactive applications with few hull points per frame.

Hybrid approach: Some libraries start with a quick O(n) test (e.g., find min/max x/y) and if points are mostly collinear, switch to Jarvis. In practice, monte carlo suggests that for random points h ≈ O(log n), making Jarvis ~O(n log n) anyway, so Graham is almost always better.

Monotone Chain — The Algorithm You Actually Use in Production

Graham Scan is fine for textbooks. Monotone Chain (Andrew's algorithm) is what you ship. It sorts once, builds the hull in two passes — lower hull then upper — and handles collinear points without the headache of polar angle sorting.

The trick: sort points by x then y. Walk the list left to right building the lower hull. For each new point, pop off the stack until the last two points and the new one make a left turn. Then build the upper hull right to left. Merge the two, removing duplicates at the start and end.

Why this matters in production: you don't need to compute a single atan2. No floating-point angle comparisons. Just cross products. That alone kills 90% of your floating-point bugs. And it's O(n log n) in the worst case — no surprises when input hits 10 million points.

The merge step feels like glue code. Don't skip testing it. I've seen production hulls that looked like a pretzel because someone forgot to strip the duplicated endpoints. Trust the algorithm, verify the output.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class MonotoneChainHull {
    record Point(long x, long y) implements Comparable<Point> {
        public int compareTo(Point other) {
            int cmp = Long.compare(this.x, other.x);
            return cmp != 0 ? cmp : Long.compare(this.y, other.y);
        }
    }

    private static long cross(Point o, Point a, Point b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
    }

    public static List<Point> convexHull(List<Point> points) {
        List<Point> sorted = new ArrayList<>(new HashSet<>(points));
        Collections.sort(sorted);
        if (sorted.size() < 3) return sorted;

        List<Point> lower = new ArrayList<>();
        for (Point p : sorted) {
            while (lower.size() >= 2 && cross(lower.get(lower.size()-2), lower.get(lower.size()-1), p) <= 0)
                lower.remove(lower.size()-1);
            lower.add(p);
        }

        List<Point> upper = new ArrayList<>();
        for (int i = sorted.size()-1; i >= 0; i--) {
            Point p = sorted.get(i);
            while (upper.size() >= 2 && cross(upper.get(upper.size()-2), upper.get(upper.size()-1), p) <= 0)
                upper.remove(upper.size()-1);
            upper.add(p);
        }

        lower.remove(lower.size()-1);
        upper.remove(upper.size()-1);
        lower.addAll(upper);
        return lower;
    }

    public static void main(String[] args) {
        var points = List.of(
            new Point(0, 0), new Point(0, 4), new Point(-4, 0),
            new Point(5, 0), new Point(0, -6), new Point(1, 0)
        );
        System.out.println(convexHull(points));
    }
}

Quickhull — When You Need Speed Over Simplicity

Quickhull is the convex hull equivalent of Quicksort — average-case O(n log n), worst-case O(n²). The idea: find the leftmost and rightmost points, split the set into two halves, and recursively find the point farthest from the line. That farthest point becomes a hull vertex, and you recurse on the subsets.

The beauty? It avoids a global sort. If your points are already spatially clustered, Quickhull can outrun Monotone Chain by a significant margin. The downside: you need a robust distance-to-line calculation, and the recursion depth can blow the stack on adversarial input — think points on a circle.

In production, I've only pulled Quickhull when my data was streaming and I couldn't afford an O(n log n) sort before starting. The algorithm processes points incrementally, which makes it ideal for real-time systems where you get one point at a time and need an approximate hull immediately.

Don't use this for random point clouds in a batch job. Use it when you have spatial locality and you're memory-constrained. And always fall back to Monotone Chain if recursion depth exceeds a threshold — your senior engineer will thank you.

// io.thecodeforge — dsa tutorial

import java.util.*;
import java.awt.geom.Point2D;

public class QuickhullRecursive {
    public static Set<Point2D> hull = new HashSet<>();

    public static void quickHull(List<Point2D> points) {
        if (points.size() < 3) { hull.addAll(points); return; }
        Point2D min = points.get(0), max = points.get(0);
        for (Point2D p : points) {
            if (p.getX() < min.getX()) min = p;
            if (p.getX() > max.getX()) max = p;
        }
        hull.add(min);
        hull.add(max);
        List<Point2D> left = new ArrayList<>(), right = new ArrayList<>();
        for (Point2D p : points) {
            double side = cross(min, max, p);
            if (side < 0) left.add(p);
            else if (side > 0) right.add(p);
        }
        buildHull(min, max, left);
        buildHull(max, min, right);
    }

    private static void buildHull(Point2D a, Point2D b, List<Point2D> points) {
        if (points.isEmpty()) return;
        int idx = 0;
        double maxDist = 0;
        for (int i = 0; i < points.size(); i++) {
            double dist = Math.abs(cross(a, b, points.get(i)));
            if (dist > maxDist) { maxDist = dist; idx = i; }
        }
        Point2D far = points.get(idx);
        hull.add(far);
        List<Point2D> left = new ArrayList<>(), right = new ArrayList<>();
        for (Point2D p : points) {
            if (cross(a, far, p) > 0) left.add(p);
            else if (cross(far, b, p) > 0) right.add(p);
        }
        buildHull(a, far, left);
        buildHull(far, b, right);
    }

    private static double cross(Point2D o, Point2D a, Point2D b) {
        return (a.getX()-o.getX())*(b.getY()-o.getY()) - (a.getY()-o.getY())*(b.getX()-o.getX());
    }
}

Visualizing Convex Hulls — Why Your Debugger Is a Liar

You cannot debug convex hull algorithms by staring at coordinates. The human brain fails at spatial reasoning past three points. You need visualization, and not the half-baked console logging you're about to write.

Every production hull system I've built ships with a debug visualizer. On failure, I plot the point set, the hull edges, and the current candidate. A single frame shows you what 50 log statements won't: the exact false left turn, the collinear point that slipped through, the numeric precision error that made a point jump a millimeter.

The cheap approach: dump to SVG. No dependencies, text format, Git-diffable. The pro approach: overlay multiple algorithmic steps in different colors. When Jarvis March wraps clockwise instead of counterclockwise, you'll see the helix instantly. Don't guess. Render.

// io.thecodeforge — dsa tutorial

import java.util.List;
import java.util.stream.Collectors;

record Point(double x, double y) {}

public class HullDebugSVG {
    public static String toSvg(List<Point> hull, List<Point> all) {
        var sb = new StringBuilder();
        sb.append("<svg viewBox='0 0 100 100' xmlns='http://www.w3.org/2000/svg'>");
        for (var p : all)
            sb.append(String.format(
                "<circle cx='%.2f' cy='%.2f' r='1' fill='#ccc'/>", p.x(), p.y()));
        if (hull.size() > 1) {
            sb.append("<polygon points='");
            sb.append(hull.stream()
                .map(p -> String.format("%.2f,%.2f", p.x(), p.y()))
                .collect(Collectors.joining(" ")));
            sb.append("' fill='none' stroke='#d00' stroke-width='0.5'/>");
        }
        sb.append("</svg>");
        return sb.toString();
    }
}

Visualizing Performance — Why O(n log n) Means Nothing at 100 Points

Stop optimizing algorithms for hypothetical input sizes. Graham Scan is O(n log n). Great. For 100 points, the constant factors from sorting overhead and cross-product calls dominate. You need to visualize runtime as a function of input distribution, not just n.

Plot runtime vs input size for random, grid, and pathological point sets. You'll see Quickhull smoke Graham Scan on random sets under 10,000 points because its divide-and-conquer hits early. Monotone Chain's sorting cost is identical to Graham's, but the second pass is a linear sweep — visible as a flat line on your plot when the first pass dominates.

I keep a benchmark harness that outputs CSV. One gnuplot command later, I see the crossover where one algorithm dies. Don't trust big-O alone. Plot your algorithms against production-like data. The graph is your real complexity analysis.

// io.thecodeforge — dsa tutorial

import java.util.*;
import java.util.stream.IntStream;

public class BenchmarkCsv {
    static Random rng = new Random(42);

    static List<Point> randomPoints(int n) {
        return IntStream.range(0, n)
            .mapToObj(i -> new Point(rng.nextDouble()*100, rng.nextDouble()*100))
            .toList();
    }

    public static void main(String[] args) {
        for (int n : new int[]{10, 100, 1000, 10000}) {
            var pts = randomPoints(n);
            long start = System.nanoTime();
            var hull = GrahamScan.run(pts); // dummy reference
            long end = System.nanoTime();
            System.out.printf("%d,%.3f%n", n, (end-start)/1e6);
        }
    }
}