An intuitive understanding of the Convex Hull algorithm: A Golang Implementation
What’s a convex hull ?
Imagine a rubber band being wrapped around the edges of nails randomly nailed on a wooden plank. This rubber band forms the group of nails touching it, known as the convex hull.
Just like the rubber band that wraps around the nails at the edges, forming the group of nails touching it on the wooden plank, the concept of convex hulls can be found in a variety of real-world situations. It is used to compute the visible surface of an object in computer graphics, determine the reachable space of a robot in robotics, segment an image and identify the outline of an object in image processing, and much more. It’s not just limited to technical fields, but also it has been applied in finance for risk management and portfolio optimisation, and even in physics and engineering for solving the movement of solid body in a fluid. In essence, the convex hull concept forms the bounding area that contains a set of points, just like the rubber band around the nails.
In this article, I’ll explain the Convex Hull algorithm and its implementation in Golang using OpenGL and GLFW to visualise the convex hull. I’ll provide clear explanations and examples to give readers an intuitive and in-depth understanding of the algorithm, its concepts, and its potential applications.
An intuitive understanding of the algorithm requires some geometrical concepts. Lets’ discuss the concepts below:
Concept 1: Area of a Triangle
The area of a triangle formed by three points a, b, c is given by the formula:
A = (b.x-a.x)(c.y-a.y) — (c.x-a.x)(b.y-a.y)
This formula uses the Cartesian coordinates of the points, and is also called the Shoelace formula. The formula uses the cross product of two vectors, which is the product of their magnitudes and the sine of the angle between them.
type Point struct {
X, Y float64
}func Area2(a, b, c Point) float64 {
return (b.X-a.X)*(c.Y-a.Y) - (c.X-a.X)*(b.Y-a.Y)
}
The struct Point is a custom data type that stores the x and y coordinates of a point in a 2D plane. It’s a simple struct with two fields of type float64, representing the x and y coordinates respectively. It’s a custom type for storing points in our problem and make it more readable, instead of using two separate variables.
Concept 2: Collinearity
Points are collinear if a straight line can be drawn through them. In other words, the area of three collinear points is zero.
func IsCollinear(a, b, c *Point) bool {
area := area2(a, b, c)
return area == 0.0
}Graham Scan Algorithm
The Graham scan algorithm is a well-known algorithm for computing the convex hull of a set of points in the plane. The algorithm is adapted from the book — Computational Geometry in C
1. Find the rightmost lowest point, P0
2. Sort all other points angularly about P0
In case of tie, delete the point closer to P0
(or all but one copy for multiple points)
3. Init stack with points, P0 & P1 with P1 at the top
4. i = 2
5. while i < n do
if Pi is strictly left of Pt-1,Pt
Push Pi to the stack, i = i + 1
else
Pop stackLet’s discuss the algorithm in detail for an intuitive understanding.
Starting with (1), why should we find the rightmost lowest point to begin with ? Because we’re looking for a point that’s already on the hull. The lowest points gets swapped with the first one ( i.e. P0 = lowest point).
In (2), we sort all the points with respect to P0.
From the figure, we can assert that Angle(P0) < Angle(P1) < Angle(P2). Computing angles require using the Atan2 function which is computationally expensive. There’s actually a better way.
Given two points a & b, we can check if the third point c is on the left of a & b. The rule is, given P0, P1 < P2 IFF area2(P0, P1, P2) > 0 in the counterclockwise direction. In other words, if P2 is left of the line formed by P0 & Pi, then Pi < Pj.
If area2(P0, P1, P2) == 0, then they’re collinear. For collinear points, we ignore the point closer to P0. This could be achieved by calculating distances between P1, P0 & P2, P0. We ignore the point with shorter distance.
The rest of the algorithm goes through the sorted points and checks if the next point on the list is left of the line formed by points Pt-1 & Pt where t indexes the top of the stack. If yes, then push the point to the stack. If not, then pop the stack.
Algorithm Analysis
The Graham scan algorithm is a well-known and efficient algorithm for computing the convex hull of a set of points. Its time complexity is O(nlogn) as it first sorts the points according to angle with respect to a pivot point, then iterates through the sorted points to form the convex hull. It’s simple to implement and is widely used in a variety of fields such as image processing, computer graphics, and robotics. However, it can be sensitive to degenerate cases such as collinear points, and it’s good to handle them properly.
A Sturdy Golang Implementation
Creating a robust implementation for the task of visualising the convex hull requires careful consideration of the data structures, sorting logic and handling collinearity. I opted to use Golang as it’s simple syntax, coupled with its comprehensive standard library, made it an ideal choice for this complex task. Not only is it easy to understand, but also easy to maintain, making it easy to quickly start working on this program with the use of OpenGL and GLFW.
You can find the source code on GitHub at https://github.com/hemantasapkota/go-convexhull and check out the demo video here.
Conclusion
In conclusion, the convex hull algorithm is a powerful and versatile tool that has a wide range of applications in computational geometry. Throughout this article, I aimed to gain a deeper and intuitive understanding of the algorithm and its implementation in Golang. The project provided me an opportunity to learn, experiment, and put the theory into practice. The simplicity and clarity of Golang’s syntax, along with easily available bindings to OpenGL and GLFW, made it an ideal choice for implementing this complex algorithm. The end result is a program that is easy to understand, maintain, and most importantly, can be used to visualise real-world problems. Overall, the experience of learning and coding up the convex hull algorithm was both challenging and enjoyable. I hope this article has helped readers to deepen their understanding of the convex hull algorithm and its implementation in Golang.
References
