Convex Hull Algorithms
Overview
The Convex Hull Visualizer demonstrates Graham scan and Jarvis march algorithms for finding the smallest convex polygon containing all points. Watch as each algorithm identifies boundary points and constructs the convex hull. Perfect for understanding computational geometry, polygon algorithms, and divide-and-conquer techniques.
Tips
- The convex hull is the smallest convex polygon containing all points
- Graham scan sorts by polar angle and uses a stack, O(n log n) time
- Jarvis march (gift wrapping) selects extreme points iteratively, O(nh) time where h is hull size
- Try different point distributions: random, circle, grid
- Applications: collision detection, pattern recognition, image processing
- Watch how Graham scan eliminates concave points using cross products
- The hull always includes the extreme points (leftmost, rightmost, etc.)