Splitting up a bezier curve using “ de Casteljau's algorithm ”

To split a curve as a human, all you have to do is look at a curve, draw a point on it, and you're done. But computers don't have eyes, so how do they know whether their pen is "on the curve"? If the curve is a Bezier curve, then computers can use “de Casteljau's” algorithm, which is deceptively simple:

1. Start with a bezier curve from some point to another point (indicated in blue) using two control points (indicated in red)
2. Determine at which t value to split up the curve. t=0 is the curve start, t=0.5 is midway, and t=1 is the curve end.
3. Mark the points on each line of the bezier control box (blue) at distance t (the green dots).
4. Do this again, this time marking the points on the lines between the green dots (the yellow dots).
5. Do this again, this time marking the point on the line between the yellow dots (the black dot).
6. This dot represents the point (x,y) ← x(t), y(t) on the original curve, for the chosen t value. Further more, we've also computed all the points we need to split up the curve into two new curves:
   • curve one: from start to black point, over the first green point, and the first yellow point
   • curve two: from black point to end, over the second yellow point, and the third green point

This is illustrated in the following four boxes (which, by the way, represent a random curve. Reload the page to see a different one each time), with the first box showing the original curve with all of de Casteljau's contained control boxes show, the second one showing the joined two curves after splitting up the original curve, and the third and fourth containing those two curves separately. Note that you can click-drag the points in the first box to change the curve!

This (non-animated-gif, non-flash) animation is brought to you by Processing, the visual programming language, and Processing.js, the project that brings Processing to the web, and of course me: Mike "Pomax" Kamermans. If you want to have a look at the source code, have a look here (the main code), here (very small bounding box regulator class), and here (the bezier curve class - this is where the interesting things happen).