Graham Scan to Find the Convex Hull of a Set of Points in 2D

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

This Demonstration shows the steps of the Graham scan, an algorithm to find the convex hull of a finite set of points in 2D. The method has time complexity for points. You can drag the points to change their positions, move the step slider to step through the algorithm or generate new points for a new problem.

Contributed by: Aaron T. Becker, Yitong Lu and Daniel Biediger (December 2020)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The first step is to find the point with the lowest coordinate. This is the starting point of the convex hull. (If more than one point has this value, the rightmost one is used). Second, all the remaining points are sorted by polar angle from the starting point. This can be accomplished without trigonometry by using the reciprocal of the slope (–run/rise); use negative infinity if the points have the same coordinate. Call this list sortedPoints.

The algorithm then considers each sorted point in sequence, which you can animate by moving the "step" slider.

A stack called convexHull is maintained, initialized with the starting point and the first sorted point. For every additional point in sortedPoints, we determine if connecting to this point from the convexHull required a left turn or a right turn. If a right turn was required, points are popped off the stack convexHull until connecting to the current point in sortedPoints requires a left turn (the removed lines from convexHull are drawn as dashed red lines). This point is then added to convexHull, and the process is repeated until all the points in sortedPoints have stepped through.

The function isLeftTurn[] returns the signed area of the triangle defined by the points , , . If this area is positive, then going from to is a left turn. If the area is negative, it is a right turn. The area computation is the determinant of a matrix, and so requires no trigonometric functions.

Reference

[1] R. L. Graham, "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set," Information Processing Letters, 1(4), 1972 pp. 132–133. doi:10.1016/0020-0190(72)90045-2.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send