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:

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!

bounding box: none, normal, directional start: / control 1: / control 2: / end: / curve split at /

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).