# [Haskell-cafe] Wildly off-topic: de Boor's algorithm

Andrew Coppin andrewcoppin at btinternet.com
Thu Jul 15 13:29:34 EDT 2010

```Given a suitable definition for Vector2 (i.e., a 2D vector with the
appropriate classes), it is delightfully trivial to implement de
Casteljau's algorithm:

de_Casteljau :: Scalar -> [Vector2] -> [[Vector2]]
de_Casteljau t [p] = [[p]]
de_Casteljau t ps = ps : de_Casteljau t (zipWith (line t) ps (tail ps))

line :: Scalar -> Vector2 -> Vector2 -> Vector2
line t a b = (1-t) *| a + t *| b

Now if you want to compute a given point along a Bezier spline, you can do

bezier :: Scalar -> [Vector2] -> Vector2
bezier t ps = head \$ last \$ de_Casteljau t ps

You can chop one in half with

split :: Scalar -> [Vector2] -> ([Vector2], [Vector2])
split t ps =
let pss = de_Casteljau t ps
in (map head pss, map last pss)

And any other beautiful incantations.

Now, de Boor's algorithm is a generalisation of de Casteljau's
algorithm. It draws B-splines instead of Bezier-splines (since B-splines
generalise Bezier-splines). But I think I may have ACTUALLY MELTED MY
BRAIN attempting to comprehend it. Can anybody supply a straightforward