Given a set of points on a 2 dimensional plane, a Convex Hull is a geometric object, a polygon, that encloses all of those points. The vertices of this polygon maximize the area while minimizing the circumference.
Note that if some additional points were to be included, then the covering area is reduced while the circumference is increased. Likewise, if some of the vertices of the Convex Hull are omitted, then the resulting polygon won’t cover all of the points in the set.
The Convex Hull has a wide variety of applications, ranging from image recognition in robotics to determining animal’s home range in ethology. And in this tutorial we are going to look at how to calculate the Convex Hull using two different algorithms. The first one is called “Graham Scan” while the second is called “Jarvis March”, also known as "gift wrapping algorithm". Both of them are conceptually fairly simple, but there are a few tricky implementation pitfalls that I will point out.
Graham Scan algorithm (en.wikipedia.org/wiki/Graham_...) starts by first looping over all of the points to select the one with the lowest Y coordinate. This is the bottom most point and, assuming no collinear points, is therefore guaranteed to be one of the vertices of the Convex Hull. Of course, it could just as well pick the top most or the leftmost or the rightmost point, but by convention it picks the bottom most.
Then it sorts the remaining points, ordering them by the angle that they make relative to the bottom most point and the horizontal. You can see that the angles would range from 0 to 180 degrees, given that the reference point is the bottom most one in the set.
Finally, the algorithm loops over those points in sorted order, effectively scanning in the counterclockwise direction. Each point is placed on a stack, but only if it makes a line with a counterclockwise turn relative to the previous 2 points on the stack. If that is not the case, then the previous point is popped off the stack. The algorithm continues popping points off of the stack until the resulting turn is counterclockwise.
Graham Scan Java source code:
bitbucket.org/StableSort/play...
Let’s talk about some of the implementation details that you’ll need to handle. First of all, to determine if it’s a clockwise turn or not, you could calculate the degrees of the angles using trigonometry and then compare them. But we don’t really care what the actual angles are. We just want to know if it’s a clockwise turn or not. To do just that and save a few CPU cycles in the process, we can make use of a cross product.
If you don’t recall, the cross product of two vectors V & W calculates the signed area of the parallelogram that is formed if you connect the two vectors like so. If V is on the right of W, then the cross product ends up positive. But if V is on the left of W, then it’s negative.
Now that we covered the Graham Scan algorithm, we can talk about its cousin, the Jarvis March (en.wikipedia.org/wiki/Gift_wr..., which is actually a little simpler. It also starts off by finding the lowest point on the y-axis for its 1st vertex.
But then, instead of doing any kind of sorting, it just loops through all of the points again in a brute force way to find the point that makes the smallest counterclockwise angle in reference to the previous vertex. It simply repeats this iteration through all of the points until all of the vertices are determined and it gets back to the starting point.
Jarvis March source code in Java:
bitbucket.org/StableSort/play...
Looping through every point for each vertex may seem like a lot more inefficient, but the algorithm terminates as soon as it finds all of the vertices. This means that if the number of vertices is small, in particular, less than log of n, then it’ll perform better than the Graham Scan algorithm.
More formally, the running time of Jarvis March is O(n * h) where h is the number of vertices.
Of course, if the number of vertices is large, such as when all of the points are along the perimeter, then the running time turns for the ugly of O(n^2).
By the way, the function for finding the point with the smallest counterclockwise angle is exactly the same as the one used previously that makes use of the cross product. As a little bonus, dealing with collinear points is a little easier because here you just need to pick the point that is furthest away distance wise, without needing to worry about the slope of the line.
Timothy Chan’s paper for divide and conquer algorithm:
link.springer.com/content/pdf...
Written and narrated by Andre Violentyev