Convex Hull Algorithms

Visualize the Graham Scan algorithm with step-by-step execution

Controls

50
Instructions: Click on the canvas to add points, or use "Add Random Points" button. Once you have at least 3 points, click "Compute Hull" to run the Graham Scan algorithm.

Visualization

Graham Scan Ready
Points: 0

Total Points

0

Hull Points

0

Current Step

0

Time Complexity

O(n log n)

Help

What is a Convex Hull?

The convex hull of a set of points is the smallest convex polygon that contains all the points. Imagine wrapping a rubber band around all the points - the shape it forms is the convex hull.

Properties:

  • The convex hull is always a convex polygon
  • All points are either on the hull or inside it
  • It's the minimum perimeter polygon enclosing all points
  • Common applications: collision detection, pattern recognition, image processing
Graham Scan Algorithm

The Graham Scan is an efficient algorithm for computing the convex hull, developed by Ronald Graham in 1972.

Steps:

  1. Find the anchor point: Select the point with the lowest y-coordinate (leftmost if tie)
  2. Sort points: Sort all other points by polar angle relative to the anchor point
  3. Build hull: Process points in order, maintaining only left turns (removing right turns)
  4. Complete: The resulting points form the convex hull

Time Complexity: O(n log n) - dominated by the sorting step

Space Complexity: O(n) - for storing the hull points

Color Coding
  • Blue circles: Input points not yet processed
  • Red circle: Anchor point (lowest y-coordinate)
  • Green circles: Points on the convex hull
  • Yellow circle: Current point being processed
  • Gray lines: Edges being considered
  • Green polygon: Final convex hull
How to Use Cross Product for Turn Detection

The Graham Scan uses the cross product to determine if three points make a left turn or right turn:

  • Cross Product > 0: Left turn (counter-clockwise) - keep the point
  • Cross Product < 0: Right turn (clockwise) - remove previous point
  • Cross Product = 0: Collinear points

For three points P1(x1,y1), P2(x2,y2), P3(x3,y3):

cross = (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1)

Applications of Convex Hull
  • Computer Graphics: Collision detection, rendering optimization
  • Robotics: Path planning, obstacle avoidance
  • Pattern Recognition: Shape analysis, feature extraction
  • GIS: Geographic data analysis, boundary detection
  • Machine Learning: Support Vector Machines, outlier detection
  • Image Processing: Object detection, contour analysis