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, we set pc to
pi only if pi is
further from p0 than
pc. Thus, once we have traversed all of the
points in the list, pc is the point that is
clockwise to all others with respect to p0.
At this point, we reset p0 to
pc and repeat the process until
p0 is the point at which we started. Once
we reach this point, all points in the convex hull have been inserted
into polygon at the top of the outer
loop.
The runtime complexity of cvxhull is O (nh), where n is the total number of points, and h is the number of points in the convex hull. The loop in which the lowest point is determined runs in O (n) time because we must traverse all points to determine which is the lowest. The nested loops together are O (nh) because for each point inserted into the convex hull, we must traverse all other points to determine which is next to insert. Since locating the lowest point and constructing the convex hull are carried out sequentially, the runtime complexity of cvxhull is O (nh).
/***************************************************************************** * * * ------------------------------- cvxhull.c ------------------------------ * * * *****************************************************************************/ #include <math.h> #include <stdlib.h> #include "geometry.h" #include "list.h" /***************************************************************************** * * * -------------------------------- cvxhull ------------------------------- * * * *****************************************************************************/ int cvxhull(const List *P, List *polygon) { ListElmt *element; Point *min, *low, *p0, *pi, *pc; double z, length1, length2; int count; /***************************************************************************** * * * Find the lowest point in the list of points. * * * *****************************************************************************/ min = list_data(list_head(P)); for (element = list_head(P); element != NULL; element = list_next(element)) { p0 = list_data(element); /************************************************************************** * * * Keep track of the lowest point thus far. * * * **************************************************************************/ if (p0->y < min->y) { min = p0; low = list_data(element); } else { /*********************************************************************** * * * If a tie occurs, use the lowest and leftmost point. * * * ***********************************************************************/ if (p0->y == min->y && p0->x < min->x) { min = p0; low = list_data(element); } } } /***************************************************************************** * * * Initialize the list for the convex hull. * * * *****************************************************************************/ list_init(polygon, NULL); /***************************************************************************** * * * Perform Jarvis's march to compute the convex hull. * * * *****************************************************************************/ p0 = low; do { /************************************************************************** * * * Insert the new p0 into the convex hull. * * * **************************************************************************/ if (list_ins_next(polygon, list_tail(polygon), p0) != 0) { list_destroy(polygon); return -1; } /************************************************************************** * * * Find the point pc that is clockwise from all others. * * * **************************************************************************/ count = 0; for (element = list_head(P); element != NULL; element = list_next(element)) { /*********************************************************************** * * * Skip p0 in the list of points. * * * ***********************************************************************/ if ((pi = list_data(element)) == p0) continue; /*********************************************************************** * * * Count how many points have been explored. * * * ***********************************************************************/ count++; /*********************************************************************** * * * Assume the first point to explore is clockwise from all others * * until proven otherwise. * * * ***********************************************************************/ if (count == 1) { pc = list_data(element); continue; } /*********************************************************************** * * * Determine whether pi is clockwise from pc. * * * ***********************************************************************/ if ((z = ((pi->x - p0->x) * (pc->y - p0->y)) - ((pi->y - p0->y) * (pc->x - p0->x))) > 0) { /******************************************************************** * * * The point pi is clockwise from pc. * * * ********************************************************************/ pc = pi; } else if (z == 0) { /******************************************************************** * * * If pi and pc are collinear, select the point furthest from p0. * * * ********************************************************************/ length1 = sqrt(pow(pi->x - p0->x, 2.0) + pow(pi->y - p0->y, 2.0)); length2 = sqrt(pow(pc->x - p0->x, 2.0) + pow(pc->y - p0->y, 2.0)); if (length1 > length2) { /***************************************************************** * * * The point pi is further from p0 than pc. * * * *****************************************************************/ pc = pi; } } } /************************************************************************** * * * Prepare to find the next point for the convex hull. * * * **************************************************************************/ p0 = pc; /************************************************************************** * * * Continue until reaching the lowest point again. * * * **************************************************************************/ } while (p0 != low); return 0 ; }