The convex hull of a finite planar point set S is the smallest convex polygon that contains every point of S; equivalently, it is the intersection of all convex supersets of S. This simulator implements two classical O(n log n) constructions in the plane. Graham scan picks the lowest-then-leftmost anchor, sorts the remaining points by polar angle about the anchor (ties broken by distance), and walks the sorted list while maintaining a stack: before pushing the next candidate, pop while the last turn would be non-left (cross product ≤ 0), guaranteeing counterclockwise vertices. Snapshots record the stack and the point under consideration for classroom playback. QuickHull chooses the leftmost and rightmost extreme points, splits the set into points above and below the oriented line LR, and recursively attaches the point farthest from each segment (maximizing triangle area, detected via the magnitude of the 2D cross product); points on the segment are discarded as interior to that edge. Collinearities can make tie-breaking differ between algorithms; the UI reports whether the vertex index sets agree for the current cloud. Interaction matches other geometry labs: click empty space to add a point (with a small duplicate guard), drag near a point to move it, and regenerate a random cloud from count and seed.
Who it's for: Undergraduate discrete geometry, algorithms, and computational geometry courses; anyone learning divide-and-conquer versus incremental hull construction.
Key terms
Convex hull
Graham scan
QuickHull
Polar sort
Monotonic stack
Cross product (orientation)
Divide and conquer
Collinearity
How it works
2D convex hull on the canvas: Graham scan (polar sort around the lowest point, stack with CCW turns) with a step slider and optional playback, or QuickHull (divide by the farthest point from segment LR, recurse). Compare both on the same set.
Frequently asked questions
Why can Graham and QuickHull disagree on “the” hull?
All extreme boundary points lie on the hull, but different implementations choose different subsets when many points are collinear along an edge. Graham scan with a non-strict left turn test keeps only endpoints of collinear runs; QuickHull may retain intermediate collinear vertices unless explicitly filtered. Both describe the same convex set; vertex lists can differ.
What does the cyan polyline show in Graham mode?
It traces the current stack of candidate hull vertices at the selected construction step—the partial hull Graham would have after processing points up to that snapshot. The pink ring highlights the point currently being considered.
Is this implementation numerically robust?
The demo uses double-precision floats and standard cross products. Near-degenerate angles or nearly collinear triples can flicker if points are edited to be extremely close; the duplicate guard when adding points reduces accidental coincident seeds.
How does QuickHull split the set?
After fixing the extremes L and R, points strictly to the left of oriented LR form the upper chain problem; points to the right form the lower chain. Each recursive call picks the farthest point C from segment AB among points on the correct side, partitions the remainder into triangles ABC, and recurses on outer subsets until no point lies strictly outside the edge.