The Convex Hull of a set of points is the smallest convex polygon that contains all the points in that set. Visualize it as the shape formed by stretching a rubber band around all the points. Convex Hull algorithms play a fundamental role in computational geometry with applications in pattern recognition, image processing, GIS, and more.
This article explores two classical Convex Hull algorithms: Graham Scan and Jarvis March. Both algorithms have distinct approaches and performance characteristics. Detailed explanations, step-by-step examples, and mermaid diagrams clarify their workings.
What is a Convex Hull?
Given a set of points on a plane, the Convex Hull is a polygon that encloses all the points such that any line segment drawn between two points inside or on the polygon never leaves the polygon. The hull is convex, meaning there are no “indentations”.
Graham Scan Algorithm
The Graham Scan algorithm finds the Convex Hull by sorting points based on their polar angle relative to an anchor point and then traversing the sorted list to build the hull using a stack to manage turn directions.
Step-by-step Graham Scan
- Find the anchor point: the point with the lowest y-coordinate (and lowest x if tie).
- Sort points by polar angle: calculate angles between the anchor and all other points and sort accordingly.
- Initialize a stack: push the anchor and the point with the smallest angle.
- Iterate through sorted points: for each next point, check the orientation of the last two points in the stack with the new point:
- If it makes a left turn, push the point.
- If it makes a right turn or is collinear, pop from the stack until a left turn is found, then push.
- The stack after processing all points: forms the vertices of the Convex Hull in order.
Example of Graham Scan
Consider the following points:
- P0: (0, 0)
- P1: (1, 1)
- P2: (2, 2)
- P3: (3, 1)
- P4: (2, 0)
Step 1: Anchor is P0 (lowest Y).
Step 2: Sort points by angle relative to P0:
- P4 (angle 0°)
- P3 (angle ~18°)
- P1 (angle 45°)
- P2 (angle 45° but farther)
Step 3 & 4: Iteratively build stack and remove points causing right turns.
Final hull points: P0 → P4 → P3 → P2
Jarvis March Algorithm (Gift Wrapping)
Jarvis March is a more intuitive Convex Hull algorithm, sometimes called the “Gift Wrapping” algorithm. It “wraps” around the points one by one, selecting the next hull point by choosing the point with the lowest polar angle relative to the current point.
Step-by-step Jarvis March
- Start from the leftmost point: this point is on the hull.
- Choose the next point: find the point such that all others lie to the right relative to the segment from current hull point.
- Repeat: set the next point as current and find the next hull point until you reach the start point again.
Example of Jarvis March
With the same set of points on the plane:
- Start at P0 (0,0)
- Scan all points to find the one making the smallest counterclockwise angle
- Choose points wrapping outward until returning to P0
Comparison: Graham Scan vs Jarvis March
| Aspect | Graham Scan | Jarvis March |
|---|---|---|
| Approach | Sort points by angle; stack-based traversal | Wrap hull points iteratively using angle comparisons |
| Complexity | O(n log n) due to sorting | O(nh) where h = hull points count |
| Best for | Large datasets with many points | Small hull relative to total points |
| Ease of Understanding | Moderate (requires stack and orientation checks) | Simple and intuitive (like wrapping gift) |
Interactive Conceptual Visualization
For those interested in visual and interactive exploration, imagine dragging points around on a plane and watching how the hull dynamically updates with Graham Scan or Jarvis March logic. Such interactivity greatly enhances the understanding of the algorithm flow.
Practical Applications of Convex Hull
- Collision detection in gaming and robotics
- Pattern recognition and image processing
- Geospatial mapping and terrain analysis
- Shape analysis and cluster boundary detection
Summary
The Convex Hull is an essential problem in computational geometry solved effectively by algorithms like Graham Scan and Jarvis March. Graham Scan shines with better average performance for large inputs, while Jarvis March offers a straightforward wrapping approach useful for smaller hulls. The choice depends on data size and application needs.
By mastering these methods and visualizing them effectively, developers and computer scientists can handle geometric problems efficiently and elegantly.
