The convex hull CH(P) of a set of points P is the convex polygon that contains all the points P.
The algorithm described on this page is commonly known as Graham's scan.
The following animation demonstrates the algorithm by showing all the intermediate steps.
The algorithm ConvexHull(P) takes as input a set P of points and
returns a list containing the vertices of CH(P) in clockwise order.
This is the pseudocode for the algorithm, as described in [1].
1. Sort the points in lexicographical order on the x and y coordinate, resulting in a sequence p0, p1, ..., pn. 2. Put the points p0 and p1 in a list L_upper. 3. for i = 2 to n 4. append pi to L_upper 5. while L_upper contains more than two points and the last three points in L_upper do not make a right turn 6. delete the middle of the last three points from L_upper. 7. Put the points p[n-1] and p[n-2] in a list L_lower with p[n-1] as the first point. 8. for i = n - 3 downto 0 9. append pi to L_lower 10. while L_lower contains more than two points and the last three points in L_lower do not make a right turn 11. delete the middle of the last three points from L_lower. 12. Remove the first and the last point from L_lower to avoid duplication of the points where the upper and lower hull meet. 13. Append L_lower to L_upper and call the result L. 14. Return L
[1] Computational Geometry - Algorithm and Applications, 3rd edition, section 1.1.
[2] Math StackExchange, How do I visualize if three points represent a right or left turn?, https://math.stackexchange.com/a/2121132