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.

Convex Hull (Graham & QuickHull)

Click to add points, drag to move; Graham scan with step playback or QuickHull divide-by-farthest; compare vertex sets.

About this model

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.

Continue with similar topics in this category — or all 85 in Math Visualization.

View category →

NewSchool

Bézier & de Casteljau

Launch Simulator

Drag control points; live recursive linear-interpolation scaffolding evaluates B(t).

NewSchool

Delaunay & Voronoi

Launch Simulator

Bowyer–Watson triangulation and dual Voronoi tessellation; click to add seeds, drag to move.

NewSchool

Linear Regression: OLS, Ridge, Lasso & R²

Launch Simulator

Click/drag scatter points; fit y = β₀ + β₁x with OLS, Ridge (L2 on slope), or Lasso (L1 on slope). Spike Δy on the largest |x| point to see outlier sensitivity; compare SSE and R².

NewSchool

K-Means Clustering (Lloyd)

Launch Simulator

Click to add points, choose k, randomize centroids, then step Lloyd iterations (assign to nearest centroid, update means). Optional Gaussian-mixture demo; watch within-cluster SSE decrease.

NewSchool

Gradient Descent (2D)

Launch Simulator

Level sets of f(x,y) and path (x,y) ← (x,y) − η∇f; bowl or elliptic well.

NewSchool

Toy 2-Layer MLP + Backprop (XOR / spiral)

Launch Simulator

Click-labeled 2D data; **tanh** hidden layer + **logistic** output trained by **full-batch** gradient descent on **binary cross-entropy**. Heatmap shows **P(class 1)** evolving across epoch blocks — watch the **0.5 decision contour** wrap XOR or untangle spirals.

Convex Hull (Graham & QuickHull)

About this model

How it works

Frequently asked questions

Related simulators

Bézier & de Casteljau

Delaunay & Voronoi

Linear Regression: OLS, Ridge, Lasso & R²

K-Means Clustering (Lloyd)

Gradient Descent (2D)

Toy 2-Layer MLP + Backprop (XOR / spiral)

Convex Hull (Graham & QuickHull)

About this model

How it works

Frequently asked questions