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 ; }