01 / The idea
The boundary has to contain every point, without bending inward.
Our park has six outside points and four measurements inside. The fence should pass through the outside points, never cut across the park’s interior, and remain convex so every turn faces the same way.
The convex hull is the outer envelope of a point set. It is useful for collision broad phases, map footprints, pointer regions, and the first approximation before a more detailed geometric test.
Keep the fence. Ignore the points inside it.
Sort by x, then y. The leftmost point is where the outside walk begins. Order so far: bridge.
Put points in order
Sort by x, then y. The leftmost point is where the outside walk begins. Order so far: bridge.
Reduced motion: choose a scene to see its completed state.
Read this scene
Sort by x, then y. The leftmost point is where the outside walk begins. Order so far: bridge.
Sort by x, then y. The leftmost point is where the outside walk begins. Order so far: bridge.
Watch and Step through replay the lower and upper scans. Try it recomputes the hull when you remove or restore survey points.
The monotonic chain keeps bridge, gate, lake, ridge, north, and grove. Pond, lookout, meadow, and camp are still inside the boundary; they matter to the survey, but not to its convex envelope.
02 / Name the rule
Keep a left turn. Pop the point behind a right turn.
Sort the points from left to right. For the lower walk, append the next point and inspect the last three. If the cross product is zero or negative, the middle point is not a strict counter-clockwise corner of the lower boundary, so remove it and check again. Do the same from right to left for the upper walk.
Left to right
Sorting turns a two-dimensional boundary into two one-dimensional scans.
Read three points
The cross product says whether the newest segment turns left, right, or stays straight.
Remove the inward corner
A point popped from the stack cannot return to this walk’s outside boundary.
We use a strict hull: points that lie exactly on a straight edge between two corners are excluded. If an application needs every boundary measurement, change the collinearity policy; that is a product choice, not a different cross product.
Why does a popped point stay out?The sorted order gives it nowhere useful to return
For the current walk, the two points around the popped point already form a boundary segment that turns more safely toward the outside. Every later point is farther right for the lower scan, so the popped point cannot become a corner again without violating the same turn rule. The upper scan makes the corresponding argument from the other side.
03 / Read the shape
Two stacks and one turn test.
Basic form validates and sorts the points, then builds both walks. In the wild keeps a copy of the stack after every point: the trace the film above replays. At the call site prints the park’s retained boundary.
Validate the points, sort them by x then y, and build the lower and upper monotonic chains with the cross-product pop test.
export const MAX_POINTS = 128;
export const MIN_COORDINATE = -1_000;
export const MAX_COORDINATE = 1_000;
export type Point = { id: string; x: number; y: number };
export type HullErrorCode = 'too-many' | 'bad-point' | 'duplicate-id' | 'duplicate-position';
export class HullError extends Error {
readonly code: HullErrorCode;
constructor(code: HullErrorCode, message: string) {
super(message);
this.name = 'HullError';
this.code = code;
}
}
function validate(points: Point[]) {
if (points.length > MAX_POINTS) throw new HullError('too-many', `up to ${MAX_POINTS} points`);
const ids = new Set<string>();
const positions = new Set<string>();
for (const point of points) {
if (
!/^[a-z][a-z0-9-]{0,23}$/.test(point.id) ||
!Number.isInteger(point.x) ||
!Number.isInteger(point.y) ||
point.x < MIN_COORDINATE ||
point.x > MAX_COORDINATE ||
point.y < MIN_COORDINATE ||
point.y > MAX_COORDINATE
)
throw new HullError(
'bad-point',
'point ids are lowercase slugs and coordinates are bounded integers'
);
if (ids.has(point.id)) throw new HullError('duplicate-id', `point appears twice: ${point.id}`);
const position = `${point.x},${point.y}`;
if (positions.has(position))
throw new HullError('duplicate-position', `position appears twice: ${position}`);
ids.add(point.id);
positions.add(position);
}
}
const cross = (a: Point, b: Point, c: Point) =>
(b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
const compare = (a: Point, b: Point) => a.x - b.x || a.y - b.y || a.id.localeCompare(b.id);
export function convexHull(points: Point[]): Point[] {
validate(points);
const sorted = [...points].sort(compare);
if (sorted.length <= 2) return sorted;
const lower: Point[] = [];
for (const point of sorted) {
while (lower.length >= 2 && cross(lower.at(-2)!, lower.at(-1)!, point) <= 0) lower.pop();
lower.push(point);
}
const upper: Point[] = [];
for (const point of [...sorted].reverse()) {
while (upper.length >= 2 && cross(upper.at(-2)!, upper.at(-1)!, point) <= 0) upper.pop();
upper.push(point);
}
return lower.slice(0, -1).concat(upper.slice(0, -1));
}type Point struct {
ID string
X, Y int
}
type HullError struct{ Code, Message string }
func (e *HullError) Error() string { return e.Message }
var pointID = regexp.MustCompile(`^[a-z][a-z0-9-]{0,23}$`)
func validate(points []Point) error {
if len(points) > MaxPoints {
return &HullError{"too-many", fmt.Sprintf("up to %d points", MaxPoints)}
}
ids, positions := map[string]bool{}, map[string]bool{}
for _, point := range points {
if !pointID.MatchString(point.ID) || point.X < MinCoordinate || point.X > MaxCoordinate || point.Y < MinCoordinate || point.Y > MaxCoordinate {
return &HullError{"bad-point", "point ids are lowercase slugs and coordinates are bounded integers"}
}
if ids[point.ID] {
return &HullError{"duplicate-id", "point appears twice: " + point.ID}
}
ids[point.ID] = true
key := fmt.Sprintf("%d,%d", point.X, point.Y)
if positions[key] {
return &HullError{"duplicate-position", "position appears twice: " + key}
}
positions[key] = true
}
return nil
}
func cross(a, b, c Point) int { return (b.X-a.X)*(c.Y-a.Y) - (b.Y-a.Y)*(c.X-a.X) }
func sorted(points []Point) []Point {
result := append([]Point{}, points...)
sort.Slice(result, func(i, j int) bool {
return result[i].X < result[j].X || (result[i].X == result[j].X && (result[i].Y < result[j].Y || (result[i].Y == result[j].Y && result[i].ID < result[j].ID)))
})
return result
}
func hull(points []Point) ([]Point, error) {
if err := validate(points); err != nil {
return nil, err
}
ordered := sorted(points)
if len(ordered) <= 2 {
return ordered, nil
}
lower := []Point{}
for _, point := range ordered {
for len(lower) >= 2 && cross(lower[len(lower)-2], lower[len(lower)-1], point) <= 0 {
lower = lower[:len(lower)-1]
}
lower = append(lower, point)
}
upper := []Point{}
for i := len(ordered) - 1; i >= 0; i-- {
point := ordered[i]
for len(upper) >= 2 && cross(upper[len(upper)-2], upper[len(upper)-1], point) <= 0 {
upper = upper[:len(upper)-1]
}
upper = append(upper, point)
}
return append(lower[:len(lower)-1], upper[:len(upper)-1]...), nil
}Reading the TypeScriptFresh stacks and integer turns
The lower and upper arrays are stacks. While their last two points and the candidate make a non-left turn, the last point is popped. The cross product uses only integer arithmetic; no angle or square root is needed.
Reading the Gosort.Slice, slices as stacks, and fresh copies
sorted copies the input and orders it with sort.Slice: by x,
then y, then id, the same order as TypeScript’s compare. The walks are
slices; append pushes and lower[:len(lower)-1] pops.
In walk, each step starts from append([]Point{}, …), a fresh copy of the last snapshot, so
popping never changes a snapshot already recorded. Errors come back as a *HullError with the same codes as TypeScript, and ids are checked with the same
regular expression.
What is refusedBounded, distinct survey points
More than 128 points is too-many. An id that isn’t a lowercase slug, or a
coordinate that isn’t a whole number from −1,000 through 1,000, is bad-point. A repeated id is duplicate-id, and two points at
one position are duplicate-position. Empty, one-point, two-point, and
all-collinear inputs return the smallest valid hull.
04 / Try a decision
Should a point on the straight edge remain?
Suppose a new measurement lies exactly on the straight edge between gate and lake. The turn test sees three points in a line, so the cross product is 0. Decide what the strict rule does with it before you check.
Keep the policy explicit: this lesson returns corners only. A cartographic boundary that must preserve every sampled boundary point can retain collinear points with a different pop condition.
05 / Follow the cost
The scan is linear after the sort.
| Operation | Time | Extra space | What it assumes |
|---|---|---|---|
| Sort the points | O(P log P) | O(P) | Order by x, then y, to give both walks a fixed direction. |
| Build one walk | O(P) | O(P) | Each point is pushed once and popped at most once. |
| Build the full hull | O(P log P) | O(P) | The sort dominates the two linear monotonic-chain scans. |
| Test one turn | O(1) | O(1) | An integer cross product tells whether the newest point turns left, right, or stays straight. |
| Trace both walks (In the wild) | O(P²) | O(P²) | traceHull copies the stack after every push so the film can replay it: P + 1 snapshots of up to P points per walk. |
For P points, sorting costs O(P log P). Each scan is O(P) because a point is pushed once and
popped at most once, so the complete algorithm is O(P log P) with O(P) auxiliary storage.
The traced version behind the film keeps P + 1 snapshots per walk, which is O(P²) time and
space; use the plain convexHull when only the boundary is needed.
06 / Give it a real job
Store the outline when the survey is saved.
A parks team’s survey tool collects points from a field crew. When a survey is saved, the
server calls convexHull once and stores the corners beside the points. The map draws
that outline as the park’s footprint, and a quick check against it tells the next crew whether
a new measurement falls outside everything surveyed so far.
The outline owns only the corners, in counter-clockwise order from the leftmost point. It leaves out the interior points, which stay in the survey, and the points on a straight edge, which the strict policy drops. It also leaves out any inward bend: a lake shore that curves into the park is covered by the hull, so the outline is a first test, not the boundary a surveyor would sign.
For geographic data, project coordinates into a planar system before using planar cross products; raw latitude and longitude are not equal-distance x and y. This runs on the server that saves the survey; the map page only draws the corners it gets back, and nothing in a component computes the hull.
07 / Make the call
Use the hull to reduce a geometry problem before solving it precisely.
Use a convex hull when the outer envelope is the question or when interior points can be rejected in a broad phase. Use Ramer–Douglas–Peucker when the input is already an ordered line and you want to preserve its path shape. Use Bresenham when the output is a pixel-grid line, not a boundary around points.
If only a few points are corners, gift wrapping (the Jarvis march) finds each corner by scanning every point, O(P · h) for h corners, with no sort. For the park’s six corners out of ten points that is no saving; for thousands of points with a handful of corners it can be.
SourcesThe monotonic-chain paper
- A. M. Andrew, “Another efficient algorithm for convex hulls in two dimensions”, Information Processing Letters 9(5), 1979, 216–219: sort the points, then build the lower and upper chains.
Checked 23 September 2026.
08 / Take the idea with you
Explain a fence without saying “convex hull.”
“Line the posts up from left to right. Walk along the bottom, and whenever the last three posts bend inward or run straight, pull out the middle one. Walk back along the top the same way. The posts still standing are the fence.”
Before moving on, draw six dots on paper with one of them inside, and walk the bottom edge by hand. Name each dot you pull out and the turn that made you pull it.
Connections to follow nextRelated lessons
- Stack is each walk: push the next point, pop the last one while the turn is wrong.
- Sorting is the O(P log P) step that gives both walks a direction, and the most expensive part of the hull.
- Sweep line also sorts first and then settles everything in one pass from left to right.
- Ramer–Douglas–Peucker keeps the points of an ordered line that stray, where the hull keeps the outside of an unordered cloud.