Answer 4—In very loose terms, you “roll” the set of points along a straight line in order to find which of them lie on the hull and in what sequence. The set of line segments discovered this way, taken together, constitute the convex hull of the set.

In more rigorous terms, you need to start by finding the lowest point in the set. Then you calculate the slopes of the lines from that point to each of the other points, and pick the one that has the smallest positive value. This becomes the first line segment of the polygon.

Next, you perform a coordinate transformation to make this line segment horizontal, and then repeat the search starting from the second point to find the next one. Repeat until you arrive back at the original lowest point.

Contributor: David Tweed

Published February 2004