Graham Scan - Pseudocode

Pseudocode

First, define

# Three points are a counter-clockwise turn if ccw > 0, clockwise if # ccw < 0, and collinear if ccw = 0 because ccw is a determinant that # gives the signed area of the triangle formed by p1, p2 and p3. function ccw(p1, p2, p3): return (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x)

Then let the result be stored in the array points.

let N = number of points let points = the array of points swap points with the point with the lowest y-coordinate sort points by polar angle with points # We want points to be a sentinel point that will stop the loop. let points = points # M will denote the number of points on the convex hull. let M = 1 for i = 2 to N: # Find next valid point on convex hull. while ccw(points, points, points) <= 0: if M > 1: M -= 1 # All points are collinear else if i == N: break else i += 1 # Update M and swap points to the correct place. M += 1 swap points with points

This pseudocode is adapted from Sedgewick and Wayne's Algorithms, 4th edition.

The check inside the while statement is necessary to avoid the case when all points in the set are collinear.