What is the quick hull algorithm?

The quick hull algorithm uses a divide and conquer strategy to compute the convex hull of a shape. A shape's convex hull (also referred to as the convex closure) is the smallest set of points encapsulating it. The following image illustrates the convex hull.

You can see that the convex hull on the right is the smallest number of points that encapsulates the shape, which is five points. Let's see how it works below.

How does the algorithm work

Given an array of points, we will follow these steps to find the convex hull. Note that our convex hull will be a set, so there are no duplicates.

1. Find the point with the minimum x-coordinate, min-x, and another point with the maximum x-coordinate, max-x.
2. Join these two points with a line L to divide the shape into two parts.
3. For a part, we find the point P furthest from the line. Join the points min-x and max-x with P to form a triangle. We are sure they are not part of the convex hull inside the triangle since they are already encapsulated within it.

• This step further divides the problem into two sub-problems and thus is recursive. The first sub-problem has a new line from points min-x and P. The second sub-problem has a line from points P and max-x. Repeat step 3 on the sub-problems until there is no point remaining. Then, we can add the points to be part of the convex hull.

Let's illustrate the steps with the diagram above.

Step 1

Find the point with the minimum x-coordinate, min-x, and another point with the maximum x-coordinate, max-x.

The illustration shows two red points. Those are our min-x and max-x.

Step 2

Join these two points with a line L to divide the shape into two parts.

We can see the line dividing the shape into two parts. Let's say these are the upper and lower parts.

Step 3

For a part, we find the point P furthest from the line. Join the points min-x and max-x with P to form a triangle.

We solve the upper part as follows:

Let's take the upper part and find point P with the maximum distance from the line. Remember that this step further divides the problem into two sub-problems. Note that we can see the point (2,2) inside the triangle can never be part of the convex hull since it is encapsulated by min-x, max-x, and P.

Sub-problem 1: The line joining min-x and P.

• For this sub-problem, there are no points to make a triangle, so we finish here. We add the two points P and min-x to our convex hull.

Sub-problem 2: The line joining max-x and P.

• We find another point P1, and we form a triangle joining P, max-x, and P1, dividing into two more sub-problems, which are the line joining P and P1, and the line joining P1 and max-x. For sub-problem 1, there are no further points, so we add P and P1 to the hull. For sub-problem 2, there are also no further points, so we add P1 and max-x to the hull.

We solve the lower part as follows:

Let's take the lower part and find point P2 with the maximum distance from the line. There are two sub-problems; the line joining min-x and P2 and the line joining P2 and max-x. For both, there are no further points so we add min-x, P2, and max-x to the hull.

Our final convex hull is min-x, max-x, P, P1, P.

Code

Here is the implementation.

Explanation

Here is what the code does:

The getSide.js file

• Lines 5–6: Returns the cross product of p1.p2 and p1.p vectors.
• Lines 8–9: Either 1 or -1 is returned, representing the side point P is on with respect to the line.

The getDistanceFromLine.js file

• Uses the formula from the reference to get a value proportional to the distance between the line and the point P.

The quickHull.js file

• Lines 11–19: Find the point P with maximum distance from Line L. The point must be on the same side as what's given as an argument to quickHull().
• Lines 24–27: If no points were found in lines 11–19, the ind value will still be -1. This means we reach the stopping condition. We add the two points that form the line to the convex hull set.
• Lines 30–31: We divide into two sub-problems and solve them recursively.
• The new line for sub-problem 1 is formed by points[ind], p1.
• The new line for sub-problem 2 is formed by points[ind], p2.

The index.js file

• Lines 4–6: A convex hull is not possible with less than 3 points.
• Line 9: We initialize the hull set.
• Line 12–17: We find min-x and max-x points.
• Line 21 and 24: We recursively solve the two sides divided by the line formed by min-x and max-x.
• Lines 29–40: We initialize our points and call the algorithm, printing out the resulting convex hull.

Complexity

The time complexity is similar to QuickSort due to the division into two sub-problems. Every call of quickHull() takes O(n) due to the step where we find point P furthest from the line.

The best case is when the line divides the two balanced parts, resulting in the recurrence relation of T(n) = 2 T(n/2) + O(n).

This expands to become T(n) = O(n log(n)).

The worst case is when the line divides into extremely unbalanced parts, resulting in a recurrence relation of T(n) = T(n-1) + O(n).

We expand this further into = T(n-2) + O(n) + O(n) = T(n-3) + O(3n) = ... = O(n^2).

The space complexity is O(n) because the resulting convex hull set is limited by the number of points given to the algorithm.