Computational Geometry: Finding a Convex Hull

This section presents efficient geometric algorithms for finding a convex hull for a set of points. Computational geometry is to study the algorithms for geometrical problems. It has applications in computer graphics, games, pattern recognition, image processing, robotics, geographical information systems, and computer-aided design and manufacturing. Section presented a geometrical algorithm for finding the closest pair of points. This section introduces geometrical algorithms for finding a convex hull.

Given a set of points, a convex hull is the smallest convex polygon that encloses all these points, as shown in Figure below (a). 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 below (a) form a convex polygon, but not in Figure below (b), because the line that connects v3 and v1 is not inside the polygon.

A 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, as shown in Figure below (c). This tool allows you to add and remove points and displays the convex hull dynamically.

Many algorithms have been developed to find a convex hull. This section introduces two popular algorithms: the gift-wrapping algorithm and Graham’s algorithm.

Gift-Wrapping Algorithm

An intuitive approach, called the gift-wrapping algorithm, works as shown in steps below:

• Step 1: Given a list of points S, let the points in S be labeled s0, s1, ..., sk. Select the rightmost lowest point S. As shown in Figure below (a), h0 is such a point. Add h0 to list H. (H is initially empty. H will hold all points in the convex hull after the algorithm is finished.) Let t0 be h0.


• Step 2: Let t1 be s0. For every point p in S, if p is on the right side of the direct line from t0 to t1, then let t1 be p. (After Step 2, no points lie on the right side of the direct line from t0 to t1, as shown in Figure below (b).)


• Step 3: If t1 is h0 (see Figure below (d)), the points in H form a convex hull for S. Otherwise, add t1 to H, let t0 be t1, and go back to Step 2 (see Figure below (c)).

The convex hull is expanded incrementally. The correctness is supported by the fact that no points lie on the right side of the direct line from t0 to t1 after Step 2. This ensures that every line segment with two points in S falls inside the polygon.

Finding the rightmost lowest point in Step 1 can be done in O(n) time. Whether a point is on the left side of a line, right side, or on the line can be determined in O(1) time. Thus, it takes O(n) time to find a new point t1 in Step 2. Step 2 is repeated h times, where h is the size of the convex hull. Therefore, the algorithm takes O(hn) time. In the worst-case, h is n.

Graham’s Algorithm

A more efficient algorithm was developed by Ronald Graham in 1972, as shown in steps below.

Step 1: Given a list of points S, select the rightmost lowest point and name it p0. As shown in Figure below (a), p0 is such a point.

Step 2: Sort the points in S angularly along the x-axis with p0 as the center, as shown in Figure below (b). If there is a tie and two points have the same angle, discard the one that is closer to p0. The points in S are now sorted as p0, p1, p2, ..., pn-1.

Step 3: Push p0, p1, and p2 into stack H. (After the algorithm finishes, H contains all the points in the convex hull.)

Step 4:

i = 3;

while (i < n) {

Let t1 and t2 be the top first and second element in stack H;

if (pi is on the left side of the direct line from t2 to t1) {

Push pi to H;

i++; // Consider the next point in S.

}

else

Pop the top element off stack H.

}

Step 5: The points in H form a convex hull.

The convex hull is discovered incrementally. Initially, p0, p1,and p2 form a convex hull. Consider p3. p3 is outside of the current convex hull since points are sorted in increasing order of their angles. If p3 is strictly on the left side of the line from p1 to p2 (see Figure below (c)), push p3 into H. Now p0, p1, p2, and p3 form a convex hull. If p3 is on the right side of the line from p1 to p2 (see Figure below (d)), pop p2 out of H and push p3 into H. Now p0, p1, and p3 form a convex hull and p2 is inside of this convex hull. You can prove by induction that all the points in H in Step 5 form a convex hull for all the points in the input list S.

Finding the rightmost lowest point in Step 1 can be done in O(n) time. The angles can be computed using trigonometry functions. However, you can sort the points without actually computing their angles. Observe that p2 would make a greater angle than p1 if and only if p2 lies on the left side of the line from p0 to p1. Whether a point is on the left side of a line can be determined in O(1) time. Sorting in Step 2 can be done in O(n log n) time using the merge-sort or heap-sort algorithms. Step 4 can be done in O(n) time. Therefore, the algorithm takes O(n logn) time.