Convex Hull | Set 1 (Jarvis's Algorithm or Wrapping) | GeeksforGeeks

Convex Hull | Set 1 (Jarvis's Algorithm or Wrapping) | GeeksforGeeks
Given a set of points in the plane. the convex hull of the set is the smallest convex polygon that contains all the points of it.

Gift or Package Wrapping
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 useorientation() 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 don’t 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).

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 don’t 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).

Time Complexity: For every point on the hull we examine all the other points to determine the next point. Time complexity is ?(m * n) where n is number of input points and m is number of output or hull points (m <= n). In worst case, time complexity is O(n 2). The worst case occurs when all the points are on the hull (m = n)

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

    int next[n];

    for (int i = 0; i < n; i++)

        next[i] = -1;

    // 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

    int p = l, q;

    do

    {

        // Search for a point 'q' such that orientation(p, i, q) is

        // counterclockwise for all points 'i'

        q = (p+1)%n;

        for (int i = 0; i < n; i++)

          if (orientation(points[p], points[i], points[q]) == 2)

             q = i;

        next[p] = q;  // Add q to result as a next point of p

        p = q; // Set p as q for next iteration

    } while (p != l);

    // Print Result

    for (int i = 0; i < n; i++)

    {

        if (next[i] != -1)

           cout << "(" << points[i].x << ", " << points[i].y << ")\n";

    }

}

Time Complexity: For every point on the hull we examine all the other points to determine the next point. Time complexity is  where n is number of input points and m is number of output or hull points (m <= n). In worst case, time complexity is O(n ²). The worst case occurs when all the points are on the hull (m = n)
Java Program to Implement Jarvis Algorithm
private boolean CCW(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 false;
return true;
}

public void convexHull(Point[] points) {
int n = points.length;
/** if less than 3 points return **/
if (n < 3)
return;
int[] next = new int[n];
Arrays.fill(next, -1);

/** find the leftmost point **/
int leftMost = 0;
for (int i = 1; i < n; i++)
if (points[i].x < points[leftMost].x)
leftMost = i;
int p = leftMost, q;
/** iterate till p becomes leftMost **/
do {
/** wrapping **/
q = (p + 1) % n;
for (int i = 0; i < n; i++)
if (CCW(points[p], points[i], points[q]))
q = i;

next[p] = q;
p = q;
} while (p != leftMost);

/** Display result **/
display(points, next);

}
public void display(Point[] points, int[] next) {
System.out.println("\nConvex Hull points : ");
for (int i = 0; i < next.length; i++)
if (next[i] != -1)
System.out
.println("(" + points[i].x + ", " + points[i].y + ")");

}
http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
Read full article from Convex Hull | Set 1 (Jarvis's Algorithm or Wrapping) | GeeksforGeeks