Computing the Convex Hull in Python
Gift Wrapping algorithm & Graham Scan
Imagine a set of nails (represented by points in the plane). Now imagine an elastic rubber band stretched around the them. Then, the convex hull of these nails is merely the shape of the rubber after we let it go:
Formal Definition of the Convex Hull
To compute the convex hull and understand its mathematical properties, we need a more formal definition.
Let’s start first with the definition of a convex set: A subset S of the plane is called convex if and only if for any pair of points p, q in S, the line segment pq is completely contained in S.
The convex hull of a set S is then defined as the smallest convex set that contains S, also defined as the intersection of all convex sets that contain S.
Although we won’t prove it in this article, the convex hull, as we can observe in the first illustration, is a convex polygon. And as it turns out, a natural way to represent a polygon is by listing its vertex in clockwise order.
The problem of finding the convex hull becomes: given a set of points, compute a list that contains the points that represent the convex hull’s edges, listed in clockwise order. Here’s an example:
But how do we find the edges of this polygon?
A first algorithm to compute the convex hull
By inspecting closely the convex hull of any set of points, we could make this ultimate observation:
(p,q) is an edge of CH(S) if and only if each point of S lies
- strictly to the right of the directed line p → q
- on the line segment pq
Thus, we can construct the convex hull using the following algorithm:
From the set E of edges, we can easily construct the list of vertices of the convex hull stored in clockwise order.
- Let L be our sorted list. Initially, it’s empty.
- We pick a random edge from E and add it to the list.
- We then pick the edge whose starting point is the end point of the previous edge.
- We repeat the 3rd step.
This holds true because every vertex of the convex hull appears in two edges, one time as the starting point and the second time as the end point.
But another problem arises: How do we know a point r lies on the right side of a line (p → q)?
Thanks to algebra, we can easily solve this problem using this magical property:
Runtime of the Algorithm
if r lies on the left of line (p->q):O(1)for all other points r: O(n)for all ordered points (p,q) with p != q:O(n²)
So, our first algorithm computes the convex hull of n points in total O(n³) time. This algorithm is painfully slow.
Gift Wrapping Algorithm
The gift-wrapping algorithm computes the convex hull like how a person would wrap a gift. It follows these steps:
- Start with the leftmost vertex and a vertical ray directed downwards.
2. Then rotate it until we hit the next vertex.
3. From that last directed line, we keep rotating until we hit the next vertex.
And we keep going like that until we reach the leftmost point again.
And now you can see why this is called a gift-wrapping algorithm: If you have an object and you want to wrap it in a gift, you start from the left (or right) side and you keep rotating until you get to the beginning again.
Let’s write the Python code for this algorithm. First we need to find the leftmost point:
Then, starting from the leftmost point, until reaching it again, we need to find the point with the lowest angle. Since this point is a vertex of the convex hull, it verifies the property that all other points lie to the left of the directed line (previousVertex(p) -> thisPoint). Hence all we need to do to is look for the point q such that the triplet (p, q, r) is counterclockwise for any other point r.
We first define a helper function that checks whether a triplet is counterclockwise or not:
The rest of the code is as follows:
Let’s test our code:
We obtain:
The complexity of the Gift Wrapping algorithm is O(n*h) where n is the number of input points and h is the number of points of the convex hull. It is thus an output sensitive algorithm: if the convex hull is small it is very fast but if the order of points of the convex hull is O(n) the algorithm runs in O(n²) time, making it slower than some other algorithms.
Graham Scan Algorithm
The algorithm relies on the property:
For a shape to be convex, the CCW (counterclockwise) traversal of the vertices should never require a CW (clockwise) rotation
We can break down the execution of the algorithm into 4 distinct phases:
- Find the point P with the lowest y-coordinate (if duplicates, choose the one with lowest x-coordinate).
2. Sort the remaining points in order of increasing polar angle from P (if duplicates, order by increasing distance from P). We can visualize this like follows:
3. Initialize the hull with the anchor point P and the first element in the sorted list.
4. Iterate over each point in the sorted list and determine if traversing to it from the prior two points in the hull constitutes making a CW or counterclockwise CCW rotation. If CW, backtrack (delete points on hull) until adding this point constitutes a CCW rotation.
Testing our algorithm, we obtain:
It works perfectly well! Here’s a nice visualization of the algorithm:
The complexity of the Graham Scan is O(nlogn), making it better than gift wrapping in the worst case even though they have same running time on the average case.
However, there exists better algorithms to compute the convex hull such as Chan’s algorithm running in O(nlogh). This is the best you can do to compute the convex hull. The algorithm, though quite elegant, is a little bit more complicated than those discussed in this article. I invite you nonetheless to take a look on it as it presents new ideas to tackle the convex hull computing problem.
