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 46, Bézier curve
I like Bézier curves because they're pretty. Seriously, they're a way of drawing a curve that passes through two points. Control points control the shape of the curve, without actually being on the curve. The result is cool and graceful. Bouda's solution overlays Bézier curves between two points, using an increasing number of control points.
import numpy as np import scipy.special from bokeh.plotting import figure, show, output_notebook
def bezier(points, steps=100): n = len(points) b = [scipy.special.binom(n - 1, i) for i in range(n)] r = np.arange(n) for t in np.linspace(0, 1, steps): u = np.power(t, r) * np.power(1 - t, n - r - 1) * b yield t, u @ points
points = np.array([[0, 0], [0, 1], [1, 1], [1, 0]] * 4) plot = figure() for i in range(3, 14): curve = np.array([p for _, p in bezier(points[:i])]) color = tuple(np.random.randint(0, 256, 3)) plot.line(curve[:, 0], curve[:, 1], color=color) show(plot)
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).
If you're rolling your own Jupyter environment, you need:
Python 3.5 (a few of the “days” require 3.6; most will work with 3.4)