Friday, February 24, 2017

bézier curves

De Casteljau's algorithm is a fast, numerically stable way to rasterize Bézier curves. This code implements an interactive demo: click to append nodes to the curve's defining polygon, and drag any node to alter the curve.

Wednesday, February 22, 2017

convex hulls

This code demonstrates the Graham scan, an O(n log n) method for finding the convex hull (smallest enclosing polygon) of a planar point set. It's a great example of exploiting order: it works by sorting the set by angle about a known extreme point, allowing the hull points to be found in linear time.

A variation on the algorithm, noted by A.M. Andrew, sorts the set lexicographically and finds the upper and lower hull chains separately. This 'monotone chain' version is often preferred, since it's easier to do robustly.

Wednesday, February 15, 2017

more Π obscurantism

Here's an illustration of an approach to Π pointed out by Kevin Brown. Define f(n) as the nearest greater or equal multiple of n-1, then of n-2, etc (yielding OEIS sequence 2491). Then, inverting a result found by Duane Broline and Daniel Loeb, Π = n2 / f(n).

But as you can see from the comment, the series converges very slowly!