Computational Geometry: 2D Convex Hull

In computational geometry, of the many problems computer scientists have dealt with is to find the hull of a set of points. There are several approaches for this but the "Graham Scan" algorithm guarantees a performance in time of O(nlog(n)) which  is optimal.

This algorithm makes use of sorting methods such as merge sort because it respects the previous order in subsequent sortings.

Finding the convex hull has many applications in 3d digital content creation tools as well as in image processing and so many other fields.

Since I finished the MOOC on algorithms I wanted to code this algorithm. Nevertheless, the web is full of code for this. In my case, I've followed the approximation held in Algorithms, 4th Edition by Sedgewick. Pseudocode can be found here.

I've had a good time coding this :D!

Here are some results from the video.