The Quickhull Algorithm

Demonstrates the quickhull algorithm for computing the convex hull of a set of planar points.

[Click to add points]

The algorithm proceeds like this: (Copypasta from this wikipedia article)

  1. Find the points with minimum and maximum x coordinates, those are bound to be part of the convex hull.
  2. Use the line formed by the two points (white line) to divide the set in two subsets of points, which will be processed recursively.
  3. Determine the point, on one side of the line, with the maximum distance from the line.
    The two points found before along with this one form a triangle. (Red and green)
  4. The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.
  5. Repeat the previous two steps on the two lines formed by the triangle (not the initial line).
  6. Keep on doing so on until no more points are left, the recursion has come to an end and the points selected constitute the convex hull.