2. Given a set of points, a convex hull is the smallest convex polygon that encloses all these points, as shown in Figure 22.8a. A polygon is convex if every line connecting two vertices is inside the polygon. For example, the vertices v0,v1,v2,v3,v4, and v5 in Figure 22.8a form a convex polygon, but not in Figure 22.8b, because the line that connects v3 and v1 is not inside the polygon. (a) A convex hull (b) A nonconvex polygon (c) Convex hull animation Figure 22.8 A convex hull is the smallest convex polygon that contains a set of points. Convex hull has many applications in game programming, pattern recognition, and image processing. Before we introduce the algorithms, it is helpful to get acquainted with the concept using an interactive tool from http://liveexample.pearsoncmg.com/dsanimation/ConvexHull.html, as shown in Figure 22.8c. The tool allows you to add/remove points and displays the convex hull dynamically. Many algorithms have been developed to find a convex hull. An intuitive approach, called the gift-wrapping algorithm, works as follows: Step 1: Given a list of points S, let the points in S be labeled s0,s1,,sk. Select the rightmost lowest point h0 in S as shown in Figure 22.9a. Add ho to the convex hull H.H is a list initially being empty and it will hold all the points in the convex hull after the algorithm is finished. Let to be ho. Step 2: Let t1 be s0. For every point p in S if p is on the right side of the direct line from t0t0t1 then let t1 be p. (After Step 2, no points lie on the right side of the direct line from to to t1, as shown in Figure 22.9b.) Step 3: If t1 is h0 (see Figure 22.9d ), the points in H form a convex hull for S. Otherwise, add t1 to H, let t0 be t1, and go to Step 2 (see Figure 22.9c). Figure 22.9 (a) h0 is the rightmost lowest point in S. (b) Step 2 finds point t. (c) A convex hull is expanded repeatedly. (d) A convex hull is found when t1 becomes h0. A console-based program for finding the convex hull is given to you (mailed separately) Develop a GUl program as shown in Figure 22.8c. Name the program Exercise22_13 (Hint: Do it incrementally. Can you add a point? Can you remove a point? Can you find a convex hull? Can you display a convex hull?)