V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Convex Hull

Andrew's monotone chain with cross-product turn tests

The tight boundary around a point set

The convex hull is the smallest convex polygon containing every input point. Imagine stretching a rubber band around the outermost points: when released, it touches the hull vertices and leaves all interior points enclosed.

Use cross products to keep only left turns

For points O, A, and B, the sign of (A-O) x (B-O) tells whether the path turns left or right. Andrew's algorithm sorts points by (x, y), scans left to right for the lower hull, then right to left for the upper hull. A non-left turn pops the middle point because it cannot belong to the convex boundary.

Sort the points by (x, y), then scan left to right to build the lower hull with cross-product turn tests.

1function convexHull(pts: Pt[]): Pt[] {
2 pts.sort((a, b) => a.x - b.x || a.y - b.y); // sort by (x,y)
3 const cr = (o: Pt, a: Pt, b: Pt) => // cross product (A-O)x(B-O)
4 (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
5 const lower: Pt[] = [];
6 for (const p of pts) { // lower hull: left to right
7 while (lower.length >= 2 && cr(lower.at(-2)!, lower.at(-1)!, p) <= 0) lower.pop(); // pop non-left turns
8 lower.push(p);
9 }
10 const upper: Pt[] = [];
11 for (const p of [...pts].reverse()) { // upper hull: right to left
12 while (upper.length >= 2 && cr(upper.at(-2)!, upper.at(-1)!, p) <= 0) upper.pop();
13 upper.push(p);
14 }
15 return [...lower.slice(0, -1), ...upper.slice(0, -1)]; // concatenate lower and upper hulls
16}
Points7
PhaseLower hull
StackEmpty
1 / 16

Complexity and uses

Sorting costs O(n log n); each point enters and leaves each scan stack at most once, so both scans are linear. Convex hulls are a foundation for collision tests, farthest-point pairs, minimum enclosing shapes, and geometric preprocessing.

The stack invariant is simple: every consecutive triple currently on the chain makes a left turn. The moment a new point violates that invariant, pop until convexity is restored.