Graham Scan: O(n log n) convex-hull algorithm

Visualization:

Algorithm:

1. Find the point with the lowest y-coordinate, break ties by choosing lowest x-coordinate. Call this point P. Add P to the convex hull.
2. Sort the remaining points in increasing order of the angle they and the point P make with the x-axis.
3. Consider each point in the sorted array in sequence.
4. Let the current point be X. Add X to the convex hull.
5. Look at the last 3 points in the convex-hull, and determine if they make a right turn or a left turn. If a right turn, the second-last point is not part of the convex hull, and lies ‘inside’ it. Remove it from the convex-hull.
6. Repeat step 2 until last 3 points comprise a left turn.
7. If at any stage the three points are collinear, one may opt either to discard it or keep it, based on the requirements for that specific application (minimum number of points in the hull vs all points on boundary of hull).
8. Done!

Implementation details:

• One can use a simple array or queue to store the current convex-hull.
• Sorting in order of angle does not require computing the angle. It is possible to use any function of the angle which is monotonic. The dot product is one of the most convenient functions to use.
• Given points A, B and C figuring out whether they make a left turn or a right turn also does not require computing the angle. A recommended option is the cross-product of the vectors AB and AC given by

Source: Adapted from Wikipedia.