[Math] Casteljau’s algorithm – practical example

bezier-curve

I have a dataset with about 50 points (x,y) and I would like to draw a smooth curve that can pass as closer as possible on those points.

I have heard about Casteljau's algorithm for splines but after hours searching on google I was not able to find a single piece of code I can use.

As far as I understood, to use this algorithm, I have to divide my dataset in groups of 4 points, right? 1234 5678 etc.. and as far as I noticed, my only problem is to find points in the middle. I mean, if I am calculating a curve for points 1234, I already have points 1 and 4 and I need to calculate 2 and 3, right? But it is a mystery to me how to do that.

I would like to ask you guys if you know some code in C, C++ or Objective-C that computes the curves based on datasets with any amount of number.

What I need is: I send the code an array with the dataset and I receive back an array with the points to draw.

My math is crap. So, please give me practical examples. No need to send me to pages with math theory. Looking at these pages makes my brain hurt…

Answer as you would ask a 10 year old child… 😀

thanks.

Best Answer

Here's an implementation of the Casteljau algorithm that I just wrote (in Java, though you should be able to convert to C/C++/Ob-C with little effort - I didn't use any high-level language features).

I haven't tried it so I don't know if it's correct - the best I can say is that it compiles. Here your list of $x_i$ is given in the array x, your $y_i$ are given in y and $n$ is the number of points. It takes $O(n^2)$ time to compute the location of one point along the Bezier curve fitting your points, and if you want to plot the curve with $k$ points, it will take $O(kn^2)$ time to run.

public class Casteljau {

    private double[] x;
    private double[] y;
    private int n;

    private double[][] b;

    public Casteljau(double[] x, double[] y, int n) {
        //require x.length = y.length = n
        this.x = x;
        this.y = y;
        this.n = n;
        this.b = new double[n][n];
    }

    private void init(double[] initialValues) {
        for (int i = 0; i < n; i++) {
            b[0][i] = initialValues[i];
        }
    }

    private double evaluate(double t, double[] initialValues) {
        init(initialValues);
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < n - j; i++) {
                b[j][i] = b[j-1][i] * (1-t) + b[j-1][i+1] * t;
            }
        }
        return(b[n-1][0]);
    }

    public double[] getXYvalues(double t) {
        double xVal = evaluate(t, x);
        double yVal = evaluate(t, y);
        return new double[] {xVal, yVal};
    }

}
Related Question