*Mark Nelson is a contributing editor to Dr. Dobb's Journal. He can be contacted at marknelson.us.*

Finding the Convex Hull of a set of points is an interesting problem in computational geometry. It is useful as a building block for a diverse set of applications, including things such as:

- Collision detection in video games, providing a useful replacement for bounding boxes.
- Visual pattern matching/object detection
- Mapping
- Path determination

Just as an example, consider if one of the Mars rovers has to chart a path around a boulder. The convex hull can be used to provide the shortest path past the obstacle, given a map that shows the points where the boulder abuts the ground.

In this article, I review the definition of the 2D convex hull, describe Graham's efficient algorithm for finding the convex hull of a set of points, and present a C++ program that you can use to experiment with the algorithm.

### The Convex Hull

There are many ways to draw a boundary around a set of points in a two-dimensional plane. One of the easiest to implement is a bounding-box, which is a rectangle that spans the set from its minimum and maximum points in the X and Y planes.

Creating a bounding-box is easy, but it doesn't form as tight a wrapper as we might like around a set of points. Consider the bounding box around the three points in Figure 1.

You can certainly wrap those points much more tightly using easy-to-compute straight lines, and Figure 2 shows an example that is significantly more compact:

As it happens, Figure 2 is a convex hull.

So what is the definition of a convex hull? The common visualization analogy for a 2D convex hull is to imagine the set of points on the plane as nails pounded into a board. If you wrap the entire set in an appropriately sized rubber band, the band snaps into place, forming a convex hull, which is the minimum-energy wrapper that encloses all the points.

An informal definition that has a little more precision but is still easy to understand might say that the convex hull meets the following properties:

- The hull is a cycle graph whose vertices are composed of a subset of the the points in set
**S**. - No points in
**S**lie outside the graph. - All interior angles in the graph are less than 180 degrees.