## 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, ...