Gift Wrap Algorithm (Jarvis March Algorithm) to find Convex Hull

Reading time: 25 minutes | Coding time: 10 minutes

In this article, we have explored the Gift Wrap Algorithm ( Jarvis March Algorithm ) to find the convex hull of any given set of points.

Convex Hull is the line completely enclosing a set of points in a plane so that there are no concavities in the line. More formally, we can describe it as the smallest convex polygon which encloses a set of points such that each point in the set lies within the polygon or on its perimeter.

The convex hull is a ubiquitous structure in computational geometry. Even though it is a useful tool in its own right, it is also helpful in constructing other structures like Voronoi diagrams, and in applications like unsupervised image analysis.

We can visualize what the convex hull looks like by a thought experiment. Imagine that the points are nails sticking out of the plane, take an elastic rubber band, stretch it around the nails and let it go. It will snap around the nails and assume a shape that minimizes its length. The area enclosed by the rubber band is called the convex hull of . This leads to an alternative definition of the convex hull of a finite set of points in the plane: it is the unique convex polygon whose vertices are points from and which contains all points of .

In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points

In the two-dimensional case the algorithm is also known as Jarvis march after R. A. Jarvis, who published it in 1973; it has O(nh) time complexity, where n is the number of points and h is the number of points on the convex hull.

Algorithm

The idea of Jarvis’s Algorithm is simple,

We start from the leftmost point (or point with minimum x coordinate value) and we keep wrapping points in counterclockwise direction.

The big question is, given a point p as current point, how to find the next point in output?

The idea is to use orientation() here. Next point is selected as the point that beats all other points at counterclockwise orientation, i.e., next point is q if for any other point r, we have “orientation(p, r, q) = counterclockwise”.

Following is the detailed algorithm.

1) Initialize p as leftmost point.
2) Do following while we do not come back to the first (or leftmost) point.
     a) The next point q is the point such that the triplet (p, q, r) is counterclockwise for any other point r.
     b) next[p] = q (Store q as next of p in the output convex hull).
     c) p = q (Set p as q for next iteration).

Pseudocode

The pseudocode of Gift Wrap Algorithm ( Jarvis March Algorithm ) is as follows:

jarvis(S)
   // S is the set of points
   pointOnHull = leftmost point in S //which is guaranteed to be part of the Hull(S)
   i = 0
   repeat
      P[i] = pointOnHull
      endpoint = S[0]      // initial endpoint for a candidate edge on the hull
      for j from 1 to |S|
         if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint)
            endpoint = S[j]   // found greater left turn, update endpoint
      i = i+1
      pointOnHull = endpoint
   until endpoint == P[0]      // wrapped around to first hull point

Animation of Gift Wrap Algorithm ( Jarvis March Algorithm ):

Implementations

Implementation of Gift Wrap Algorithm ( Jarvis March Algorithm ) in C++ is as follows:

• C++

// A C++ program to find convex hull of a set of points
#include <bits/stdc++.h>
using namespace std; 
struct Point					// To store the co-ordinates of every point
{
    int x, y;
} ;
// To find orientation of ordered triplet (p, q, r).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p, Point q, Point r)
{
    int val = (q.y - p.y) * (r.x - q.x) -
              (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0; 	 // colinear
    return (val > 0)? 1: 2; 	// clock or counterclock wise
}
// Prints convex hull of a set of n points
void convexHull(Point points[], int n)
	{
    // There must be at least 3 points
    if (n < 3) return;
    // Initialize Result
    vector<Point> hull;
    // Find the leftmost point
    int l = 0;
    for (int i = 1; i < n; i++)
        if (points[i].x < points[l].x)
            l = i;
    // Start from leftmost point, keep moving counterclockwise
    // until reach the start point again.  This loop runs O(h)
    // times where h is number of points in result or output.
    int p = l, q;
    do
    {
        // Add current point to result
        hull.push_back(points[p]);
        // Search for a point 'q' such that orientation(p, x,
        // q) is counterclockwise for all points 'x'. The idea
        // is to keep track of last visited most counterclock-
        // wise point in q. If any point 'i' is more counterclock-
        // wise than q, then update q.
        q = (p+1)%n;
        for (int i = 0; i < n; i++)
        {
           // If i is more counterclockwise than current q, then
           // update q
           if (orientation(points[p], points[i], points[q]) == 2)
               q = i;
        }
        // Now q is the most counterclockwise with respect to p
        // Set p as q for next iteration, so that q is added to
        // result 'hull'
        p = q;
    } while (p != l);  // While we don't come to first point
    // Print Result
    for (int i = 0; i < hull.size(); i++)
        cout << "(" << hull[i].x << ", "
              << hull[i].y << ")\n";
}
// Driver program to test above functions
int main()
{
    Point points[] = {{0, 3}, {2, 2}, {1, 1}, {2, 1},
                      {3, 0}, {0, 0}, {3, 3}};
    int n = sizeof(points)/sizeof(points[0]);
    convexHull(points, n);
    return 0;
}

Complexity

• Worst case time complexity: Θ(N ^ 2)
• Average case time complexity: Θ(N log N)
• Best case time complexity: Θ(N log N)
• Space complexity: Θ(N)

The inner loop checks every point in the set S, and the outer loop repeats for each point on the hull. Hence the total run time is O(nh).
The run time depends on the size of the output, so Jarvis's march is an output-sensitive algorithm.
In worst case, time complexity is O(n^2). The worst case occurs when all the points are on the hull (h = n)

Applications

The applications of this Divide and Conquer approach towards Convex Hull is as follows:

• Collision avoidance: If the convex hull of a car avoids collision with obstacles then so does the car. Since the computation of paths that avoid collision is much easier with a convex car, then it is often used to plan paths.

• Smallest box: The smallest area rectangle that encloses a polygon has at least one side flush with the convex hull of the polygon, and so the hull is computed at the first step of minimum rectangle algorithms. Similarly, finding the smallest three-dimensional box surrounding an object depends on the 3D-convex hull.

• Shape analysis: Shapes may be classified for the purposes of matching by their "convex deficiency trees", structures that depend for their computation on convex hulls.

• Other practical applications are pattern recognition, image processing, statistics, geographic information system, game theory, construction of phase diagrams, and static code analysis by abstract interpretation.

• It also serves as a tool, a building block for a of other computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.

Question

Question on Gift Wrap Algorithm ( Jarvis March Algorithm ) is as follows: