Convex Hull

Shrink-wrap a contour in the smallest convex polygon that holds it. The gaps between wrap and shape reveal fingers, notches, and every concave secret.

The hull is the smallest convex polygon holding every point: six points give four hull vertices and two interior points

Why Does This Exist?

Moments weigh a shape but cannot see dents: a starfish and its shrink-wrapped blob share similar area yet differ exactly where the arms indent. Gesture interfaces need those indentations (fingertips are hull vertices, webbing between fingers is defects), and part inspection needs concavity as a 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. Fitted boxes and circles for the same simplification job are in bounding shapes.

Think of It Like This

A rubber band around pegs

Hammer pegs into a board in the shape's outline and snap a rubber band around all of them. The band touches only the outermost pegs and spans straight across every bay between headlands. Touched pegs are hull vertices, spanned bays are concavities, and the deepest water under each span measures the defect depth.

It stops holding for interiors. The band never learns about holes or inner walls, the same way the hull of a washer equals the hull of a solid disk. Interior detail needs contour hierarchy, never the hull.

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 in linearithmic time, keeping only left turns for a counterclockwise hull. Andrew's monotone chain runs in $O(n \log n)$ dominated by the sort.

Trace six points: $(0,0)$ , $(2,1)$ , $(4,0)$ , $(1,3)$ , $(3,3)$ , $(2,0.5)$ . The band touches $(0,0)$ , $(4,0)$ , $(3,3)$ , $(1,3)$ and spans over $(2,1)$ and $(2,0.5)$ , which sit strictly inside (both fall left of every directed hull edge, the interior side). Four hull vertices, two interior points, and the signed-area check 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 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

Hull spikes from unfiltered speckle

Symptom: one stray bright pixel becomes a hull vertex and invents a huge defect across the real shape. The hull is maximally sensitive to outliers by construction. Approximate the contour and drop specks with a morphological open before hulling, and distrust defects whose start or end sits on an isolated vertex.

Thresholding absolute defect depths

Symptom: a fixed depth cutoff counts fingers on adult hands but misses children's, because depth scales with hand size in pixels. Defect depth is an absolute pixel distance. Normalize by the hull edge length or the hand's bounding size before comparing, and calibrate the cutoff per camera distance.

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.