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.

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.

Frequently Asked Questions