# Building the Convex Hull

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.

Figure 1: A standard bounding box around three points.

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:

Figure 2: A convex hull around the three points from Figure 1.

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.

### More Insights

 To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.