[Haskell-cafe] Wildly off-topic: de Boor's algorithm
mokus at deepbondi.net
mokus at deepbondi.net
Fri Aug 6 10:03:52 EDT 2010
mokus at deepbondi.net wrote:
> It took me a while to get the intuition right on those, but here's a quick
> sketch. Let n = number of control points, m = number of knots, and p =
> degree. For p = 0 (constant segments), each control point corresponds to
> one span of the knot vector, so n = m - 1. Each time you move up a
> degree, the basis functions span one more segment of the knot vector.
> Thus, to keep the same number of control points you have to add a knot
> when you add a degree, so n = m - 1 + p. Equivalently, n - p = m - 1,
> which incidentally makes an appearance in the deBoor function below when
> we zip "spans p us" with "spans 1 ds". This is just the property that
> ensures that the length of these lists is equal.
How embarrassing, I managed to get this simple math wrong. That's what I
get for trying to think in the morning without either my notes or my
coffee, I suppose. At least, I have that standard excuse to fall back on,
so I'll take advantage of it. "n = m - 1 + p" should read "n + p = m - 1"
- I added "p" to the wrong side.
It is indeed the property that makes the zip line up, but not by the math
I gave. Instantiating n and m as the respective "length" expressions
makes the equation:
> length ds + p = length us - 1
With subsequent derivation in light of the fact that the 1st control point
is being ignored (which introduces a "- 1" on the RHS, if I'm not mistaken
again), as mentioned earlier, and the fact that the expression in question
is supposed to return a list one shorter than ds:
> length ds + p - 1 = length us - 1 = length (tail us)
> length ds - 1 = length (tail us) - p
> length (spans 1 ds) = length (spans p (tail us))
(Under the assumption that all the lists involved are long enough for the
tail and drop operations)
And all is (hopefully) right again.
-- James
More information about the Haskell-Cafe
mailing list