Finding The Convex Hull












Figure 33.7: The execution of GRAHAM-SCAN on the set Q of Figure 33.6. The current convex hull contained in stack S is shown in gray at each step. (a) The sequence p1, p2, ..., p12 of points numbered in order of increasing polar angle relative to p0, and the initial stack S containing p0, p1, and p2. (b)-(k) Stack S after each iteration of the for loop of lines 6-9. Dashed lines show nonleft turns, which cause points to be popped from the stack. In part (h), for example, the right turn at angle p7p8p9 causes p8 to be popped, and then the right turn at angle p6p7p9 causes p7 to be popped. (l) The convex hull returned by the procedure, which matches that of Figure 33.6.
  • The remainder of the procedure uses the stack S. Lines 3-5 initialize the stack to contain, from bottom to top, the first three points p0, p1, and p2. Figure 33.7(a) shows the initial stack S. The for loop of lines 6-9 iterates once for each point in the subsequence p3, p4, ..., pm. The intent is that after processing point pi , stack S contains, from bottom to top, the vertices of CH({ p0, p1, ..., pi}) in counterclockwise order. The while loop of lines 7-8 removes points from the stack if they are found not to be vertices of the convex hull. When we traverse the convex hull counterclockwise, we should make a left turn at each vertex. Thus, each time the while loop finds a vertex at which we make a nonleft turn, the vertex is popped from the stack. (By checking for a nonleft turn, rather than just a right turn, this test precludes the possibility of a straight angle at a vertex of the resulting convex hull. We want no straight angles, since no vertex of a convex polygon may be a convex combination of other vertices of the polygon.) After we pop all vertices that have nonleft turns when heading toward point pi , we push pi onto the stack. Figures 33.7(b)-(k) show the state of the stack S after each iteration of the for loop. Finally, GRAHAM-SCAN returns the stack S in line 10. Figure 33.7(l) shows the corresponding convex hull.

Jarvis's march: Jarvis's march computes the convex hull of a set Q of points by a technique known as package wrapping (or gift wrapping). The algorithm runs in time O(nh), where h is the number of vertices of CH(Q). When h is o(lg n), Jarvis's march is asymptotically faster than Graham's scan. Intuitively, Jarvis's march simulates wrapping a taut piece of paper around the set Q. We start by taping the end of the paper to the lowest point in the set, that is, to the same point p0 with which we start Graham's scan. This point is a vertex of the convex hull. We pull the paper to the right to make it taut, and then we pull it higher until it touches a point. This point must also be a vertex of the convex hull. Keeping the paper taut, we continue in this way around the set of vertices until we come back to our original point p0.

More formally, Jarvis's march builds a sequence H = p0, p1, ..., ph-1 of the vertices of CH(Q). We start with p0. As Figure 33.9 shows, the next convex hull vertex p1 has the smallest polar angle with respect to p0. (In case of ties, we choose the point farthest from p0.) Similarly, p2 has the smallest polar angle with respect to p1, and so on. When we reach the highest vertex, say pk (breaking ties by choosing the farthest such vertex), we have constructed, as Figure 33.9 shows, the right chain of CH(Q). To construct the left chain, we start at pk and choose pk 1 as the point with the smallest polar angle with respect to pk, but from the negative x-axis. We continue on, forming the left chain by taking polar angles from the negative x-axis, until we come back to our original vertex p0.

Figure 33.9: The operation of Jarvis's march. The first vertex chosen is the lowest point p0. The next vertex, p1, has the smallest polar angle of any point with respect to p0. Then, p2 has the smallest polar angle with respect to p1. The right chain goes as high as the highest point p3. Then, the left chain is constructed by finding smallest polar angles with respect to the negative x-axis. We could implement Jarvis's march in one conceptual sweep around the convex hull, that is, without separately constructing the right and left chains. Such implementations typically keep track of the angle of the last convex-hull side chosen and require the sequence of angles of hull sides to be strictly increasing (in the range of 0 to 2π radians). The advantage of constructing separate chains is that we need not explicitly compute angles; the techniques of Section 33.1 suffice to compare angles.