Jarvis's march, also known as the gift wrapping algorithm, is a straightforward method for finding the convex hull of a set of points in a plane. It works by repeatedly selecting the point with the smallest polar angle relative to the current point and adding it to the convex hull.
Select Initial Point: Start by selecting the point with the lowest y-coordinate (or the leftmost point if there are multiple points with the same lowest y-coordinate). This point is guaranteed to be part of the convex hull.
Find Next Point: From the current point, consider all other points in the set. Calculate the polar angle of each point relative to the current point. The polar angle is the angle formed by the line segment connecting the current point and the candidate point with respect to the positive x-axis.
Select Smallest Angle: Choose the point with the smallest polar angle. This point will be added to the convex hull.
Repeat: Set the chosen point as the new current point and repeat steps 2 and 3 until the algorithm reaches the initial point again.
Termination: Once the algorithm returns to the initial point, the convex hull is complete.
The complexity of Jarvis's march algorithm depends on the number of points in the input set. In the worst case, where all points lie on the convex hull, the algorithm has a time complexity of O(nh), where n is the number of points and h is the number of points on the convex hull. However, in practical scenarios, the complexity is often better than the worst case.
Jarvis's march is relatively easy to implement and works well for small or moderately sized point sets. However, it may not be the most efficient algorithm for very large point sets due to its time complexity.