17.6 Convex Hull

Problem

Given a set of points, compute the smallest convex polygon that contains all of them.

This polygon is called the convex hull. You can think of it as the shape formed by stretching a rubber band around the outside of the point set and letting it snap tight.

Convex hulls appear in collision detection, pattern recognition, geographic analysis, robotics, image processing, computational geometry, and optimization. They are also a gateway algorithm: once you can build a hull, many other geometric problems become easier.

Solution

Use Andrew’s Monotonic Chain algorithm.

It is simple, fast, and robust for most practical purposes. The algorithm sorts the points, builds the lower hull, builds the upper hull, and joins them.

The main operation is the orientation test from Section 17.2.

Given three points:

A, B, C

if the turn from A -> B -> C is not counterclockwise, point B cannot remain on the convex hull.

def orientation(a, b, c):
    return (
        (b.x - a.x) * (c.y - a.y)
        -
        (b.y - a.y) * (c.x - a.x)
    )

A positive value means a left turn. A negative value means a right turn. Zero means the points are collinear.

Implementation

Assume a simple point type:

from dataclasses import dataclass

@dataclass(frozen=True, order=True)
class Point:
    x: int
    y: int

The order=True option lets Python sort points lexicographically by x, then by y.

Now implement the hull:

def convex_hull(points):
    points = sorted(set(points))

    if len(points) <= 1:
        return points

    lower = []

    for p in points:
        while len(lower) >= 2 and orientation(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    upper = []

    for p in reversed(points):
        while len(upper) >= 2 and orientation(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    return lower[:-1] + upper[:-1]

The result is the convex hull in counterclockwise order, without repeating the first point at the end.

Example

Input points:

(0,0)
(1,1)
(2,2)
(0,3)
(3,0)
(3,3)

The point (1,1) and (2,2) lie inside or on a diagonal boundary and do not define new corners of the hull.

The hull is:

(0,0)
(3,0)
(3,3)
(0,3)

A rough sketch:

(0,3) -------- (3,3)
  |              |
  |    *  *      |
  |              |
(0,0) -------- (3,0)

How the Lower Hull Works

After sorting, the algorithm scans from left to right.

For each new point, it checks the last two points already in the lower hull. If adding the new point creates a clockwise turn or a straight line, the middle point is removed.

while len(lower) >= 2 and orientation(lower[-2], lower[-1], p) <= 0:
    lower.pop()

This line is the heart of the algorithm.

It says: while the current chain bends the wrong way, delete the last point.

After enough deletions, the chain becomes convex again, and the new point can be appended safely.

How the Upper Hull Works

The upper hull is symmetric.

The algorithm scans the same sorted points in reverse order:

for p in reversed(points):
    ...

This constructs the top boundary of the hull.

The final hull combines:

lower boundary + upper boundary

The last point of each half is omitted to avoid duplicates:

return lower[:-1] + upper[:-1]

Handling Collinear Points

The condition:

orientation(lower[-2], lower[-1], p) <= 0

removes collinear points from the boundary.

This produces a minimal hull containing only corner vertices.

For example:

(0,0), (1,0), (2,0), (3,0)

becomes:

(0,0), (3,0)

If you want to keep all boundary points, change the condition to:

orientation(lower[-2], lower[-1], p) < 0

Now only right turns are removed, while collinear boundary points remain.

Correctness Argument

The sorted order guarantees that the lower hull is built from left to right. At every step, the lower list is a convex chain for the points processed so far.

When a new point creates a right turn, the previous endpoint cannot be part of the convex hull. It lies inside the triangle or below the valid boundary formed by neighboring points. Removing it restores the invariant.

The same argument applies to the upper hull in reverse order.

When both chains are joined, every input point lies on or inside the resulting polygon, and every retained vertex is necessary for the outer boundary.

Complexity Analysis

Sorting dominates the running time.

For n input points:

sorting: O(n log n)
scan:    O(n)
total:   O(n log n)

Each point is pushed and popped at most once from each chain, so the hull construction after sorting is linear.

Space usage is:

O(n)

for the sorted input and hull arrays.

Variants

Graham Scan also computes a convex hull in:

O(n log n)

It sorts points by polar angle around a pivot, then uses a stack to remove right turns.

Jarvis March, also called gift wrapping, runs in:

O(nh)

where h is the number of hull vertices. It can be useful when the hull is very small compared with the number of input points.

Andrew’s algorithm is usually the easiest to implement correctly because lexicographic sorting is simpler than angular sorting.

Common Pitfalls

Forgetting to remove duplicate points can produce repeated vertices and incorrect turns.

Using < 0 instead of <= 0 changes whether collinear boundary points are kept.

Returning lower + upper without dropping the final elements duplicates endpoints.

Using floating-point coordinates can make near-collinear points unstable. For integer coordinates, the orientation predicate is exact as long as intermediate products do not overflow.

Sorting by y before x changes the construction. The standard monotonic chain implementation sorts by x, then by y.

Discussion

The convex hull is a compact summary of a point set’s outer boundary. Many geometric algorithms become simpler after reducing a point set to its hull. Diameter, width, farthest-pair queries, collision approximations, and rotating-calipers techniques all use hulls as a starting point.

Andrew’s Monotonic Chain algorithm is a practical default. It uses one familiar primitive, the orientation test, and a small stack-like structure. The implementation is short, but the invariant is strong: each partial chain remains convex after every insertion.