Software Development

This version uses four incredibly easy to understand passes. Afterwards, I will explain how to optimize it (otherwise, there's no point to this article) as well as explain how you can combine the last three passes into one for a total of two passes overall. This algorithm runs in O(N log(N)) time because of the sorting required.

PASS 1

For this pass, we sort all our points according to the x value.

That's it. Just sort them from left to right.

PASS 2

You need to duplicate the sorted list created in pass 1.

Yeah, that's it. We'll call one list TOP and the other list BOTTOM.

PASS 3

Pass 3 and 4 are the same except the comparisons check opposite values.

For this pass, we build the top portion of the convex hull between the leftmost and rightmost points. So we scan three points (A,B,C) at a time making sure that the angle between those three points are convex. If they're not convex, we remove point B and then move A back one point and start scanning again from there. The reason we move back after removing B is because point A now has a new neighbour which means its angle has changed. So we need to check it again. And only move back if you can (ie. If A isn't already the leftmost point).

How do we check if three points are convex? Easy. We just check if the three points are clockwise. And we do that by using the cross product of two vectors, otherwise known as the determinant (in this particular case).

c = (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);

If c > 0 then it's counterclockwise and you need to remove B from the TOP list.

So that's all you have to do here is scan the whole list and remove B every time c is greater than zero (and then back up one point in the list before continuing to scan). Once you've scanned the whole list, you have the top part of the convex hull.

PASS 4

This pass is exactly the same as Pass 3 except you remove point B from the BOTTOM list if c < 0. That's it.

When you're done, merge your two lists together (making sure not to duplicate the leftmost and rightmost points since they appear in both lists) and you have your convex hull.


Optimizations

As mentioned earlier, you can combine passes 2-4 into a single pass by simply checking c for both lists at the same time. If it's convex, you include it in the proper list. Backtracking would take a little bit more work to do, but it's not that bad.

There are other optimizations you can do. Once you find the leftmost and rightmost points, call these P and Q respectively, you can create smaller top and bottom lists and eliminate a great deal of points right away. We'll call TOPY the maximum Y value from P and Q and BOTY is the lowest. For the top list, we do not include any points that are less than BOTY. And for the bottom list, we don't include any points that are above TOPY.

When we build the top list, we know that no points below P and Q will be part of this section of the convex hull. So there's no need to consider them. Same thing for the bottom list in that no point above both P and Q will be part of that section of the convex hull.

As far as scanning, I'm not sure if the following will help or not, but it's good information to have. When checking the points A, B and C, we know these are from left to right. (We assume we're checking the top list for this example.) So if the points are from left to right, there are two cases where we know for certain if it's concave or convex. If B is below both A and C on the Y axis, we know for certain that this is counterclockwise and hence concave. So if B is below A and B, we can remove it right away without using any cross product. This will actually be the case over 90% of the time from what I've seen. I haven't actually run tests, but the vast majority of the time, you will find B to be below both A and C.

The second case is if B is above both A and C. If so, then it's convex for certain and we can continue scanning the list.

The last case is if B is between A and C on the Y axis. In this case, you have to use the dot product or check if B is on the left side of the line between A and C. Either way, you need to use some multiplications.

That covers the Graham scan variant of convex hull construction.

Below, you will find screenshots of different aspects of the Graham scan.

This next pic shows the formation of the top list by not including any points below P and Q. As can be seen, you can eliminate a lot of possibilities right away. Unfortunately, this doesn't happen all the time as will be seen later for the bottom list.

(Click on picture for larger version)


Here, we see the result of ONLY checking if B is below A and C. No cross product is used. We can see on the left that there is a point that should not be there. But overall, it's very close to the actual convex hull.



And now we see the correct top part of the convex hull in yellow as well as the bottom list.



Just as was the case for the top list, we see how good a result only checking if B is above A and C for the bottom part of the convex hull. Some points should not be included, but it again demonstrates just how often this simple check eliminates candidate points.



And finally the convex hull.