Convex Hull: Graham Scan and Jarvis March
Imagine stretching a rubber band around a set of nails hammered into a board. When you release it, the band snaps to the outermost nails, forming the tightest possible enclosure. That shape is the...
Key Insights
- Graham Scan runs in O(n log n) time regardless of output size, making it ideal when you expect many points on the hull, while Jarvis March’s O(nh) complexity excels when the hull contains few vertices relative to the input size.
- Both algorithms rely on the same fundamental operation—computing the cross product to determine point orientation—so mastering this single function unlocks both implementations.
- Floating-point precision and collinear points are the two most common sources of bugs in convex hull implementations; handling them explicitly prevents subtle failures in production.
Introduction to Convex Hulls
Imagine stretching a rubber band around a set of nails hammered into a board. When you release it, the band snaps to the outermost nails, forming the tightest possible enclosure. That shape is the convex hull—the smallest convex polygon containing all points in a set.
Convex hulls appear everywhere in software engineering. Game engines use them for simplified collision detection. Image processing pipelines compute them to find object boundaries. Geographic information systems rely on them for spatial queries and clustering. Understanding how to compute them efficiently is fundamental knowledge for any engineer working with geometric data.
The problem statement is deceptively simple: given n points in a 2D plane, find the vertices of the smallest convex polygon that contains all points, listed in counterclockwise order. Two classic algorithms solve this problem with different trade-offs: Graham Scan and Jarvis March.
Foundational Concepts
Before diving into algorithms, you need to understand orientation testing. Given three points P, Q, and R, we need to determine whether the path P → Q → R turns left (counterclockwise), turns right (clockwise), or continues straight (collinear).
The cross product of vectors (Q - P) and (R - Q) gives us this information directly. A positive result means counterclockwise, negative means clockwise, and zero means collinear.
def cross_product(o, a, b):
"""Calculate cross product of vectors OA and OB."""
return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
def orientation(p, q, r):
"""
Determine orientation of triplet (p, q, r).
Returns:
1 -> Counterclockwise (left turn)
-1 -> Clockwise (right turn)
0 -> Collinear
"""
val = cross_product(p, q, r)
if val > 0:
return 1 # Counterclockwise
elif val < 0:
return -1 # Clockwise
return 0 # Collinear
This function is the building block for both algorithms. Every decision about whether to include a point on the hull reduces to an orientation test.
Graham Scan Algorithm
Graham Scan takes a sorting-first approach. The algorithm selects a starting point (typically the lowest, then leftmost point), sorts all other points by polar angle relative to this anchor, then processes points in order while maintaining a stack of hull candidates.
The key insight is that as we process points in sorted angular order, we can detect and remove points that would create a right turn (concave angle) in the hull. If adding a new point creates a right turn with the last two points on the stack, we pop the middle point and check again.
Here’s the complete implementation:
import math
def graham_scan(points):
"""
Compute convex hull using Graham Scan algorithm.
Returns hull vertices in counterclockwise order.
Time complexity: O(n log n)
"""
if len(points) < 3:
return points[:]
# Find the bottom-most point (or left-most in case of tie)
start = min(points, key=lambda p: (p[1], p[0]))
def polar_angle(p):
"""Calculate polar angle from start point."""
if p == start:
return -math.inf # Ensure start comes first
return math.atan2(p[1] - start[1], p[0] - start[0])
def distance_sq(p):
"""Squared distance from start point."""
return (p[0] - start[0])**2 + (p[1] - start[1])**2
# Sort by polar angle, then by distance for collinear points
sorted_points = sorted(points, key=lambda p: (polar_angle(p), distance_sq(p)))
# Build the hull using a stack
hull = []
for p in sorted_points:
# Remove points that make clockwise turn
while len(hull) >= 2 and cross_product(hull[-2], hull[-1], p) <= 0:
hull.pop()
hull.append(p)
return hull
The algorithm runs in O(n log n) time, dominated by the sorting step. The stack processing is linear because each point is pushed and popped at most once.
Jarvis March (Gift Wrapping) Algorithm
Jarvis March takes an output-sensitive approach. Instead of processing all points upfront, it builds the hull incrementally by “wrapping” around the point set. Starting from the leftmost point (guaranteed to be on the hull), the algorithm repeatedly finds the point that makes the smallest counterclockwise angle with the current edge.
Think of it as standing at a hull vertex and rotating a line until it hits the next point. That point becomes the next hull vertex, and you repeat until returning to the start.
def jarvis_march(points):
"""
Compute convex hull using Jarvis March (Gift Wrapping) algorithm.
Returns hull vertices in counterclockwise order.
Time complexity: O(nh) where h is the number of hull vertices
"""
if len(points) < 3:
return points[:]
# Start from the leftmost point
start = min(points, key=lambda p: (p[0], p[1]))
hull = []
current = start
while True:
hull.append(current)
# Find the most counterclockwise point from current
next_point = points[0]
for candidate in points[1:]:
if candidate == current:
continue
# Check if candidate is more counterclockwise than next_point
orient = cross_product(current, next_point, candidate)
if next_point == current or orient > 0:
# candidate is more counterclockwise
next_point = candidate
elif orient == 0:
# Collinear: pick the farther point
dist_next = (next_point[0] - current[0])**2 + (next_point[1] - current[1])**2
dist_cand = (candidate[0] - current[0])**2 + (candidate[1] - current[1])**2
if dist_cand > dist_next:
next_point = candidate
current = next_point
# Check if we've completed the hull
if current == start:
break
return hull
The time complexity is O(nh) where h is the number of hull vertices. For each of the h hull vertices, we scan all n points to find the next one. This makes Jarvis March excellent when h is small (like O(log n)) but poor when most points lie on the hull.
Algorithm Comparison
The choice between these algorithms depends on your data characteristics:
import random
import time
def benchmark_algorithms(n_points, distribution='random'):
"""Compare algorithm performance on different distributions."""
if distribution == 'random':
# Points uniformly distributed - hull typically has O(log n) points
points = [(random.uniform(0, 1000), random.uniform(0, 1000))
for _ in range(n_points)]
elif distribution == 'circle':
# Points on a circle - all points on hull (worst case for Jarvis)
import math
points = [(500 + 400 * math.cos(2 * math.pi * i / n_points),
500 + 400 * math.sin(2 * math.pi * i / n_points))
for i in range(n_points)]
elif distribution == 'clustered':
# Tight cluster with few outliers - small hull
points = [(500 + random.gauss(0, 10), 500 + random.gauss(0, 10))
for _ in range(n_points - 4)]
# Add corner outliers
points.extend([(0, 0), (1000, 0), (0, 1000), (1000, 1000)])
# Benchmark Graham Scan
start = time.perf_counter()
hull_graham = graham_scan(points)
graham_time = time.perf_counter() - start
# Benchmark Jarvis March
start = time.perf_counter()
hull_jarvis = jarvis_march(points)
jarvis_time = time.perf_counter() - start
return {
'n_points': n_points,
'hull_size': len(hull_graham),
'graham_ms': graham_time * 1000,
'jarvis_ms': jarvis_time * 1000,
'winner': 'Graham' if graham_time < jarvis_time else 'Jarvis'
}
With random uniform distributions, the expected hull size is O(log n), making Jarvis March competitive for small to medium inputs. With points arranged on a circle, Jarvis March degrades to O(n²) while Graham Scan maintains O(n log n). For clustered data with few outliers, Jarvis March often wins dramatically.
Edge Cases and Implementation Pitfalls
Production code must handle edge cases that textbook implementations ignore. Floating-point precision causes the most insidious bugs—two points that appear distinct might compare as equal, or orientation tests might give inconsistent results.
EPSILON = 1e-10
def robust_cross_product(o, a, b):
"""Cross product with floating-point tolerance."""
val = (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
if abs(val) < EPSILON:
return 0
return val
def robust_orientation(p, q, r):
"""Orientation test with epsilon comparison."""
val = robust_cross_product(p, q, r)
if val > EPSILON:
return 1
elif val < -EPSILON:
return -1
return 0
def preprocess_points(points):
"""Remove duplicates and handle degenerate cases."""
# Remove exact duplicates
unique = list(set(points))
if len(unique) < 3:
return unique # Degenerate case: line or point
# Check if all points are collinear
p0, p1 = unique[0], unique[1]
all_collinear = all(
robust_orientation(p0, p1, p) == 0
for p in unique[2:]
)
if all_collinear:
# Return endpoints of the line segment
by_x = sorted(unique, key=lambda p: (p[0], p[1]))
return [by_x[0], by_x[-1]]
return unique
Collinear points require explicit handling. When multiple points lie on a hull edge, you must decide whether to include all of them or just the endpoints. Most applications want only endpoints, but some (like computing the hull perimeter with all vertices) need every collinear point.
Conclusion
Graham Scan and Jarvis March represent two fundamental approaches to the convex hull problem. Graham Scan’s O(n log n) guarantee makes it the safe default choice—it never degrades regardless of input structure. Jarvis March shines when you know the hull will be small relative to the input, offering better constants and simpler implementation.
For production systems, consider Chan’s algorithm, which achieves O(n log h) time by combining both approaches—the best of both worlds. Quickhull offers another practical alternative with excellent average-case performance and easy parallelization.
Whichever algorithm you choose, remember that the orientation test is your foundation. Get that right, handle your edge cases explicitly, and the rest follows naturally.