Implementation of the Graham scan method to find the convex hull of a series of points in rust. For use in my graph transportation network problem to find the two points with the greatest distance in O(nlog(n)) time.
A convex hull of a shape is defined as the smallest number of points required to enclose the remaining points. The convex hull has many applications in Maths, Statistics, Physics and Computer science.
Graham scan algorithm finds the convex hull of a series of points in O(n log(n)) time. It does so by calculating the angle between every point and the lowest point, and then sorting in ascending order. The sorted algorithms are iterated through with three points at a time being tested for whether they for a clockwise or anti clockwise angle.
Assuming the input length is greater than 3.
1. Find the lowest / furthest left point -> min.
2. Calculate the angle between each point and min using atan2().
3. Sort the points by angle in ascending order -> sorted.
4. Take the first two values from sorted and add them to a stack.
5. Foreach remaining value from sorted:
6. Take top two values from stack and point.
7. Calculate if the three points make a clockwise of counter clockwise turn.
8. If clockwise pop stack and recalculate turn, repeating step 7.
9. If anti clockwise add point to stack
10. Return stack.