A long, long time ago I had an interview for a video game company where I was asked to solve a problem that amounted to the convex hull problem. Needles to say, I didn't get the job but it was a fun exercise in computational geometry. This is the touched up code that I submitted. I've included a short tutorial on what the convex hull is, and how to solve it - in case you're in the middle of an interview and in a jam.
If you've run across this project, chances are you need to create a bounding box around some polygon. At this point, you may not know what a convex hull is but don't worry-we'll define it before digging into the code. In short, a convex hull is the outer most points on a polygon. Some applications (like the bounding box) only need the outer-most parts of the polygon to accomplish some task. Note that polygons are 2-dimensional. When we extend out to 3 dimensions, we are no longer dealing with vanilla polygons, but polyhedrons.
Consider the two polygons below. If we are interested in the global features of polygon A, we can see that the jagged right side does not contribute to its size. The convex hull of polygon A is polygon B. Note that we discarded the points on the jagged side and instead connected the two exterior points.
First, let's identify the concave line segments; this is shown in polygon A in the figure below. The two red line segments are concave, along with the two green line segments. Removing the two vertices, we arrive at polygon B. Note that there is a larger concave segment, colored red in polygon C. Once removing the vertex, we arrive at polygon D: the convex hull. Note that all vertices are convex.
To emphasize the convex/convex difference, refer to the image below. The first shows a concave segment. The second highlighted segment is convex.
Now that we have the basic vocabulary down, we can define what a convex polygon is. Math Open Reference defines a convex polygon as
Definition: A polygon that has all interior angles less than 180° (Result: All the vertices point 'outwards', away from the center.)
Looking back at the example pictures above, you will notice that the convex line segments are all 180° or higher. We can use the last example to illustrate.
The first polygon has vertices that have connecting line segments that are all greater 180°, it is convex. Note that we can pick any two points and draw a line that is completely contained in the polygon. The second polygon however, has an angle (B) which is less than 180°. We can take two points and connect a line which falls outside the polygon border. This polygon is concave.
The goal of a convex hull algorithm is to take a polygon, and give the set of vertices that gives the smallest convex polygon. The more common convex hull algorithms are listed below.
| Algorithm | Complexity | Worst Case | Algorithm Alias | Date Published |
|---|---|---|---|---|
| Grahm Scan | O(n) | 1972 | ||
| Monotone Chain | O(n) (When sorted) | O(nlog(n)) | Andrew's Algorithm | 1979 |
| Quickhull | O(nlog(n)) | O(n2) | 1977 | |
| Gift Wrapping | O(nh) | O(n2) | Jarvis March | 1970 |
| Chan's Algorithm | O(nlog(n) | 1996 | ||
| Kirkpatrick–Seidel | O(nlog(h)) | the ultimate planar convex hull algorithm | 1986 | |
| Incremental Convex Hull Algorithm | O(nlog(n)) | 1984 |
All of the repositories use the same structure: a Coordinate class and a ConvexHull class. The Coordinate class is identical throughout the projects. You will commonly see
std::vector polygon
defining the polygon that will be passed to the algorithm. The first step is creating a vector of coordinates.
There is also a Polygon class, which has a member function that computes the convex hull. The Polygon constructor takes a vector of coordinates, and stores it internally. In case you don't want to keep the original polygon around, you may use the move constructor. The second step is creating this polygon class, and passing the set of polygon points to it.
To compute the convex hull, call
Polygon::ComputeConvexHull()
which returns a vector of coordinates defining the convex polygon.
This project computes the convex hull by using the Graham Scan. This implementation assumes that the points are not sorted, which restricts the complexity time to O(nlogn). The complexity time of the convex hull algorithm itself is O(n). If you have points that are already sorted, you can remove the sorting routines.
To build, run the following from the ./build directory.
cmake ..
cmake --build .
You can now run the program with
./convex-hull
If you need to use some of this code in your own code, here are a few tips.