Bézier splines

While I was working with natural cubic splines I first time met the Bézier splines and was not too interested in them in the first moment as they have not too much to do with interpolation. So I left them. Meanwhile the question came up to me about reading dxf files and dealing with them and in these dxf files the Bézier splines found their way back to me :-)

Natural Splines interpolate a curve between a set of data points. Bézier splines do not really interpolate between data points. They draw a curve that meets the first and the last data point and can be formed by the placement of the points between these two points. The first and the last point are called the knots and all the others are control points. I’ll call the computation of the curve approximation now.

Mathematically B-Splines are based on polynomials of (t + (t-1))k. Whereas k = n -2 with n data points. The elements of this polynomial are then multiplied by the data points. So if there are for instance 4 data points P1..P4 we get a polynomial for the approximation point Q(t) like


BezierBezier

An important detail is that q and the points p1..p4 are points in the 2 dimensional room consisting of the coordinates x and y. That means the coordinates of q are


BezierBezier
BezierBezier

For the approximation we let t run from 0 to 1. That gives us the coordinates of the graph to these 4 points. Four data points like P1(120;160), P2(35; 200), P3(220;260), P4(220;40) build a curve like:


Bezier


The curve meets P1 and P4. A rather small detail: With t = 0 the curve starts at P4 and with t = 1 it ends at P1. So the curve is drawn backward :-)


The basic formulation for the B-Spline is


Bezier


The expression




Bezier


Is the binominal coefficient of n-1 and k. The formulation for a binominal coefficient is:




Bezier


Whereas n! means the factorial of n which is n * (n-1) * (n-2) * … * 2. Now the computation of these factorials consumes quite some time in a computer. That’s not too cool. But if we have a closer look at the entire fraction:




Bezier


That can be written as




Bezier


And like this a big part of the calculations can be reduced and we get




Bezier


That reduces the calculation effort quite a bit.


I put this into a small function like:


double CalcBinom(int m, int n)
{
int i;
double numerator = 1;
double denominator = 1;
if (m >= (2 * n))
{
for (i = m; i > (m - n); i--)
{
numerator = numerator * (double)i;
}
for (i = n; i >= 2; i--)
{
denominator = denominator * (double)i;
}
return numerator / denominator;
}
return 0;
}


And with this the function to approximate the curve looks like:




void Approximate(int nbOfPoints)
{
int i, k;
double t1;
double t2;
 
for (k = 0; k <= nbOfPoints; k++)
{
yp[k] = 0;
xp[k] = 0;
t1 = 1 - (double)(k) / (double)(nbOfPoints);
t2 = (double)(k) / (double)(nbOfPoints);
for (i = 0; i < order; i++)
{
yp[k] = yp[k] + y_k[i] * Math.Pow(t1, order-i-1)* Math.Pow(t2, i)*b[i];
xp[k] = xp[k] + x_k[i] * Math.Pow(t1, order-i-1)* Math.Pow(t2, i)*b[i];
}
}
}




This computes two arrays of coordinates xp and yp that contain the all points of the curve and the next step is to run through these points and to draw lines from one point to the next. And don’t be astonished if there comes a strange shape onto the screen. Weird shapes are possible :-)



Bezier



C# Demo Project Bézier splines
  • B_Spline.zip