Jarvis March Algorithm
It's also called the gift wrapping algorithm and is a simple solution to the convex hull problem. The algorithm starts by choosing the leftmost point as this point is guaranteed to be part of the convex-hull. It then iteratively chooses the point that is reached with the least clockwise rotation. And in this way we get the points of the convex hull. It is analogous to how the edges of a box get covered one by one when a box is gift wrapped.
Jarvis March Main Function
It calls the findInitialOrigin function to find a starting point that is the lowest among the points that have least x-coordinate. It initializes another variable to store the point with the minimum angle in each iteration. It also creates an empty list to store the points that form the convex hull. The function enters a loop inside which: It initializes a variable minAngle to a large value to keep track of the minimum angle found in this iteration. It iterates through all points except the current point to find the next point that forms a counter-clockwise turn in the convex hull boundary.It calculates the angle between the current point and other points using the findAngle function. It compares the calculated angle with the current minimum angle and if the calculated angle is lesser than the current minimum angle then the current minimum angle is updated. It updates the current point to the point found in this iteration. The loop continues till the current point again becomes the initial point. The function then returns the list that stores the points that form the convex hull.