Mastering Algorithms with C

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 case we reset pc to pi. If pi and pc are collinear, ...