The problem statement is given a set of points, in compute the convex hull of S. The input of the algorithm is the set, , of points and the output of the algorithm is the set of points that are the vertices of the convex hull of
Our algorithm will use a standard design technique to generate what’s called an incremental algorithm. That is we compute the solution for the first points then add the point and compute the new solution using the previous solution.
Algorithm ConvexHull(P) (the pseudocode is borrowed from “Computational Geometry algorithms and applications”)
Input. A set P of points in the plane
Output. A list containing the vertices of in clockwise order.
1. Sort the points by x-coordinate, resulting in a sequence
2. Put the points and in a list with as the first point.
3. for to
4. do Append to
5. while contains more than two points and the last three points in do not make a right turn
6. do Delete the middle of the last three points from
7. Put the points and in a list with as the first point.
8. for downto 1
9. do Append to
10. while contains more than 2 points and the last three points in do not make a right turn
11. do Delete the middle of the last three points from
12. Remove the first and last point from to ovoid duplication of the points where the upper and lower hull meet.
13. Append to and call the resulting list