Building the Convex Hull

The Details

The algorithm starts with an unordered set of points defined by cartesian coordinates -- each point has a position on the X-axis and Y-axis. To illustrate the algorithm, I start with the points in Figure 3.

Before construction of the upper and lower hull can take place, you have to first sort the input data based on its X-axis value, then partition the resulting set into a leftmost point, a rightmost point, and the sets of points above and below the line between the leftmost and rightmost point.

Obviously once the data is sorted it's trivial to find the leftmost and rightmost points, and remove them from the set of points -- these are just the first and last members of the sorted array.

Sorting the remaining points into the upper and lower sets requires that we have some function that determines whether a point is above or below a line. I accomplish this using the following strategy. Given a set of points on a line, p0, p1, and p2, I first perform a coordinate translation so that p1 is at 0,0. I then take the determinant of p0 and p2. The resulting value will be negative if p2 angled off in the left direction, positive if it has moved to the right, and 0 if it is colinear with the first two points.

The matrix that is used to get this determinant looks like this:

For this 2x2 matrix, the formula for the determinant will be:

det = ((p0_x-p1_x)x(p2_y-p1_y)) - ((p2_x-p1_x)x(p0_y-p1_y))

Partitioning set S into upper and lower is simply a matter of iterating over each point, calculating the determinant, and moving it into lower for a value ≥ 0, or upper for a value < 0.

Once this is complete, the resulting partitions will look like those in Figure 4.

Now that things are partitioned, the actual construction of the hull can begin. From the algorithm description, you can see that the upper and lower hull construction steps are symmetrical. Both proceed from right to left, starting at the leftmost point and moving to the rightmost point. The only difference is the source of their input points, and the direction they check to insure convexity.

The upper or lower hull is started by simply adding left to the output hull. Points are then added from the correct input source. As each point is added, if the number of points in the working hull is equal to 3 or more, a test is made to see if the last three points have created a convex angle.

Testing for the convex angle is done using the same determinant formula as shown above. If the hull has n points, we simply test to see if p_n-1 is above or below the line formed by p_n-2 and p_n. When constructing the lower hull, if we see that the point is above the line, we have violated convexity, and the middle point is removed from the hull. The opposite test is made when constructing the upper hull. This test-and-remove process is repeated until the last three points are convex, or there are fewer than three points in the working hull.

Figure 5 shows an animation of this process.

The final step, merging the upper and lower hulls, is a trivial matter of appending one hull to the other, and removing the extra copy of right. Once that is done, the actual convex hull definition can be given as a list of points, starting with left and moving counter-clockwise around the hull. Figure 6 is the last frame in the animation, which shows the complete hull.