Title: Find the convex hull of a set of points in Python

This example shows how to find the convex hull for a set of points. The details are fairly complicated 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. Those four points define the orange quadrilateral shown in the picture.

Next, the program finds a rectangle that lies inside the quadrilateral. To do that, it uses the minimum and maximum coordinates of the quadrilateral's points. For example, to find the rectangle's left X coordinate, the program takes the larger of the X coordinates of the quadrilateral's upper left and lower left corners. It gets the rectangle's other coordinate bounds similarly. This doesn't give the largest possible rectangle inside the quadrilateral, but it gives one that's usually pretty large and it's much easier to find.

The program then culls any points that lie within the rectangle because those points cannot be on the convex hull. In the picture above, those points are drawn in red and they amount to about half of the points. The exact number of points that are culled depends on the points' arrangement, but in general a larger fraction of the points are culled when the problem involves more points. For example, in the picture on the right, you can see that a large majority of the points have been culled.

You could also find the points that lie inside the quadrilateral and cull them, but that would be more work and, for most situations, wouldn't exclude nearly as many points as the rectangle does.

After it has finished culling, the program uses a method called angle_value to order the points. Suppose dx and dy represent the coordinate differences between two points. The angle_value 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 angle_value(x) < angle_value(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 angle_value from that point. It adds the new point to the hull and repeats the sweep from that 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 hull polygon at each step.

The methods that the program uses return multiple results so the program can draw the quadrilateral, culling rectangle, and hull. For example, the find_convex_hull method returns the points that define the quadrilateral, the points that define the rectangle, the points that were culled, the points that were not culled, and the points in the convex hull.

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