Convex Hull Visualizer

Hammer a few dozen pegs into a board, stretch a rubber band around all of them and let go. The band snaps inward until it rests on the outermost pegs and touches nothing else. The shape it makes is the convex hull: the smallest convex region that contains every point. Barber, Dobkin and Huhdanpaa open their 1996 paper with that definition almost word for word, and it is hard to improve.

The band finds its shape for free. A computer has to work it out, and the interesting thing is how little it needs to know. Every one of the classic planar methods, from Graham’s scan to quickhull, is built on a single yes or no question about three points. The methods differ in how many times they ask it, and the question itself is where most of the trouble hides.

The only question that matters

Take three points a, b and c. Walk from a to b, then turn toward c. Do you turn left, turn right, or carry straight on? The answer comes from one small calculation: multiply the run from a to b by the rise from a to c, subtract the rise from a to b times the run from a to c, and look at the sign. Positive means a left turn, negative a right turn, zero means the three points sit on one line.

That number is twice the signed area of the triangle the three points make. It needs two multiplications and a few subtractions. It never computes an angle, a square root or a slope. Shewchuk describes the same orientation test as one of the basic predicates of geometric programs, the decision of which side of a line a point falls on.

Here is a worked example you can type into the tool. Use six points: (0, 0), (4, 0), (8, 0), (8, 6), (4, 3) and (0, 6). The turn from (0, 0) through (8, 0) to (8, 6) gives 8 times 6 minus 0 times 8, which is 48, a left turn. The turn from (0, 0) through (4, 0) to (8, 0) gives exactly zero: those three are in line.

The hull is the rectangle with corners (0, 0), (8, 0), (8, 6) and (0, 6). Its shoelace sum is 96, so the area is 48 square units and the perimeter is 28. The middle point (4, 3) is inside, and (4, 0) sits on the bottom edge.

That last point is the first real decision any implementation has to make. Is a point lying on an edge part of the hull or not? Some uses want only the true corners. Others want every point the band touches. Neither is wrong, but a program has to pick one and apply it the same way everywhere, or two methods will hand back different answers for the same input and both will look correct.

Four ways to wrap a set

Graham’s scan appeared in Information Processing Letters in 1972. In the form usually written today, and the form the tool runs, it starts from the lowest point. The others are sorted by their angle around it, which can be done with the turn test alone, because one point comes before another exactly when the turn from the pivot through the first to the second goes left. Then the sorted list is walked with a stack. Each new point either makes a left turn with the top two entries, and is pushed, or it does not, and the top is popped until it does. The sort dominates, so the whole thing takes on the order of n log n steps.

Andrew’s 1979 paper offered a variant that needs no pivot. Sort the points by x, then by y, and build the lower half of the hull from left to right and the upper half from right to left, with the same stack rule. No angles are involved, only coordinate comparisons in the sort and turn tests in the two passes. The bound is again n log n.

Gift wrapping, published by Jarvis in 1973, works the way you would wrap a parcel by hand. Start at a point known to be on the hull. Look at every other point and keep the one that leaves all the rest on its left. That is the next corner. Repeat until you are back where you started. Each corner costs a pass over all n points, so the total is n times h, where h is the number of corners. When the hull is small, that is cheap. When every point is a corner, it is n squared.

Quickhull follows the pattern of a sorting method too: Eddy wrote in 1977 that his version works in a fashion similar to the sorting algorithm Quickersort. Join the leftmost and rightmost points. Find the point farthest outside that line, which must be a corner, and throw away everything inside the triangle it forms. Recurse on the two new edges. On typical inputs most points vanish early. On bad inputs the splits are lopsided, and the worst case is n squared.

Sorting is the price, unless the answer is small

Why should n log n be the target? The Wikipedia survey of hull methods gives a neat reason. Put the numbers you want sorted onto a parabola, as points of the form x and x squared. Every one of them is a corner, and walking the hull visits them in sorted order. Any hull method fast enough to beat sorting would therefore sort faster than sorting allows. Preparata and Hong made the same point in 1977 when they presented a divide and conquer method that meets the bound, and Yao proved in 1981 that any method using only tests of degree two needs on the order of n log n of them in the worst case.

That argument has a loophole, and it is the size of the answer. The parabola trick only bites when every point is a corner. Kirkpatrick and Seidel showed in 1986 that the problem can be solved in order n log h time, where h is the size of the output, and that this is optimal even when the cost is measured against both input and output. Chan gave a simpler method with the same bound ten years later. Gift wrapping was an early hint of the idea: its cost already depends on h, just not as gently.

You can watch the difference in the tool. Load the preset of 108 lattice points lying exactly on a circle of radius 1,105, where every point is a corner. Gift wrapping makes 11,449 orientation tests. Monotone chain makes 319, plus 552 coordinate comparisons in its sort. Graham’s scan makes 705, because its angular sort compares points with the turn test. Then load a random disc of 200 points with seed 7: after merging duplicates, 191 points remain and only 21 are corners, and gift wrapping falls to 3,970 tests.

Those counts are measured, not estimated, and they depend on details: how ties are broken, how the sort is written, whether duplicates are merged first. The sources quote orders of growth, n log n for the sorting methods, n h for gift wrapping, and for quickhull n log n on average with n squared in the worst case. An order of growth carries no constant, so the honest comparison is between methods on the same points, not between a count and a formula.

When the points line up

All of this assumes the turn test gives the right sign. With exact arithmetic it always does. With the floating-point numbers most programs use, it can fail exactly where it matters, when three points are nearly in a line. Kettner, Mehlhorn, Pion and Schirra built a set of classroom examples around this: geometric algorithms are designed for exact real numbers, and substituting floating-point arithmetic can make an implementation fail. Barber and his coauthors noted that assuming well-behaved input can lead to serious errors once floating point is involved.

The tool avoids the problem by staying on whole numbers. JavaScript numbers hold every integer up to two to the power 53, minus one, exactly. If every coordinate is at most 2^24 in size, each difference is at most 2^25, each product at most 2^50, and the turn value at most 2^51. Nothing is ever rounded, so the sign is always right. Shewchuk’s approach is the other classic answer: fast floating-point tests that switch to extended precision only when the result is in doubt.

The tempting shortcut is to sort by angle with the arc tangent function instead of the turn test. Try the pivot (16,777,000, minus 16,777,216) with the points (minus 16,702,302, 16,093,537) and (minus 15,937,649, 15,342,783). All three coordinates fit in the safe range. The exact turn value is minus 1: a sliver of a triangle with an area of one half.

Yet a current JavaScript engine’s arc tangent returns the same angle for both directions. A scan that keeps only the farthest point of each angle, as the textbook version does, then drops a genuine corner without any warning.

This is what the method cannot do on its own: survive inexact arithmetic. None of the four algorithms is robust by itself. Each is only as good as its turn test, and a library that accepts arbitrary decimal input has to choose between exact arithmetic, adaptive precision, or a documented tolerance. A widely used scientific library documents that its convex hull routine calls Qhull, the program from the Barber paper, and that points left out because of numerical precision can be reported in a separate list.

Where the band gets used

The hull turns up wherever a cloud of points needs an outline. Bentley, Preparata and Faust opened their 1982 paper on approximate hulls by noting that the problem arises in many applications, and offered a method that gives up a little accuracy for speed: an approximate hull in time proportional to n plus one over the error allowed. In ecology, the minimum convex polygon around an animal’s recorded locations is the oldest way to draw a home range. A 2018 survey by Baillo and Chacon calls it the simplest method, lists studies using it back to Mohr in 1947, and warns that it tends to overestimate the range because it swallows terrain the animal never visits.

That warning is a good place to end. A hull is the tightest convex wrapper, not the tightest wrapper. It is cheap, unique and easy to check, which is why the same left-turn test has carried it through half a century of algorithms. What it describes is the reach of the points, not their shape.