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)
- Find the points with minimum and maximum x coordinates, those are bound to be part of the convex hull.
- Use the line formed by the two points (white line) to divide the set in two subsets of points, which will be processed recursively.
- 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)
- The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.
- Repeat the previous two steps on the two lines formed by the triangle (not the initial line).
- 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.