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.
