The convex hull of a set of N points is the smallest perimeter fence enclosing the points.

Convex hull output. Sequence of vertices in counterclockwise order.

Graham scan

1. Choose point p with smallest y-coordinate.
2. Sort points by polar angle with p.
3. Consider points in order; discard unless it create a counterclockwise turn.

Implementations

1) How to find point p with smallest y-coordinate?

• Define a total order, comparing by y-coordinate

2) How to sort points by polar angle with respect to p?

• Define a total order for each point p.

3) How to determine whether p1 -> p2 -> p3 is a counter clockwise turn?

• Computation geometry.

4) How to handle degeneracies (three or more points on a line)?

See booksite