Title: Find the convex hull of a set of points in C#

This example shows how to find the convex hull for a set of points. The details are fairly complicated so I'm not going to show them all here, but the basic ideas are relatively straightforward.

A convex hull is a smallest convex polygon that surrounds a set of points. If you imagine the points as pegs sticking up in a board, then you can think of a convex hull as the shape made by a rubber band wrapped around them all. Some of the points may lie inside the polygon. They are not part of the convex hull.

This program demonstrates several useful techniques for finding convex hulls.

First, the program culls some points out to make finding the convex hull faster. To do this, it finds the points that most closely represent the set's upper left, upper right, lower left, and lower right corners. It finds the largest rectangle parallel to the X and Y axes that fits within the quadrilateral defined by those points. This rectangle is guaranteed to lie within the convex hull so any point that lies entirely within the rectangle cannot be on the convex hull. That lets the program remove those points from consideration quickly.

Similarly the program finds the quadrilateral defined by those four points and culls any points that lie inside it. It's harder to determine whether a point lies inside a quadrilateral than inside a rectangle parallel to the X and Y axes, so the program performs the rectangle culling first.

After it has finished culling, the program uses an AngleValue method to order the points. Suppose dx and dy represent the difference between two points. The AngleValue method uses the numeric value dy / (dy + dx) to order the angle from one point to another with respect to the horizontal. This number is not the angle itself, but it has the property that AngleValue(x) < AngleValue(y) if Angle(x) < Angle(y).

The program starts with a point guaranteed to be on the convex hull. For example, the point with the smallest X coordinate or the smallest Y coordinate. Then it begins sweeping around to find the point with the smallest AngleValue. It adds that point to the hull and repeats the sweep from the new point starting with the sweep angle it used in the last test. This process continues until the program finds the start point again. (Basically this lets the program work its way around the convex hull, adding the next point along the polygon at each step.)

To use the program, click several times to select points. Each time you select a point, the program draws the points, highlights those that are culled, draws the culling rectangle and quadrilateral, and draws the convex hull.

Download the example to experiment with it and to see additional details.