convex hull scheme code example

Example: what is convex hull

#Let p_0 be the point in G with the smallest y-coordinate. In case there is a tie, it is the left most element.
#Let {p_1, p_2, ... ,p_m } be the set of remaining point in G, sorted by polar angle in clock wise order around p_0( if more than one point has the same angle, remove all but the one that is farthest from p_0)
Stack S
S.push(p_0)
S.push(p_1)
S.push(p_2)
function next_to_top(stack)
   returns the point one entry below the top of the stack S
function top(stack)
  returns the top point of a stack



for i <- 3 to m
        do while the angle formed by points next_to_top(S), top(s), and p_i make a turn which is not left(either straight or to the right)
                do S.pop()
             S.push(p_i,S)
return S