The convex hull of 30 random points in 3D. Created with matplotlib and NumPy.
The convex hull of 30 random points in 3D. Created with matplotlib and NumPy. (source: Dominik Moritz on Wikimedia Commons)

100 Days of Algorithms is a series of Medium posts and Jupyter Notebooks by Tomáš Bouda that implements 100 interesting algorithms. They're a programming exercise that Bouda set for himself: can he implement 100 interesting algorithms, one per day?

The answer was “yes.” The algorithms range from classics like Towers of Hanoi to Bloom filters and graph traversal. Over the coming weeks, we’ll be featuring selections from Bouda's 100 Days of Algorithms project here on O’Reilly.

Day 28, convex hull

Imagine putting a bunch of nails in a wooden board, then stretching a rubber band around all the nails. That's the convex hull problem: given a group of points in a plane, what's the smallest polygon that contains all those points?

Here's Bouda's Medium post, and you can access and clone the Jupyter Notebook here.

import numpy as np
from bokeh.plotting import figure, output_notebook, show

algorithm

def split(u, v, points):
    # return points on left side of UV
    return [p for p in points if np.cross(p - u, v - u) < 0]

def extend(u, v, points):
    if not points:
        return []

    # find furthest point W, and split search to WV, UW
    w = min(points, key=lambda p: np.cross(p - u, v - u))
    p1, p2 = split(w, v, points), split(u, w, points)
    return extend(w, v, p1) + [w] + extend(u, w, p2)

def convex_hull(points):
    # find two hull points, U, V, and split to left and right search
    u = min(points, key=lambda p: p[0])
    v = max(points, key=lambda p: p[0])
    left, right = split(u, v, points), split(v, u, points)

    # find convex hull on each side
    return [v] + extend(u, v, left) + [u] + extend(v, u, right) + [v]

run

points = np.random.rand(100, 2)
hull = np.array(convex_hull(points))
hull
    array([[ 0.9991102 ,  0.74387573],
           [ 0.98512754,  0.91822047],
           [ 0.79267953,  0.95080755],
           [ 0.11250518,  0.98983246],
           [ 0.04098604,  0.9784821 ],
           [ 0.01458786,  0.89852061],
           [ 0.00210623,  0.23655309],
           [ 0.05913608,  0.12453548],
           [ 0.19229802,  0.0073965 ],
           [ 0.3678626 ,  0.01986249],
           [ 0.74089924,  0.0571285 ],
           [ 0.93004227,  0.08858407],
           [ 0.99371365,  0.52807472],
           [ 0.9991102 ,  0.74387573]])
output_notebook()

plot = figure()
plot.scatter(x=points[:, 0], y=points[:, 1])
plot.line(x=hull[:, 0], y=hull[:, 1], color='red')

show(plot)

Technical notes

The implementations work; the Jupyter Notebooks all run. Since this started off as a personal exercise, don't expect the implementations to be optimal, bullet-proof, or even necessarily correct (though we don't see anything wrong with them). And don't expect them to contain your favorite algorithms (or the ones you need for your homework assignments).

The easiest way to install Jupyter Notebooks is to use Anaconda. The second easiest (and most bulletproof) way is to install Docker and then use the scipy-notebook container.

If you're rolling your own Jupyter environment, you need:

Article image: The convex hull of 30 random points in 3D. Created with matplotlib and NumPy. (source: Dominik Moritz on Wikimedia Commons).