Mastering Algorithms With C - Kyle Loudon [217]
Returning to the peg analogy, in the right chain, selecting each point pc is similar to tying a string to the current p 0, pulling it taut to the right, and then advancing the string counterclockwise until it touches another point. In the left chain, the process is similar to pulling the string taut to the left before advancing it counterclockwise. Figure 17.4 illustrates this process.
Figure 17.4. Computing the convex hull for a set of 10 points
Computationally, to determine the point clockwise from all other points with respect to p 0, we traverse each point pi in P, except p 0, and keep track of the best choice for pc as we go. For each pi in P, we compare the orientation of pi relative to the pc we have found thus far using the expression for z that follows. If z is greater than 0, pi is clockwise from pc with respect to p 0, and we reset pc to the current pi . One nice thing about this approach is that we do not need to worry about whether we are computing the right or left chain, as the mathematics handles this for us.
z = ( xi - x 0 ) ( yc - y0 ) - ( yi - y0 ) ( xc - x0 )
One special case occurs when z is 0. This means that pi and pc are collinear with respect to p 0. In this case, the most clockwise point is considered to be the one furthest from p 0 (in Figure 17.4, see the computation of z where p 0 = (-2, -4), pi = (0, -2), and pc = (2, 0) in step 1, and where p 0 = (-3, 4), pi = (-3, 2), and pc = (-3, -1) in step 3). To determine the distance r between p 0 = (x 0, y 0 ) and a point p j = (x j , y j ), where pj is either pi or pc , we use the following equation:
Interface for Convex Hulls
Name
cvxhull
Synopsis
int cvxhull(const List *P, List *polygon);
Return Value
0 if computing the convex hull is successful, or -1 otherwise.
Description
Computes the convex hull for a list of points specified in P. Each element in P must be of type Point . Since the cvxhull operation works in two dimensions, like lint, it ignores the z-coordinate in each Point structure. The convex hull is returned in polygon, which is a list of Point structures. The elements in polygon point to the actual points in P, so the caller must ensure that the storage in P remains valid as long as polygon is being accessed. Use list_destroy to destroy polygon once it is no longer needed.
Complexity
O (nh), where n is the total number of points, and h is the number of points in the convex hull.
Implementation and Analysis of Convex Hulls
To compute the convex hull of a set of points, we begin with a list containing each point. Each point in the list is a Point structure. This structure consists of three members, x, y, and z, which are the coordinates of a point. Recall that we ignore all z-coordinates since the operation works in two dimensions.
The cvxhull operation (see Example 17.3) begins by locating the lowest point passed to it in P. To determine this, we traverse all points while keeping track of which has the smallest y-coordinate. If two points share the smallest y-coordinate, we choose the point that has the smallest x-coordinate. This results in the lowest and leftmost point. Once we have identified this point, we set p0 to it.
The actual process of constructing the convex hull takes place within a nested loop. At the start of the outer loop, we insert p0 into the convex hull. On the first iteration of the loop, p0 is the lowest point. As the algorithm progresses, each successive iteration of the outer loop yields a new p0. Within the inner loop, we traverse each point pi in P to determine the next p0. Specifically, as we traverse each point, pc maintains the point determined to be clockwise from all others thus far with respect to the current p0. To determine whether a given pi is clockwise from the current pc, we use the method presented earlier. That is, if z is greater than 0, pi is clockwise from pc, in which