Reading time: 15 minutes | Coding time: 8 minutes

Algorithm

The QuickHull algorithm is a Divide and Conquer algorithm similar to QuickSort.

Let a[0…n-1] be the input array of points. Following are the steps for finding the convex hull of these points.

• Find the point with minimum x-coordinate lets say, min_x and similarly the point with maximum x-coordinate, 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 sub-problems (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 (n-2) 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 1-2: Divide points in two subsets

Steps 3-5: Find maximal distance point, ignore points inside triangle and repeat it

Step 6: Recurse until no more points are left

Implementations

• 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)

set hull;
// 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 p2
int 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 -> y-coordinate of the ith point

if (n < 3)

{

cout << "Convex hull not possible\n";

return;

}
// Finding the point with minimum and
// maximum x-coordinate
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 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 number of other computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.