The Convex Hull

The Convex Hull of a set of points in the plane is the shape you would get if you stretched an elastic band around the points, and let it snap tight. A more formal mathematical definition is as follows.

A set C is convex if for any x and y in C, and for any l between 0 and 1, the point lx+(1-l)y is also in C. That is, if x and y are in C, the line segment between x and y is completely contained in C. So for example, circles, squares and ovals are convex, but crosses or crescent moons are not. The convex hull of a set of points is the ßmallest possible" convex hull containing the points. More technically, it is the intersection of all convex sets containing the points.

An alternative definition, at least if the set of points P = {p₁,p₂,...,p_n} is finite, is that the convex hull consists of all points x which may be written x = l₁ p₁ + l₂ p₂ + ... + l_n p_n, for some l₁,l₂,...,l_n such that l₁+l+2+...+l_n = 1.

The DotPlacer Applet (on this site) allows you to place a set of points on the screen, and have it draw the convex hull for you (and many other things). You can even move the points around, and watch the shape change. Try it!

I used the following algorithm to draw the Convex hull. First of all, I found the point p₁ with the smallest x coordinate. Then, I chose a vector v₁ pointing up the y axis. Then I found the point p₂ for which the line p₁p₂ made the smallest angle with v₁, and let v₂ be a vector in the direction of this line. Then, I used p₂ and v₂ to find p₃ and v₃ and so on, finding p₄, p₅, p₆ and so on until the p_k I found is the same as p₁. Then, I connect all the points I found with straight lines.

The algorithm above may not be the most efficient one available for constructing the convex hull, but it works. The actual source code is also available.

For more information on the convex hull, see this World of Mathematics article.