Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Convex Hull
2.
Problem Statement
2.1.
Input
2.2.
Output
2.3.
Explanation
3.
Solution Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity  
4.
Frequently Asked Questions
4.1.
What do you mean by a convex hull?
4.2.
What is the angle between any two points in the convex hull?
4.3.
What is the time and space complexity of Jarvis’s Algorithm to compute the convex hull?
4.4.
What are the different ways to compute the convex hull of a given set of points?
4.5.
What are the applications of the convex hull algorithm?
5.
Conclusion
Last Updated: Mar 27, 2024
Hard

Convex Hull (Jarvis’s Algorithm)

Author Sahil Setia
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Geometry problems are significant from a data structures and algorithms point of view. Various types of issues can be solved using geometry algorithms and knowledge. Numerous algorithms are used in geometry and polygon problems, which are essential from an interview point of view.

title image

In this blog, we will learn about implementing a convex hull using Jarvis’s algorithm. But, before diving into the problem statement or solution, let’s first get a brief introduction about the convex hulls.

Convex Hull

A line that entirely encloses a group of points on a plane without any concavities is said to have a convex hull. In simple words, It is referred to as the ‘smallest convex polygon’, and it has a set of points, each of which is contained within or next to the polygon. The smallest convex shape, or convex shape covering the smallest area or volume in geometry, encompasses all the points present in a plane. 

For example, let’s look at the following set of points:

Intro image 1

The convex hull in which all the points lie on the boundary or inside of it looks something like this:

Intro image 2

Now, that we have a brief understanding of the convex hull, let’s focus on the implementation of this convex hull algorithm. We can implement this algorithm by using divide and conquer and using a monotone chain algorithm. 

In this blog, we will use Jarvis’s Algorithm to compute the convex hull of the given set of points. Before diving into the solution, let’s briefly examine the problem statement once again.

Problem Statement

Given a set of some points given in a 2-D plane, our task is to find out the convex hull of the given set of points, i.e., all the points that constitute the boundary of the convex hull of the given set of points.
 

Note: All the given points are unique, i.e., no two points coincide. 

Input

Total number of points = 7

Points = [[3, 0], [4, 2], [0, 7], [4, 4], [2, 3], [5, 6], [2, 8] ]
 

The given input looks like this:

Input image

Output

Points in the convex hull are : (0, 7), (2, 8), (3, 0), (4, 2), (5, 6) 

Explanation

Diagrammatically, the convex hull looks something like this:

Explanation image

The red lines contain the coordinates of the points which lie in the convex hull and all the points lie on the boundary or inside the convex hull. Hence, the convex hull is logically correct.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Solution Approach

In the solution approach, the Jarvis march algorithm is used to compute the convex hull of the given set of points. Given a set of data points, the Jarvis March technique is used to identify the corner points of a convex hull. 

In general, we start from the leftmost point in the data set, rotate the points clockwise or anticlockwise to keep them in the convex hull when the angle is significant, and then from the current point, select the following point by examining the direction of the points relative to the current point. Once all the points have been completed, the leftmost point becomes a  starting point, and the operation is stopped. 

To locate the convex hull, Jarvis's march method uses a technique known as gift wrapping. Convex hull computation using this approach is among the easiest.

Algorithm

  1. Call the ‘convex_hull’ function for the given set of points.
     
  2. Find the leftmost point, i.e., the point with the minimum x coordinate, and store it in variable ‘left_idx’ as it will lie in the convex hull of the given set of points.
     
  3. From this ‘left_idx’, we must find the leftmost point in our convex hull. To achieve this, we can do the following:

    1. We start from the leftmost index ‘left_idx’ and take the ‘next’ point from the available set of points. Using these two points, we look for the point which is more clockwise from the current point. In this manner, we advance ‘next’ to the left throughout each iteration, stopping when ‘next’ is in the position that is farthest to the left of ‘left_idx’.

      1. For checking any two points regarding which one is more anti-clockwise with respect to the ‘curr_idx’, we call the ‘check_direction’ function, which simply uses the slope concept between two lines to return the same.
         
    2. After extracting the leftmost index of our current index, ‘curr_idx’, we insert all the collinear points with the current point ‘curr_idx’ into our set ‘curr_set’.
       
  4. Now, update the ‘curr_idx’ to ‘next’ and repeat the 2nd step.
     
  5. Repeat the steps mentioned above 2 and 3 until we reach the point from where the process starts, and here, we will break our loop as we have computed our convex hull for the given set of points.

Dry Run

Given a set of points looks like this:

Dry run image 1

Initially, we pick the leftmost point, i.e., the point whose x coordinate is minimum among all. In this case, that point is (0, 7). The ‘left_idx’ corresponds to the position of the (0, 7) point in the initial array of points which is equal to 2.

Dry run image 2

Now, we will look for the leftmost point in the clockwise direction from the current point ‘curr_idx’ whose value is equal to (0, 7). From the current point, we will take a reference point ‘next’ generally which is taken as the point with index = ‘curr_idx’ + 1. 

For each point, we will check the value of the corresponding ordered triplet and if it’s less than zero that means that point lies on the left side of the current point in the clockwise direction and we update our ‘next’ with the index we are on. Let’s see a visualization of the above-mentioned thing.
 

The formula for calculating the ‘check_direction’ function is equal to

(b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y)

where, a = point at current index ‘curr_idx’

            b = point at next index ‘next’

            c = point at index ‘i’

In this iteration, the value of the ‘check_direction’ function will be

check_direction = (4 - 7) * (3 - 4)  -  (4 - 0) * (0 - 4) = 3 + 16 = 19 

Using this formula, we will calculate the values of the ‘check_direction’ function for other iterations.

Dry run image 3

Now, as we can see the value for the check_direction function for the triplet is greater than zero hence we will not update our ‘next’ pointer. Moving on to the next iteration.

Dry run image 4

As we can see, the value for the check_direction function for the triplet is greater than zero; hence we will not update our ‘next’ pointer. Moving on to the next iteration.

Dry run image 5

Now, as we can see, the value for the check_direction function for the triplet is equal to zero; hence we will not update our ‘next’ pointer. Moving on to the next iteration.

Dry run image 6

Now, as we can see, the value for the check_direction function for the triplet is equal to zero; hence we will not update our ‘next’ pointer. Moving on to the next iteration.

Dry run image 7

As we can see, the value for the check_direction function for the triplet is greater than zero; hence we will not update our ‘next’ pointer. Moving on to the next iteration.

Dry run image 7

Now, as we can see, the value for the check_direction function for the triplet is less than zero; hence we will update our ‘next’ pointer to point(5,6). Moving on to the next iteration.

Dry run image 8

Now, as we can see, the value for the check_direction function for the triplet is less than zero; hence we will update our ‘next’ pointer to point(2, 8). Our first iteration of finding the leftmost point corresponding to the current pointer is over. Hence, if we join these two points, we get a line as follows.

Dry run image 8

After following the steps mentioned above, for each point until we reach the starting point(0, 7) again. Finally, we get the convex hull of the given set of points as follows.

Dry run image 9

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Struct for storing the points
struct Point{
    public:
    int xc, yc;
    Point(){
        xc=0;
        yc=0;
    }
    
    Point(int x,int y){
        xc=x;
        yc=y;
    }
};

// Comperator for set
struct compare{
    bool operator()(const Point& a, const Point& b) const{
        return a.xc < b.xc or (a.xc == b.xc and a.yc < b.yc);
    }
};

// Function to check the direction is anti-clockwise or not
int check_direction(Point a, Point b, Point c) {
    return (b.yc - a.yc) * (c.xc - b.xc) - (b.xc - a.xc) * (c.yc - b.yc);
        
}

vector <Point> convex_hull(vector <Point>& points){
    
    // Stores all points in the current convex hull
    set <Point, compare> curr_set;
    
    // Contains index of the leftmost point
    int left_idx=0;
    
    int n = points.size();
    
    // Base case for 3 points;
    if(n==3){
        return points;
    }
    
    // Calculating the index of the leftmost index
    for(int i=0;i<n;i++){
        if(points[i].xc<points[left_idx].xc){
            left_idx=i;
        }
    }
    
    // Stores the value of the current index
    int curr_idx=left_idx;
    
    /*
        Base condition of the convex hull,i.e.
        All points lie on the boundary of 
        The convex hull
    */
    while( curr_set.size() != n){
        
        // Checking for the next candidate 
        int next = (curr_idx + 1);
        next %= n;
        
        /*
            Starting from the left_idx
            And then try picking the next
            Point from the available points
            Which is more anti-clockwise from the current point
            And stopping when we come to the same starting point.
        */
        for(int i=0;i<n;i++){
            if(check_direction(points[curr_idx],points[next],points[i]) < 0){
                
                next=i;
            }
        }
        
        /*
            Inserting all the points which 
            Are collinear with current point
        */
        for(int i=0;i<n;i++){
            if(check_direction(points[curr_idx],points[next],points[i]) == 0){
                
                Point c;
                c.xc = points[i].xc;
                c.yc = points[i].yc;
                curr_set.insert(c);
            }
        }
        
        // Updating the current index
        curr_idx = next;
        
        // Reaching the same point again so break
        if(curr_idx == left_idx){
            break;
        }
    }
    
    // Storing and returning the result
    vector <Point> ans;
    
    for(auto i:curr_set){
        ans.push_back(i);
    }
    
    return ans;
}

int main(){
    
    // Total number of the points
    int N = 7;
    
    // Storing the points
    vector <Point> points(N);
    Point a(3,0),b(4,2),c(0,7),d(4,4),e(2,3),f(5,6),g(2,8);
    points[0] = a;
    points[1] = b;
    points[2] = c;
    points[3] = d;
    points[4] = e;
    points[5] = f;
    points[6] = g;
    
    // Calling the function and storing the result
    vector <Point> convex_points=convex_hull(points);
    
    // Displaying the result
    for(auto i:convex_points){
        cout<<i.xc<<" "<<i.yc<<"\n";
    }
    return 0;
}

Output

Output c++

Implementation in Java

import java.util.ArrayList;
import java.util.*;
   
// Class for storing the points
class Point{
        
    int xc, yc;
    Point(int xc, int yc){
        this.xc=xc;
        this.yc=yc;
    }
}

public class MyClass {
    
    // Function to check the direction is anti-clockwise or not
    static int check_direction(Point a, Point b, Point c) {
        return (b.yc - a.yc) * (c.xc - b.xc) - (b.xc - a.xc) * (c.yc - b.yc);
        
    }
    
    static ArrayList<Point> convex_hull(Point points[]){
        
        // Stores all points in the current convex hull
        Set<Point> curr_set = new HashSet<>();
        
        // Contains an index of the leftmost point
        int left_idx=0;
        
        int n = points.length;
        
        // Calculating the index of the leftmost index
        for(int i=0;i<n;i++){
            if(points[i].xc<points[left_idx].xc){
                left_idx=i;
            }
        }
        
        // Stores the value of the current index
        int curr_idx=left_idx;
        
        /*
            Base condition of convex hull,i.e.
            All points lie on the boundary of 
            The convex hull
        */
        while( curr_set.size() != n){
            
            // Checking for the next candidate 
            int next = (curr_idx + 1);
            next %= n;
            
            /*
                Starting from the left_idx
                And then try picking the next
                Point from the available points
                Which is more anti-clockwise from the current point
                And stoping when we come to the same starting point.
            */
            for(int i=0;i<n;i++){
                if(check_direction(points[curr_idx],points[next],points[i]) < 0){
                    
                    next=i;
                }
            }
            
            /*
                Inserting all the points which 
                Are collinear with current point
            */
            for(int i=0;i<n;i++){
                if(check_direction(points[curr_idx],points[next],points[i]) == 0){
                    
                    curr_set.add(points[i]);
                }
            }
            
            // Updating the current index
            curr_idx = next;
            
            // Reaching the same point again so break
            if(curr_idx == left_idx){
                break;
            }
        }
        
        // Returning the result
        return new ArrayList<Point>(curr_set);
    } 
    
    // Driver Function
    public static void main(String args[]) {
        
        // Total number of the points
        int N = 7;
        
        // Storing the points
        Point points[] = new Point[N];
            
        // Adding the points
        points[0] = new Point(3,0);
        points[1] = new Point(4,2);
        points[2] = new Point(0,7);
        points[3] = new Point(4,4);
        points[4] = new Point(2,3);
        points[5] = new Point(5,6);
        points[6] = new Point(2,8);
        
        // Calling the function and storing the result
        ArrayList<Point> convex_points = convex_hull(points);
        
        int sz = convex_points.size();
        
        System.out.println("Points in the convex hull are:");
        // Displaying the result
        for(Point p:convex_points){
            
            System.out.print(p.xc);
            System.out.print(" ");
            System.out.println(p.yc);
        }
    }
}

Output

Output java

Time Complexity

O(N * H), where ‘N’ is the total number of the given set of points and ‘H’ is the number of the points which are in the convex hull set.

Note: H < = N as the total number of the points in the convex hull will always be less than or equal to the total number of the given points.

Explanation: As for each point, we find the leftmost point corresponding to that point in the anti-clockwise direction, and this process goes on until we reach the same point again. So, H being the number of points, and to find the leftmost point, we do N iterations which yield a total time complexity of O(N* H). In the worst case, H can equal N, so the worst-case time complexity is O(N²).

Space Complexity  

O(N + H) where ‘N’ is the total number of the given points and ‘H’ is the total number of the points in the convex hull of the given set of points.

Explanation: O(N) is the space required for storing the points in a 2-D array, and we initialized a set of points to store the points which lie in the convex hull, which required a space of O(H). Hence, the total space required is O(N + H).

Also Read - Kadanes Algorithm

Frequently Asked Questions

What do you mean by a convex hull?

A line that entirely encloses a group of points on a plane without any concavities is said to have a convex hull. In simple words, It is referred to as the smallest convex polygon, and it has a set of points, each of which is contained within or next to the polygon.

What is the angle between any two points in the convex hull?

The angle between any two points must be less than 180 degrees in the convex hull or the convex polygon the points form.

What is the time and space complexity of Jarvis’s Algorithm to compute the convex hull?

The time complexity of Jarvis’s algorithm is O(N * H), and the space complexity of Jarvis’s algorithm is O(N + H), where N is the total number of points and H is the total number of points that lie in the convex hull. 

What are the different ways to compute the convex hull of a given set of points?

The different ways to compute the convex hull are Jarvis’s algorithm, divide and conquer using the median finding approach, Graham scan algorithm, and quick hull approach.

What are the applications of the convex hull algorithm?

Convex hull finds application in computer visualization, pathfinding, geographical information systems, and visual pattern matching. 

Conclusion

In this blog, we discussed ‘Jarvis’s Algorithm’ using which we solved the convex hull problem, the various approaches to solve this problem programmatically, and saw the implementation of the approaches in Java and C++. We also discussed the time and space complexity of both approaches and saw how we used Jarvis’s algorithm to implement the convex hull. 

Recommended Reading:

Do check out The Interview guide for Product Based Companies, as well as some of the popular interview problems, asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!

Previous article
Basic Geometry Knowledge
Next article
Convex Hull Problem using Divide and Conquer Algorithm
Live masterclass