Do you think IIT Guwahati certified course can help you in your career?
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.
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:
The convex hull in which all the points lie on the boundary or inside of it looks something like this:
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.
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:
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.
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
Call the ‘convex_hull’ function for the given set of points.
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.
From this ‘left_idx’, we must find the leftmost point in our convex hull. To achieve this, we can do the following:
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’.
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.
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’.
Now, update the ‘curr_idx’ to ‘next’ and repeat the 2nd step.
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:
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.
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
Using this formula, we will calculate the values of the ‘check_direction’ function for other iterations.
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.
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.
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.
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.
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.
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.
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.
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.
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;
}
You can also try this code with Online C++ Compiler
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);
}
}
}
You can also try this code with Online Java Compiler
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).
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.
242+ registered 
