Quick Hull Algorithm to find Convex Hull
Get this book > Problems on Array: For Interviews and Competitive Programming
Reading time: 15 minutes  Coding time: 8 minutes
Quickhull is a method of computing the convex hull of a finite set of points in the plane. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its average case complexity is considered to be Î(n * log(n)), whereas in the worst case it takes O(n^2). Quick Hull was published by C. Barber and D. Dobkin in 1995.
The key idea behind QuickHull is that:
When a convex Hull H of a set of points S in known, then the convex Hull H1 of the set of points S1, that is S + a new point P, is computed as follows:
 Let P1 and P2 be the closest point to P in the left and right section respectively
 Remove line P1 to P2 from convex Hull H
 Add lines P1 to P and P to P2 to modified convex hull H to get new convex Hull H1
Algorithm
The QuickHull algorithm is a Divide and Conquer algorithm similar to QuickSort.
Let a[0âŚn1] be the input array of points. Following are the steps for finding the convex hull of these points.
 Find the point with minimum xcoordinate lets say, min_x and similarly the point with maximum xcoordinate, max_x.
 Make a line joining these two points, say L. This line will divide the the whole set into two parts. Take both the parts one by one and proceed further.
 For a part, find the point P with maximum distance from the line L. P forms a triangle with the points min_x, max_x. It is clear that the points residing inside this triangle can never be the part of convex hull.
 The above step divides the problem into two subproblems (solved recursively). Now the line joining the points P and min_x and the line joining the points P and max_x are new lines and the points residing outside the triangle is the set of points. Repeat point no. 3 till there no point left with the line. Add the end points of this point to the convex hull.
Pseudocode
Pseudocode of Quick Hull algorithm to compute the Convex Hull is as follows:
Input = a set S of n points
Assume that there are at least 2 points in the input set S of points
QuickHull (S)
{
// Find convex hull from the set S of n points
Convex_Hull := {}
Find left and right most points, say A & B
Add A & B to convex hull
Segment AB divides the remaining (n2) points into 2 groups S1 and S2
where S1 are points in S that are on the right side of the oriented line from A to B, and
S2 are points in S that are on the right side of the oriented line from B to A
FindHull (S1, A, B)
FindHull (S2, B, A)
}
FindHull (Sk, P, Q)
{
// Find points on convex hull from the set Sk of points
// that are on the right side of the oriented line from P to Q
If Sk has no point, then return.
From the given set of points in Sk, find farthest point, say C, from segment PQ
Add point C to convex hull at the location between P and Q .
Three points P, Q and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2
where S0 are points inside triangle PCQ,
S1 are points on the right side of the oriented line from P to C
S2 are points on the right side of the oriented line from C to Q
FindHull(S1, P, C)
FindHull(S2, C, Q)
}
Output = Convex Hull
Follow the following illustrative example of Quick Hull algorithm:
Steps 12: Divide points in two subsets
Steps 35: Find maximal distance point, ignore points inside triangle and repeat it
Step 6: Recurse until no more points are left
Implementations
 C++
C++
include <bits/stdc++.h>
using namespace std;
// Part of Cosmos by OpenGenus Foundation
// C++ program to implement Quick Hull algorithm to find convex hull.// iPair is integer pairs
define iPair pair<int, int>
// Stores the result (points of convex hull)
sethull; // Returns the side of point p with respect to line
// joining points p1 and p2.
int findSide(iPair p1, iPair p2, iPair p)
{
int val = (p.second  p1.second) * (p2.first  p1.first) 
(p2.second  p1.second) * (p.first  p1.first);if (val > 0) return 1; if (val < 0) return 1; return 0;
}
// Returns the square of distance between
// p1 and p2.int dist(iPair p, iPair q)
{
return (p.second  q.second) * (p.second  q.second) +
(p.first  q.first) * (p.first  q.first);
}// returns a value proportional to the distance
// between the point p and the line joining the
// points p1 and p2int lineDist(iPair p1, iPair p2, iPair p)
{
return abs ((p.second  p1.second) * (p2.first  p1.first) 
(p2.second  p1.second) * (p.first  p1.first));
}// End points of line L are p1 and p2. side can have value
// 1 or 1 specifying each of the parts made by the line L
void quickHull(iPair a[], int n, iPair p1, iPair p2, int side)
{
int ind = 1;
int max_dist = 0;// finding the point with maximum distance // from L and also on the specified side of L. for (int i=0; i<n; i++) { int temp = lineDist(p1, p2, a[i]); if (findSide(p1, p2, a[i]) == side && temp > max_dist) { ind = i; max_dist = temp; } } // If no point is found, add the end points // of L to the convex hull. if (ind == 1) { hull.insert(p1); hull.insert(p2); return; } // Recur for the two parts divided by a[ind] quickHull(a, n, a[ind], p1, findSide(a[ind], p1, p2)); quickHull(a, n, a[ind], p2, findSide(a[ind], p2, p1));
}
void printHull(iPair a[], int n)
{
// a[i].second > ycoordinate of the ith point
if (n < 3)
{
cout << "Convex hull not possible\n";
return;
}// Finding the point with minimum and // maximum xcoordinate int min_x = 0, max_x = 0; for (int i=1; i<n; i++) { if (a[i].first < a[min_x].first) min_x = i; if (a[i].first > a[max_x].first) max_x = i; } // Recursively find convex hull points on // one side of line joining a[min_x] and // a[max_x]. quickHull(a, n, a[min_x], a[max_x], 1); // Recursively find convex hull points on // other side of line joining a[min_x] and // a[max_x] quickHull(a, n, a[min_x], a[max_x], 1); cout << "The points in Convex Hull are:\n"; while (!hull.empty()) { cout << "(" <<( *hull.begin()).first << ", " << (*hull.begin()).second << ") "; hull.erase(hull.begin()); }
}
// Driver code
int main()
{
iPair a[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
{0, 0}, {1, 2}, {3, 1}, {3, 3}};
int n = sizeof(a)/sizeof(a[0]);
printHull(a, 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 analysis is similar to Quick Sort. On average, we get time complexity as O(n Log n), but in worst case, it can become O(n2).
Applications
Few of the applications of Quick Hull Algorithm are 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 threedimensional box surrounding an object depends on the 3Dconvex 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 number of other computationalgeometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.