Convex Hull Visualizer — Monotone Chain
Animated convex hull (Andrew’s monotone chain) on a plane of points — push/pop construction with step controls. Runs in your browser.
Pseudocode
Press Run to animate the algorithm.
Time · Space
How to use
- 1 Press Run to build the convex hull of the scattered points.
- 2 Watch the monotone chain push points and pop them when a turn is not left.
- 3 Use Shuffle for a new random point set, or step through one operation at a time.
- 4 The green outline is the final convex hull.
Why use this tool
- See Andrew’s monotone-chain algorithm build the lower and upper hull.
- Understand why points causing a right turn get popped off the chain.
- Watch the O(n log n) construction — sorting dominates the cost.
- Runs entirely in your browser. No signup, no uploads.
Frequently asked questions
What is a convex hull?
The smallest convex polygon that contains a set of points — imagine stretching a rubber band around all the points and letting it snap tight.
What algorithm does this visualizer use?
Andrew’s monotone chain: sort the points, then build the lower and upper hulls by pushing points and popping any that would create a non-left (clockwise) turn.
What is the time complexity of the convex hull?
O(n log n), dominated by the initial sort; the chain construction itself is linear. Graham scan and QuickHull have the same average bound.
What are convex hulls used for?
Collision detection, shape analysis, pathfinding, GIS, and as a preprocessing step for many other geometric algorithms.
What is Convex Hull Visualizer?
A Convex Hull Visualizer animates how the smallest convex polygon enclosing a set of points is found. Using Andrew’s monotone-chain algorithm, it sorts the points and builds the lower and upper hulls, popping any point that makes a non-left turn.
Features
Step-by-step animation
Watch the hull get built as points are sorted and turns are tested.
Complexity
Time: O(n log n) (sort-dominated). Space: O(n).
100% private
Runs entirely in your browser — nothing is uploaded.
Example
Input
points incl. one interior pointOutput
hull = outer points only; interior point excludedCommon use cases
-
1
Computational geometry
See the foundational hull used by many geometry algorithms.
-
2
Collision & bounds
Compute a tight convex boundary around a point cloud.
-
3
Learn orientation tests
Understand left/right turn tests that build the hull.
Zerethon's convex hull visualizer animates finding the smallest convex polygon that encloses a set of points in your browser, using an O(n log n) algorithm (such as Graham scan or Andrew's monotone chain — dominated by the initial sort). Interior points are excluded from the hull; space is O(n).
- Category
- Algorithm
- Pricing
- Free
- Privacy
- Browser-based
- Signup
- Not required
References
- Convex Hull — Wolfram MathWorld — Wolfram MathWorld
- VisuAlgo — Convex Hull — VisuAlgo (NUS)
- Convex hull — Wikipedia
Privacy
Your data never leaves your browser unless explicitly stated. Convex Hull Visualizer runs entirely client-side — no server upload, no logging, no tracking of your input.
Build, share, and grow on Zerethon Social
Free signup. Earn points, collect achievements, and connect with creators worldwide.