Convex Hull Algorithms: Graham Scan

Before reading this article, I recommend you to visit following two articles. Many concepts and codes are referred from these articles.

1. Determining if two consecutive segments turn left or right
2. Convex Hull Algorithms: Jarvis’s March (Introduction Part)

Introduction

Graham scan is an algorithm to compute a convex hull of a given set of points in $O(n\log n)$ time. This algorithm first sorts the set of points according to their polar angle and scans the points to find the convex hull vertices.

Algorithm

The step by step working of a Graham Scan Algorithms on the point set $P$ is given below.

1. Find the point ($p_0$) with smallest $y$-coordinate. In case of a tie, choose the point with smallest $x$-coordinate. This step takes $O(n)$ time.
2. Sort the points based on the polar angle i.e. the angle made by the line with the $x$-axis. While implementing, we don’t calculate the angle, instead, we calculate the relative orientation of two points to find out which point makes the larger angle. This can be explained with the help of a figure shown below.
   
   To find out whether the line $P_0P_1$ or the line $P_0P_3$ makes the larger angle with the $x$-axis, we calculate the cross-product of vector $\overline{P_1P_0}$ and vector $\overline{P_1P_3}$. If the cross-product is positive, that means vector $\overline{P_1P_0}$ is clockwise from vector $\overline{P_1P_3}$ with respect to the $x$-axis. This indicates that the angle made by the vector $\overline{P_1P_3}$ is larger. We can use any sorting algorithm that has complexity $O(n \log n)$.
3. After sorting, we check for the collinear points. If we find any collinear points, we keep the furthest point from $P_0$ and remove all other points. This step takes $O(n)$ time.
4. First two points in the sorted list are always in the convex hull. In the above figure, points $P_0$ and $P_1$ are the vertices of the convex hull. We maintain a stack data structure to keep track of the convex hull vertices. We push these two points and the next point in the list (points $P_0, P_1$ and $P_3$ in the figure above) to the stack.
5. Now we check if the next point in the list turns left or right from the two points on the top of the stack. If it turns left, we push this item on the stack. If it turns right, we remove the item on the top of the stack and repeat this process for remaining items. This step takes $O(n)$ time.

If we perform these steps on a set of points, we should get correct convex hull.

Program

The python implementation of the above algorithm is presented below. The code follows the step by step process given in the Solution section.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

# find the point with minimum y coordinate
# in case of tie choose the point with minimun x-coordinate
def find_min_y(points):
    miny = 999999
    mini = 0
    for i, point in enumerate(points):
        if point.y < miny:
            miny = point.y
            mini = i
        if point.y == miny:
            if point.x < points[mini].x:
                mini = i
    return points[mini], mini

# comparator for the sorting 
def polar_comparator(p1, p2, p0):
    d = direction(p0, p1, p2)
    if d < 0:
        return -1
    if d > 0:
        return 1
    if d == 0:
        if distance_sq(p1, p0) < distance_sq(p2, p0):
            return -1
        else:
            return 1

def graham_scan(points):
    # let p0 be the point with minimum y-coordinate,
    # or the leftmost such point in case of a tie
    p0, index = find_min_y(points)

    # swap p[0] with p[index]
    points[0], points[index] = points[index], points[0]

    # sort the points (except p0) according to the polar angle
    # made by the line segment with x-axis in anti-clockwise direction
    sorted_polar = sorted(points[1:], cmp = lambda p1, p2: polar_comparator(p1, p2, p0))
    
    
    # if more than two points are collinear with p0, keep the farthest
    to_remove = []
    for i in range(len(sorted_polar) - 1):
        d = direction(sorted_polar[i], sorted_polar[i + 1], p0)
        if d == 0:
            to_remove.append(i)
    sorted_polar = [i for j, i in enumerate(sorted_polar) if j not in to_remove]

   
    m = len(sorted_polar)
    if m < 2:
        print 'Convex hull is empty'

    else:
        stack = []
        stack_size = 0
        stack.append(points[0])
        stack.append(sorted_polar[0])
        stack.append(sorted_polar[1])
        stack_size = 3

        for i in range(2, m):
            while (True):
                d = direction(stack[stack_size - 2], stack[stack_size - 1], sorted_polar[i])
                if d < 0: # if it makes left turn
                    break
                else: # if it makes non left turn
                    stack.pop()
                    stack_size -= 1
            stack.append(sorted_polar[i])
            stack_size += 1
    return stack

Execution Trace

The execution trace of the program for the point sets given below are presented in this section. (The green color means the point is in the convex hull and red color means the point can not be in the convex hull)

The program first finds the point with smallest $y$-coordinate. There are two candidate points for this ($(0, 0)$ and $(0, 7))$. Since this is a tie, the program chooses the one with smaller x-coordinate which is $(0, 0)$. This point is guaranteed to be in convex hull.

The program sorts the points based on the polar angle as shown in the figure below.

The sorted points are $[(0, 0), (7, 0), (3, 1), (5, 2), (9, 6), (3, 3), (5,5), (1, 4)]$.

Next it searches for the collinear points and keep the farthest point. Here points $(3, 3)$ and $(5, 5)$ are collinear with $(0, 0)$. Point $(5, 5)$ is kept and $(3,3)$ is discarded as $(5, 5)$ is far from $(0, 0)$.

Next, the program pushes first three points from the sorted list to the stack. First two points are always in the convex hull.

Next, it checks if the next point in the list turns right or left from the two top points in the stack. In this case, it checks if point $(5, 2)$ turns left or right from points $(7, 0)$ and $(3, 1)$. Since this is a right turn, the point $(3, 1)$ is popped from the stack as it can not be in the convex hull.

Similarly it checks if the new point in the list $(5, 2)$ turns left or right from points $(0, 0)$ and $(7, 0)$. It turns left, so the point is pushed to the stack.

The same process goes on. Next point is $(9, 6)$. It makes a left turn, so we discard point $(5, 2)$.

Next, Point $(9, 6)$ is pushed into the stack.

In the same way, $(5, 5)$ is pushed into the stack.

Next, point $(1, 4)$ is collinear with points $(9, 6)$ and $(5, 5)$. In the case of collinearity, we discard the top of the stack. Point $(5, 5)$ is popped from the stack.

Next, point $(1, 4)$ is pushed into the stack.

Since point $(1, 4)$ is the last point in the list, the algorithm terminates here. The points in the stack are the convex hull.

Complexity

The overall complexity of this algorithm is $O(n\log n)$.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (n.d.). Introduction to algorithms (3rd ed.). The MIT Press.
2. Erickson, J. (n.d.). Convex Hulls. Lecture. Retrieved August 23, 2018, from http://jeffe.cs.illinois.edu/teaching/373/notes/x05-convexhull.pdf
3. Mount, D. M. (n.d.). CMSC 754 Computational Geometry. Lecture. Retrieved August 23, 2018, from https://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf