FINDING THE CONVEX HULL OF A SIMPLE POLYGON IN LINEAR TIME S. Y. Shin T. C. Woo Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 February 1985 Technical Report 85-3

Finding the Convex Hull of a Simple Polygon in Linear Time S. Y. Shin T. C. Woo Department of Industrial & Operations Engineering University of Michigan Ann Arbor, Michigan 48109 November 1984 This work was supported in part by AFOSR under contract F4920-82-C-0089 and in part by IBM Data Systems Division.

Summary A new linear algorithm for finding the convex hull of a simple polygon is given. Based on the original idea by Sklansky (7), our version is easy to understand. Adopting the form of CH-POL by Toussaint and Avis (9), the presentation is concise. As shown in the Appendix, a PASCAL implementation of the algorithm itself is only half a page long. In the paper, we define a "zipper" as a non-self-intersecting, concave chain. Choosing an extreme vertex of the polygon as the initial zipper, we update it by classifying a vertex of the given polygon by one of three cases. Case 1: vertex of the given polygon is added to the zipper. Case 2: vertex of the given polygon is not added to the zipper. Case 3: zipper vertex is deleted. We show that, after a complete traversal of the given polygon, the zipper thus constructed is the convex hull.

Abstract Though linear algorithms for finding the convex hull of a simply-connected polygon have been reported, not all are short and correct. A compact version based on Sklansky's original idea (7) and Bykat's counter-example (8) is given. Its complexity and correctness are also shown. Keywords: Convex hull, linear algorithm, computational geometry

1. Introduction There have been many reports on a linear algorithm for finding the convex hull of a simple polygon. Certain versions were prone to counter-examples. In particular, a recent version by Ghosh and Shyamasundar (1) turned out to be incorrect (2,3). Ideally, an algorithm should be not only correct but also easy to implement. McCallum and Avis (4), for example, reported a version using two stacks. Lee (5) used one stack but the algorithm itself was two pages long. Recently, Graham and Yao (6) reported a compact algorithm that is said to be similar in spirit to Lee's version. Both (5) and (6) included two types of pocket test. In this paper, we present a version employing only one pocket test. Perhaps, the simplest version is still the one presented by Sklansky () in 1972. After a counter-example by Bykat (8), sufficiency condition was established by Toussaint and Avis (9) in 1982 and by Orlowsky (10) in 1983. Almost concurrently, Sklansky gave a modified version 11) but it was later shown to be incorrect by Toussaint and El Gindy (12). Our search for a simple, concise, and correct linear convex hull algorithm traces the following path. For simplicity, we adopt the ideas from the original version by Sklansky (7). For conciseness, we follow the form of CH-POL by Toussaint and Avis (9). For correctness, we use the notion of a pocket (or lobe) as in Graham and Yao (6) (or Lee (5)) with Bykat's counter-example (8) in mind. 1

2. Preliminaries Let P be a simple polygon with n vertices. Each vertex Vi, i = 0, 1, 2,..., (n-l), is represented by its X and Y coordinates, (Xi,Yi). Let V0 be the vertex with the minimum Y coordinate. If two or more vertices are tied then we choose among them the vertex with the minimum X coordinate as Vg. Starting from Vg and traversing the boundary B(P) of P in the clockwise order, we label the jth vertex from V0 as Vi, where i is j modulo n. These vertices in sequence are maintained as a circular doubly linked list. Throughout this paper we assume the following: (1) The boundary B(P) of a simple polygon P is traversed in the clockwise order from VO. (2) No three consecutive vertices are colinear. Definition 2.1: L(Pi,Pj) denotes a directed line segment joining two points Pi J 1 J and Pi in the direction from Pi to Pj. Definition 2.2: An edge E(Vi,Vi+l) of P is a directed line segment L(Vi,Vi+l) joining two adjacent vertices Vi and Vi+1 on B(P). A chain C(Vi,Vj) is a sequence of edges E(Vi,Vi+i), E(Vi+l,Vi+2),..., E(Vj_-,Vj) on B(P) in the clockwise order. Definition 2.3: A vertex Vi of P is extreme if Vi cannot be expressed as a convex combination of other vertices in P, i.e., Vi is extreme if and only if Vi X Z aj Vj, E aj = 1, and aj - O. jyi ji Definition 2.4: The convex hull CH(P) of P is the smallest convex polygon containing P. 2

Definition 2.4 necessarily implies that every vertex of CH(P) is an extreme vertex of P. Hence, one way to find CH(P) is to discard all non-extreme vertices. To characterize a non-extreme vertex, we employ the notion of a pocket. Definition 2.5: A pocket PKT(Vi,Vj) is one or more regions bounded by L(Vi,Vj) and C(Vi,Vj) such that all points in C(Vi,Vj) are on or to the right of L(Vi,Vj). We state an interesting property of a pocket due to Graham and Yao (6). Lemma 2.1: Let Vr be in a PKT(Vi,Vj). If Vr is neither Vi nor Vj, then Vr is not an extreme vertex of P. 3

3. Property of Zipper A pocket PKT(Vi,Vj) is said to be maximal with respect to C(VOVq) if C(Vi,Vj) is not contained in another pocket PKT(Vk,Vm), where o i < j - q, and o 1 k < m - q. Let an ordered list (Zo,Z1,Z2,...,Zj) be the sequence of all vertices in C(Vo,Vq) such that PKT(Zi,Zi+1), o < i < j, is maximal with respect to C(VO,Vq). The sequence of line segments (L(Zo,Z1),L(Z1,Z2),..., L(Zj_,,Zj)) is said to be a zipper ZPR(VO,Vq) as illustrated in Figure 3.1. Insert Figure 3.1> In this section, we show that ZPR(VO,Vq) is concave and non-self-intersecting. Our first lemma forms the basis for showing this property. In its proof and in all subsequent discussions, we use the following notations. Vq+l: = the most recently visited vertex in P. Vq: = the previous (counter-clockwise) vertex of Vq+l in P. Zj: = the vertex that is most recently added into ZPR(Vo,Vq). Zjl: = the previous vertex of Zj in ZPR(VoVq). V*: = the previous vertex of Zj in P. Lemma 3.1: Let ZPR(VO,Vq) = (L(ZO,Z1), L(Z1,Z2,),..., L(Zj_l,Zj)) and o < q < n. Any vertex Vk in the chain C( rvq) must be to the right of L(Zi,Zi+l), o' i < r' j, if Vk Zi+1 4

Z3 z.~ ~~~ ~..:...............!......!!!!!.i11!i~~iii!: "V Zj ~!!::"::::::::::: _ x —--................. - _..........._' —................... A s,'.,,.'..........,''.*.....,,., /.......:..,..... %..:..' X V, \..........., ~~~........................ a-~. -. -. -. -. -. -. -. -. -............. I.-. -.. -................................................................................. Zo: Vo Figure 3.1': Vertices of a polygon P and ZPR(VoVq)

[Proof] The proof will be by the induction on the subscript i of a zipper vertex Zi in ZPR(VO,Vq). Let Z_1 be a point on the horizontal line containing Z0 such that Z_1 lies to the right of ZO. Let Li be the line containing L(Zi_l,Zi), i=0,1,2,...,j. Li partitions the plane into two half planes. Let LHPi be the half plane to the left of L(Zi-l,Zi) and RHPi be the other. i = 0: Since V0 is extreme, V0 coincides with ZO. By the way in which V0 is chosen, the Y coordinate of V0 is not greater than the Y coordinate of any other vertex in P. Therefore, C(Vo,Vq) cannot pass through LHPO. Now, RHPo is partitioned by L1 into two regions, RHPO n LHP1 and RHPO n RHP1. We need to show that C(Z1,Vq) cannot be in RHPo n LHP1. Suppose that some vertices in C(Z1,Vq) are in RHPo n LHP1. Let W be the vertex in C(Zi,Vq) such that C(ZO,W) is to the right of L(Zo,W). Clearly, PKT(Zo,W) contains C(ZO,Z1), which contradicts the maximality of PKT(ZO,Z1). Suppose that the lemma is true for i = m-l < j-2. m i=m: We need to show that C(Zi+i,Vq) cannot be in R = [ n RHPp]n p=o LHPm+l as shown in Figure 3.2 <Insert Figure 3.2> Suppose that some vertices in C(Zm+l,Vq) are in R. Let W be the vertex in C(Zm+l,Vq) such that C(Zm,W) is to the right of L(Zm,W). PKT(Zm,W) contains C(Zm,Zm+l), which contradicts the maximality of PKT(Zm,Zm+i). 5

L2 Li 1 [ n RHPp ] n LHPA: -: l\ ",,||||||J, 1;,, -""IZm L o....................................................... 2 Zm+ I " gu 3.2.:..........::!:!:!:: e:n:[::::]::..m+.... RHPo I" LHP,+ L................ ~:: RH ~~~~o n............ Lo~~~~~~~~.......... LH ~~~~o o............ Figur 3.2 CC V+r V ) cn...............P,+...........

As illustrated in Figure 3.3, the property described in Lemma 3.1 does not necessarily hold true unless V0 is an extreme vertex of P. We next state the lemmas characterizing a ZPR(VO,Vq), the proofs of which are direct consequences of Lemma 3.1. <Insert Figure 3.3> Lemma 3.2: Let ZPR(Vo,Vq) = (L(Zo,Z1), L(Z1,Z2),..., L(Zj_l,Zj)). The internal angle ANGLE (Zi,Zi+lZi+2) between two consecutive line segments L(Zi,Zi+l) and L(Zi+l,Zi+2), o' i ~ j-2, is strictly between zero and 180 degrees. Lemma 3.3: A ZPR(Vo,Vq) is not self-intersecting. finally, we show that a zipper vertex Zk cannot be in a pocket PKT(Zi,Zi+l) if k ~ i and k i i+l. We use this property to update ZPR(VO,Vq). Lemma 3.4: Let ZPR(Vo,Vq) be (L(Zo,Z1),L(Z^1Z2),..., L(Zj_.,Zj)). Then, Zk nPKT(Zi,Zi+l) = Zk if k=i or i+l 0 otherwise for all o < i < j and o < k < j. [Proof] Suppose that Zk nPKT(Zi,Zi+i) i 0 for some k ~ i and k ~ i+l. Then either P is not simple or Vo is not an extreme point. 6

Figure 3.3 Lemm 3 1 does not hold true Figure 3 3 Lemma 3 1 does not hold true if VO is not extreme.

4. updating of Z Consider the relationship between two line segments L(Zj_l,Zj) and E(V,,Zj) As illustrated in Figure 4.1, the vertex Vq+l can be in any one of the four quadrants formed by the extensions of these two line segments. The quadrants are: Qla: to the right of L(Zj_l,Zj) and to the right of E(V*,Zj) Qlb: to the right of L(Zj_l,Zj) and to the left of E(V*,Zj) Q2a: to the left of L(Zjl,Zj) and to the right of E(V*,Zj) Q2b: to the left of L(Zj_i,Zj) and to the left of E(V*,Zj) <Insert Figure 4.1> If Vq+l is in Qlb, it is also in PKT(Zj_l,Zj). By Lemma 2.1, Vq+l and its clockwise vertices in PKT(Zj_l,Zj) can be deleted. Otherwise, we need to show if the existing zipper vertices are to be deleted or kept to advance to Vq+.1 The following three lemmas as illustrated in Figure 4.2 are useful for the updating of ZPR(VO,Vq). <Insert Figure 4.2> Lemma 4.1: Let ZPR(Vo,Vq) = (L(Zg,Z1), L(Z1,Z2)...., L(Zj_l,Zj)) and Vq = Zj VO. All pockets PKT(Zi,Zi+i), o - i j, are maximal with respect to C(VO,Vq+l), if Vq+l is in Qla. [Proof] If Vq+l = Vo, then ZPR(VO,Vq) together with E(Vq,Vq+l) forms a convex polygon since Vq+l = V0 and ZPR(Vo,Vq) is concave and non-self7

zj-1 Q 2D zj_,." Q 2a A Qlb /aQla \/ Figure 4.1 Possible locations of vertex Vq+I

Zj-l Zj.Vq PKT(Zj-,, Vq+l -' Va (a) Illustration of Lemma 4.1 Zj-1 "'..Zj PKT(jIZ,-,,Zo / - - — L /. V, (b) Illustration of Lemma 4.2 Vq+l \ PKT j-1.^^ V, (c) Illustration of Lemma 4.3 Figure 42 Updating Zipper Vertices

intersecting. Therefore, the result follows immediately. Let us consider the case for Vq+l g V0. Since ZPR(Vo,Vq) implies that PKT(Zi,Zi+l), o i < j, is maximal with respect to C(VO,Vq), all we need to show is that E(Zj,Vq+l) is PKT(Zj,Vq+l) and is maximal with respect to C(VOVq+l). First we show E(Zj,Vq+l) n PKT(Zi,Zi+l) ~ E(Zj,Vq+l) for any o - i < j. By Definition 2.5, Vq+l cannot be in PKT(Zj_l,Zj) since Vq+l is in Qla. From Lemma 3.4, Zj cannot be in PKT(Zi,Zi+l) for any o i < j-l. Therefore, E(Zj,Vq+l) n PKT(Zi,Zi+l) ~ E(Zj,Vq+l) for any o' i < j. Finally, there does not exist a vertex Vr in C(VO,V*) such that C(Vr,Vq+l) ano L(Vr,Vq+l) form a pocket PKT(Vr,Vq+l) since ZPR(Vo,Vq) is concave and P is simple. Hence, the result follows. Lemma 4.2: Let ZPR(Vo,Vq) = (L(Zo,Z1), L(Z1,Z2),..., L(Zj_i,Zj)). If C(Vq,Vr), r>q, is in PKT(Zj_l,Zj), then Vr+l is also in PKT(Zj_l,Zj) unless Vr+l is to the left of L(Zj_l,Zj). [Proof] Since P is simple, C(Vq,Vr+l) can get out of PKT(Zj_l,Zj) only through L(Zj_l,Zj). Lemma 4.3: Let ZPR(VO,Vq) = (L(Zo,Z1), L(Z1,Z2),..., L(Zj_l,Zj)). Then PKT(Zj_l,Zj) is not maximal with respect to C(VO,Vq+l), if Vq+l is in quadrant Q2a or Q2b. [Proof] ANGLE(Zj_l,Zj,Vq+l) is greater than or equal to 180 degrees since Vq+l is in Q2a or Q2b. Since ZPR(VoVq) is concave and non-selfintersecting, there must exist a vertex Z in ZPR(VO,Vq) such that L(Z,Vq+1) and C(Z,Vq+1) form a pocket PKT(Z,Vq+l). Clearly, PKT(Z,Vq+l) contains c(z3jlZ)8

5. The Algorithm and Its Analysis Our linear algorithm for finding the convex hull of a simple polygon P takes Vi, i=o,l,...n-l, as input and constructs a ZPR(Vo,Vq) with vertices Zj. Algorithm 5.1 Step 0. Z - <- V, Z1 < — V1, j < — 1, q < — 1. while (Vq f Vg) do; Step 1. if Vq+l is to the right of L(Zj_l,Zj), then do; Step la. if Vq+l is to the right of E(V*,Zj) then j < — j+l, Zj -- Vq+l, q < — q+1. Step Ib. else while (Vq+l is on or to the right of L(Zjl,Zj)) do; q < — q+l end end Step 2. else do; while (Zj f V0 and Zjl is not to the right of L(Zj,Vql)) do; j < — j-l end. j <- j+1, Zj < — Vqe, q <- q+l. end end Step 3. Stop. We show the correctness of Algorithm 5.1 with the following lemma. Lemma 5.1: Algorithm 5.1 constructs ZPR(VQ,Vq) correctly. 9

[Proof] The proof will be by induction on the number of times Step 1 is reached. Initially, the statement is trivially satisfied by Step 0 of the algorithm. Suppose that the lemma is true when Step 1 is executed m times. Then, there are three cases: (1) Case la: Vq+l is in Qla (2) Case lb: Vq+l is in Qlb (3) Case 2: Vq+1 is in Q2a or Q2b Case la: Vq+l qualifies as a zipper vertex if PKT(Zj,Vq+l) is maximal with respect to C(Vo,Vq+l). Since Vq+l is in quadrant Qla, by Lemma 4.1, PKT(Zj,Vq+l) is maximal. Indeed, Step la takes Vq+l as the new Zj. Since the correct vertex is added to the zipper the next time Step 1 is reached, the induction holds. Now, Lemma 4.1 requires the precondition that Vq equals Zj. This precondition is satisfied iteratively after executing Step la or Step 2. After executing Step lb, though Vq 4 Zj, the control must go to Step 2 oecause Vq+1 cannot be to the right of L(Zj_.,Zj). Hence, the precondition for Lemma 4.1 is always satisfied. Case lb. Because Vq+l is in quadrant Qlb, by Definition 2.5, Vq+l is in PKT(Zj_l,Zj). Therefore, Vq+l should not be a zipper vertex. Furthermore, by Lemma 4.2, all the subsequent vertices in PKT(Zj_l,Zj) should not be in the zipper ZPR(Vo,Vq) either. This is precisely what Step lb does. Since no zipper vertex is added, the next time Step 1 is reached, ZPR(Vo,Vq) is still correct. 10

Case 2: Step 2 deletes Zj since PKT(Zj_l,Zj) is not maximal with respect to C(Vo,Vq+l) by Lemma 4.3. The old Zj_- becomes the new Zj. This process is repeated until either Zj = ZO or Zj_- is to the right of L(Zj,Vq+l). At that point PKT(Zj,Vq+l) is maximal with respect to C(Vo,Vq+l), because ZPR(Vo,Vq+1) is concave and non-self-intersecting. Hence, the lemma is true. When Vq+l coincides with VO, Step 3 terminates the algorithm, and the lemma is still true by the induction hypothesis. Since ZPR(Vg,Vq) is concave and non-self-intersecting, it must form a convex polygon Pc containing P if Vq = VO. Since every vertex of Pc is a vertex of P, it is clear that P, is the smallest convex polygon containing P. By Definition 2.4, Pc must be the convex hull of a simple polygon P. Theorem 5.1: Algorithm 5.1 finds the convex hull of a simple polygon P with n vertices in O(n) time. [Proof] The algorithm moves forward, except in Step 2, until V0 is revisited. Step 2 is executed at most a total of n-3 times. 11

6. Coluding Rerks Algorithm 5.1 removes the vertices that cause self-intersection (8) in CH-POL (9). It is shorter than the version by Graham and Yao (6) when both the Left Hull and the Right Hull are taken into account. Acknowledgement The authors wish to thank 3. D. Wolter and H. C. Lee for their critical reading of the manuscript and their constructive suggestions. J. D. Wolter implemented Algorithm 5.1 in several languages. His version in PASCAL is supplied in the Appendix. 12

References 1. S. Ghosh and R. Shyamasundar, A Linear Time Algorithm for Obtaining the Convex Hull of a Simple Polygon, Patt. Recog., 16, 8, (1983), 587-592. 2. R. Shyamasundar, Note on a Linear Time Algorithm for Obtaining the Convex Hull of a Simple Polygon, private communication, August 28, 1984. 3. T. Woo and S. Shin, Counterexamples, private communications, July 10, 1984 and October 15, 1984. 4. D. McCallum and D. Avis, A Linear Time Algorithm for Finding the Convex Hull of a Simple Polygon, Infor. Proc. Lett., 9, (1979), 201-205. 5. D. Lee, On Finding the Convex Hull of a Simple Polygon, Intern. J. of Comput. and Infor. Science, 12, 2, (April 1983), 87-98. 6. R. Graham and F. Yao, Finding the Convex Hull of a Simple Polygon, J. of Algorithms, 4, (1983), 324-331. 7. J. Sklansky, Measuring Concavity on a Rectangular Mosaic, IEEE Trans. Comput., 21, (1972), 1355-1364. 8. A. Bykat, Convex Hull of a Finite Set of Points in Two Dimensions, Infor. Proc. Lett., 7, 6, (1978), 296-298. 9. G. Toussaint and D. Avis, On a Convex Hull Algorithm and its Application to Triangulation Problems, Patt. Recog., 15, 1, (1982), 23-29. 10. M. Orlowsky, On the Condition for Success of Sklansky's Convex Hull Algorithm, Patt. Recog., 16, 6, (1983), 579-586. 11. J. Sklansky, Finding the Convex Hull of a Simple Polygon, Patt. Recog. Lett., 1, (1982), 79-83. 12. G. Toussaint and H. El Gindy, A Counterexample to an Algorithm for Computing Monotone Hulls of Simple Polygons, Patt. Recog. Lett., 1, (1983), 219-222. 13

Appendix program main (input,output); var X,Y: array [0..50] of real; {coordinates of points} V,Z: array [0..50] of integer; {polygon and hull} q,j: integer; {index into polygon and hull} n: integer; {number of vertices} i: integer: {loop index} { Is point p to the left of Line (a,b)? } function left (p,a,b: integer):boolean; begin left:= (Y[p] - Y[a])*(X[b] - X[a]) > (X[p] - X[a])*(Y[b] - Y[a]); end; { Is point p to the right of Line (a,b)? } function right (p,a,b: integer):boolean; begin right:= (Y[p] - Y[a])*(X[b] - X[a]) < (X[p] - X[a])*(Y[b] - Y[a]); end; { Read in the Polygon } procedure readin; var i: integer; W: array [0..50] of integer; mx,my: real; mi: integer; begin { Read in the number of points } repeat write(' Number of points?'); read(n); until (n > 3) and (n < 50); mx:= le38; my:= le38; { While reading in vertices, find an extremal one } for i:= 0 to n-l do begin write('',i:3,':'); read(X[i],Y[i]); W[i]:= i; if (Y[i] my) or ((Y[i] = my) and (X[i] < mx)) then begin mx:= X[i]; my:= Y[i]; mi:= i; end; end; 14

{ Reorder with an extreme vertex first } V[n]:=W[mi]; for i:= 0 to n-1 do begin V[i]:= W[mi]; mi:= (mi + 1) mod n; end; end; begin { Get the polygon, and echo it back } readin; writeln(' Polygon:'); for i:= 0 to n-l do writeln('',1:3,':',X[V[i]]:10:5,',',Y[V[i]]:10;5); {Step 0} q:= 1;.i:= 1; Z[0]:= V0]; Z[1]:= V[1]; while (q < n) do if right ( V[q+l], Z[j-l], Z[j] ) then if right ( V[q+l], V[q-l], V[q] ) then begin { Step la } j:= j + 1; q:= q + 1; Z[j]:= V[q]; end else { Step lb while not left ( V[q+l], Z[j-l], Z[j] ) do q:= q + 1; else begin { Step 2 } while j > 0 and not right ( Z[j-l], Z[j], V[q+l] ) do j:= j - 1; j:= j + 1; q:= q + 1; z[j]:= V[q]; end; { Print the hull } writeln(' Hull:'); for i:= 0 to j-l do writeln('',i:3,':',X[Z[i]]:10:5,',',Y[Z[i]]:10:5); end. 15