Convex Hull

Why Does This Exist?

Area and moments weigh a shape but cannot see dents: a starfish and its shrink-wrapped blob have similar area yet differ exactly where the arms indent. Gesture interfaces need those indentations — fingertips are hull vertices, the webbing between fingers is gaps — and part inspection needs concavity as a measurable feature. The convex hull supplies both by separating what bulges out from what caves in.

This page covers the hull definition, the linearithmic construction, and convexity defects. Contour detection finds the outlines the hull then shrink-wraps.

The one idea you need first

A set is convex when the straight segment between any two of its points stays inside the set. A circle is convex; a crescent is not, because a segment across its bay leaves the shape. The hull is the smallest convex set that still contains every point you started with.

Think of It Like This

How It Actually Works

The smallest convex container

The convex hull of a point set is the smallest convex polygon containing every point: any segment between two hull points stays inside. Construction sorts points by $x$ (then $y$) and builds upper and lower chains, keeping only left turns for a counterclockwise hull. Sorting dominates, so Andrew's monotone chain runs in $O(n \log n)$ time.

Worked example

Trace six points: $(0,0)$, $(2,1)$, $(4,0)$, $(1,3)$, $(3,3)$, $(2,0.5)$. Sorted by $x$ they run $(0,0)$, $(1,3)$, $(2,0.5)$, $(2,1)$, $(3,3)$, $(4,0)$. Walking the lower chain, each right turn or straight step discards the middle point: $(1,3)$ is discarded when $(2,0.5)$ arrives, since the turn at $(1,3)$ heads back down. The band ends up touching $(0,0)$, $(4,0)$, $(3,3)$, $(1,3)$ and spanning over $(2,1)$ and $(2,0.5)$, which sit strictly inside. Four hull vertices, two interior points, and the signed area $9$ (positive) confirms counterclockwise order.

Defects, solidity, and fingers

Each hull edge plus the contour stretch beneath it defines one convexity defect: start point, end point, farthest contour point, and depth to the edge. OpenCV returns depths in fixed-point units, so scale before thresholding. Solidity — contour area over hull area — compresses the same story to one number: near $1$ for blobs, well below for stars. A raised hand shows five hull vertices at the fingertips with four deep defects between them, which is the entire gesture feature in eight numbers.

Code

Monotone-chain hull on the fixture points:

1pts = [(0, 0), (2, 1), (4, 0), (1, 3), (3, 3), (2, 0.5)]2
3def cross(o, a, b):4    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])5
6pts = sorted(set(pts))7lower, upper = [], []8for p in pts:9    while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:10        lower.pop()11    lower.append(p)12for p in reversed(pts):13    while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:14        upper.pop()15    upper.append(p)16
17hull = lower[:-1] + upper[:-1]18print(f"hull {hull}")19# -> hull [(0, 0), (4, 0), (3, 3), (1, 3)]

Four vertices, counterclockwise, with $(2,1)$ and $(2,0.5)$ correctly excluded as interior.

Watch Out For

The Quick Version

• The convex hull is the smallest convex polygon holding every contour point, built in $O(n \log n)$.
• Hull vertices mark protrusions; convexity defects measure each concavity's depth and span.
• Solidity (contour area over hull area) compresses convexity into one sortable number.
• Five fingertips plus four defects encode an open-hand gesture with no learning at all.
• Hulls ignore holes and interiors, and one outlier pixel can invent a giant false defect.

What to Read Next

• Contour Detection
• 3D Object Detection