Talk:De Boor's algorithm

Untitled

In the definition of the 0-th degree B-spline basis functions, the closed interval between u[i] and u[i+1] should be replaced by the half-open interval between u[i] and u[i+1].

Expressed otherwise, the article presently gives the requirement that we should have u[i] <= x <= u[i+1] but this requirement should really be u[i] <= x < u[i+1].

I would make this change myself, but I do not know how to do this in MathML.

Rdfuhr (talk) 06:15, 14 June 2010 (UTC)

Done. --TN (talk) 08:53, 4 August 2017 (UTC)

Why are n and p reversed?

I believe it is a fairly standard convention to have p be the degree of the curve and n either be the highest index (modus Peigl and Tiller), or the number of control points (highest index + 1).

Why is this convention reversed so that p is the number of control points and n is the degree?

CodieCodemonkey (talk) 08:52, 22 May 2012 (UTC)

Misleading terminology in introduction

In the introduction, there is some unclarity whether the autor is talking about 'control points' or 'internal knots'. Control points do not (neccessarily) lie on the b-spline curve. The introduction states that the curve should try to satisfy $\mathbf {s} (u_{0})=\mathbf {d} _{0},\dots ,\mathbf {s} (u_{p-1})=\mathbf {d} _{p-1}$, which would be valid if $\mathbf {d} _{i}$ were the knot points / internal knots, but not for the control points! Might be that I misunderstood the meaning, but it's not written very clearly. Timitry (talk) 13:20, 11 July 2016 (UTC)

Outline of the algorithm is a complete mess

The formulas in the "Outline of the algorithm" are wrong. I've tried to correct them. That attempt lead me to the impression that the complete article needs a re-write. I don't have the time for that right now. (Not in the next few month either.) The size of the knot sequence is wrong. This causes wrong indexes in the recursive formula (i.e., some undefined knots $u_{i}$ are used in the recursive formula). If $p-2$ is the number of inner knots and $n$ is the spline degree then the spline has $p+n-1$ degrees of freedom. (The first interval has $n+1$ dofs and each of the inner $p-2$ knots implies one additional dof.) For De-Boor's algorithm in its original form $p+2n$ knots are required but $u$ has only $p$ elements.

Maybe, I misinterpreted the meaning of $p$. If $p$ is the number of spline dofs as the first formula actually suggests. Then the number of knots should be $p+n+1$. That means the formulas in Section "Outline of the algorithm" remain wrong nevertheless. --TN (talk) 11:04, 4 August 2017 (UTC)

Possible typo in Optimizations?

I believe d[j] = (1-a[j])d[j-1] + a[j]d[j] would imply d[j] = d[j-1]. I don't see how that index could be right. Sobeita (talk) 23:05, 8 November 2018 (UTC)

No, your comment is not correct. ":=" is not to be understood as a mathematical equality, but as a computational assignment, like python's or C's "=" assignment operator. It just overwrites the old value on its left by what the expression on the right evaluates to (if the equality was fulfilled, there would be no need for overwriting). But there are some issues: first, only the inner temporary control points are read twice, while the leftmost and rightmost are read just once. And that is the point of the optimization: you start at an end, read the endpoint (afterwards you won't need it any more), read its neighbour, and assign. And then you do the same for the next one. In particular, there is no need at all to count down from p (always the same) to r (changing during the algorithm). I think it is much simpler to count up from zero to p-r (both for the human to understand, and also a bit less operations for the computer). Seattle Jörg (talk) 15:23, 23 April 2020 (UTC)

Error in Python Code

For p=0 there follows j=0 and thus the array evaluation at the first pass through the second loop will try to access d[-1], which triggers a breakdown. Also, a definition of k is missing, because notice: while in p=0 it is obvious how to associate t(i) with c(i), the same no longer holds true as p increases, since c must hold more elements than t. — Preceding unsigned comment added by 77.22.103.185 (talk) 08:44, 20 June 2023 (UTC)

import java.util.ArrayList;

import java.util.List;

public class DeBoor {

public static double deBoor(int k, int x, List<Integer> t, List<Double> c, int p) {

List<Double> d = new ArrayList<>();

for (int j = 0; j <= p; j++) {

d.add(c.get(j + k - p));

}

for (int r = 1; r <= p; r++) {

for (int j = p; j >= r; j--) {

double alpha = (x - t.get(j + k - p)) / (t.get(j + 1 + k - r) - t.get(j + k - p));

d.set(j, (1 - alpha) * d.get(j - 1) + alpha * d.get(j));

}

}

return d.get(p);

}

} 95.91.235.38 (talk) 19:28, 17 July 2023 (UTC)