## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required