left click to place points
right click to compute the convex hull
type r to place 15 random points
type c to clear the canvas

And of course the source code for the convex hull algorithm.

Convex Hulls

A convex hull is a polygon in which the angle from one edge to the next is always bigger than 60 degrees. That sounds like a useless trait, but that property describes any polygon that can enclose an arbitrary collection of points without "bites" in the outline. Let's build some!

For this particular implementation, we'll use a gift wrapping approach. We start at a virtual point offscreen, and drag a line across the screen until we've found a point to the left of which are all other points. That's our starting point, and the line from the virtual point to the starting point is our first edge. Albeit virtual. We then perform an extremely expensive algorithm:

Given our edge from p₁ to p₂, pick a point p₃, and check what the angle is between the two lines p₂→p₁ and p₂→p₃: this is our initial angle.

Now run through every other point, and see what the angle is from p₂→p₁ and p₂→[that point]. If it's bigger, this point is a better candidate for our next hull point. Once we've checked every point, whichever is the winner gets added as hull point, we set p₂ to the point we just added, and p₁ to refer to what was just p₂, and we run it again.

If the last point that's left in this way is the first point of our hull, we're done. We now have a closed hull.

How "expensive" is this operation? Let's find out! On your computer, it takes ... milliseconds to find the convex hull for ... points!