Convex hull – Gift wrapping algorithm in C#

A C# implementation of the Gift wrapping method (also known as Jarvis march) for computing the convex hull of a set of points.

Algorithm

Given a set of points P, the algorithm initially selects the leftmost point p1 which will belong to the convex hull.
It then proceeds to find the rest of the points belonging to the convex hull. A vertical line is taken about the p1 and rotated clockwise until it meets another point p2, which is added to the convex hull set. Taking p2 as the origin, the line continues to rotate clockwise until it meets another point p3 and so on. The algorithm terminates when it reaches the initial point p1.
However, the actual implementation doesn’t rotate a line. Given the original point p1, the next point p2 is found as follows: The angles between a vertical line about p1 and the lines passing through p1 and each of the candidate points are calculated. The next point p2 of the convex hull is the one that has the smallest angle.
The time complexity of the method is O(nh) where n is the number of points and h the number of points belonging to the convex hull. It is an output-sensitive algorithm, since the running time depends on the number of points that belong to the convex hull.

Video demonstration

You can find a Python implementation of the gift wrapping method here.