2D Spatial Point Cloud Generator
Synthesizes planar point sets of designated magnitude n ∈ [50, 5000] under controlled geometric distributions (uniform disc, Gaussian cluster, and extreme perimeter rings).
Computer Science / Convex Hull Algorithms
FREE TO EXPLORELABORATORY 17 · COMPUTER SCIENCE
Empirical Analysis of Planar Convex Hull Algorithms: Graham Scan, Jarvis March (Gift Wrapping), Quickhull, Chan's Output-Sensitive Algorithm, and 2D Cross-Product Orientation Invariants
To investigate the geometric mechanics and asymptotic complexity of planar Convex Hull algorithms, evaluate Graham's Scan against Jarvis March (Gift Wrapping), Quickhull, and Chan's optimal output-sensitive algorithm, verify the algebraic 2D cross-product orientation predicate (CCW), and empirically demonstrate the linear scan complexity law T(n) = k_ccw · n + T_0 = 2.0000 · n + 0.0000 orientation tests across point set sizes n ∈ [50, 5000] points. Explore interactive search algorithms, compare operation counts and analyse complexity scaling.
COMPUTE · BENCHMARK · ANALYSE
Your virtual algorithm laboratory.
ORIENTATION CROSS-PRODUCT EVALUATIONS T(N)—
EXECUTION STATUS
Ready to execute point count benchmark.
Adjust point count n, then execute benchmark.
Operation counts are generated deterministically by the exact algorithmic execution model. Modern hardware benchmarks additionally reflect cache line prefetching and branch misprediction penalties.
Algorithmic assumptions and limits
The simulated execution environment models idealized geometric computation where 2D cross-product orientation evaluations execute deterministically with exact arithmetic (T(n) = 2n). In physical semiconductor microprocessors, wall-clock convex hull execution latency is modulated by sorting subsystem memory bandwidth (O(n log n) cache line evictions), branch predictor stalls during orientation sign-checking (`if (Δ <= 0)`), CPU SIMD vectorization capabilities for parallel coordinate transformations, and adaptive precision fallback overhead on near-collinear inputs. In the Graham Scan convex hull benchmark across planar point sets n in [50, 5000] uniformly distributed inside a unit circular bounding disc, the initial polar angle sorting phase executes in O(n log n) time. During the subsequent perimeter scan phase, the algorithm walks the sorted point sequence, pushing each vertex onto the candidate hull stack and popping reflex vertices that produce clockwise (right) turns. Because each of the n vertices is pushed onto the stack exactly once and can be popped at most once across the entire traversal, amortized analysis proves that the total number of 2D cross-product orientation evaluations is strictly bounded by T(n) = 2.0000 · n + 0.0000 tests with exact theoretical intercept T_0 = 0.0000 tests. Ordinary least-squares regression across all benchmark trials yields an ideal coefficient of determination R² = 1.000000 with zero residual variance.
Computational tools & environment.
Pivot Finder & Polar Angle Radial Sorter
Identifies the unique bottom-most extreme pivot point P_0 (lowest y-coordinate, breaking ties with lowest x) and sorts remaining points in ascending polar angle order.
2D Cross-Product Orientation Comparator
Evaluates the sign of the 2D cross product Δ(p₁, p₂, p₃) to determine whether a three-point sequence makes a Counter-Clockwise (left) turn, Clockwise (right) turn, or Collinear line.
LIFO Candidate Convex Hull Stack
Maintains the convex polygonal chain during perimeter traversal, pushing new candidate vertices and popping interior reflex vertices upon detecting right-turn violations.
Output-Sensitive Jarvis March Tracer
Simulates gift-wrapping ray casts from current hull vertex, evaluating all n candidate points per iteration to contrast O(n·h) output sensitivity with Graham's scan.
Floating-Point Precision & Robustness Monitor
Monitors IEEE 754 rounding errors during determinant calculations, detecting collinear ambiguity and verifying Jonathan Shewchuk's adaptive precision predicates.
FOLLOW THE METHOD
A reason behind every step.
To investigate the geometric mechanics and asymptotic complexity of planar Convex Hull algorithms, evaluate Graham's Scan against Jarvis March (Gift Wrapping), Quickhull, and Chan's optimal output-sensitive algorithm, verify the algebraic 2D cross-product orientation predicate (CCW), and empirically demonstrate the linear scan complexity law T(n) = k_ccw · n + T_0 = 2.0000 · n + 0.0000 orientation tests across point set sizes n ∈ [50, 5000] points. Suggested independent settings: 50, 100, 200, 500, 1000, 2000, 5000 points.
01
Synthesize Planar Point Cloud & Locate Extreme Pivot
Initialize the virtual geometric workbench and synthesize n = 50 planar points within the 2D bounding disc. Locate the unique extreme pivot point P_0 having minimum y-coordinate (breaking ties by minimum x-coordinate).
02
Execute Radial Polar Angle Sorting
Translate all points relative to pivot P_0 and sort the remaining n - 1 points in ascending order of polar angle θ = atan2(y - y_0, x - x_0) using introsort in O(n log n) comparisons.
03
Initialize Candidate Hull Stack
Push the pivot point P_0 and the first two sorted points P_1 and P_2 onto the LIFO candidate convex hull stack, establishing the initial directed base edges.
04
Execute Graham Scan Perimeter Walk
Iterate through remaining points P_i from index 3 to n - 1. While the stack contains at least two vertices and the sequence (next-to-top, top, P_i) makes a non-left turn (cross product Δ ≤ 0), pop the top vertex from the stack. Push P_i onto the stack.
05
Record Orientation Evaluations & Close Polygon
Upon reaching the final sorted point, perform a final orientation check against pivot P_0 to close the convex hull polygon. Read the cumulative 2D cross-product evaluation register T(n).
06
Perform Asymptotic Regression Across Point Scales
Repeat the experimental benchmarking across point counts n ∈ [100, 200, 500, 1000, 2000, 5000]. Perform ordinary least-squares linear regression of T(n) against n to compute slope k_ccw, intercept T_0, and coefficient of determination R².
YOUR NOTEBOOK · 0 OBSERVATIONS
Turn measurements into asymptotic insight.
Points are your recorded benchmark observations. The regression line validates Convex Hull Algorithms complexity scaling.
LINEAR ASYMPTOTIC FIT · y = mx + b
T(n) = k_ccw · n + T_0 = 2.0000 · n + 0.0000 tests
| # | Planar point set size n (points) (points) | Orientation cross-product evaluations T(n) (tests) | Planar point set size n (points) | Orientation tests T(n) = 2.0000 · n + 0.0000 (tests) | Remove |
|---|
No readings yet. Execute a point count benchmark and record it.
Calculate it yourself.
CHECK YOUR UNDERSTANDING