Bezier Curves

What Curves?

Bezier curves. We'll take the formal mathematical approach to this problem.

1. Take n+1 control points.
2. The curve will start at the first control point and end at the last control point.
3. Iterate between t = 0 and t = 1 for small steps of t for curve points and connect the points:

   Curve point(t) = Sum each point multiplied by the Bernstein polynomial for "n choose i" evaluated at t.

Note: For example, the Bernstein polynomial for the second (i = 1) of four points (n = 3) would be the Bernstein polynomial for 3 choose 1, which is 3(1-t)t^2.

Implementation

For my implementation, I created a BernsteinPolynomial class, which objects are instantiated for a given (i,n) pair. A call can be made to evaluate the polynomial at a given t value. Be careful, with this approach you need to regenerate all the polynomials every time you change the number of control points.

public class BernsteinPolynomial {
    private int mBinomialCoefficient;
    private int mI, mN;

    public BernsteinPolynomial(int i, int n) {
        // Sanity checks
        assert (n >= 0);
        assert (i >= 0);

        if (n < 0 || i < 0) {
            throw new Error("Cannot create Bernstein polynomial for " + i + ','
                    + " and " + n + '.');
        }

        // Setup object
        mI = i;
        mN = n;
        mBinomialCoefficient = Combinatorics.binomialCoefficient(mN, mI);
    }

    public String toString() {
        return "(" + mBinomialCoefficient + ") " + ((mI == 0) ? "" : "t^" + mI)
                + "(1-t)^(" + (mN-mI)+")";
    }

    /**
     * Evaluate this at the given t value.
     */
    public double evaluate(double t) {
        double oneMinusT = 1.0 - t;

        // Bn(t) = (n choose i)*(t to the i)*(1 - t to the n-i)
        return mBinomialCoefficient * Math.pow(t, mI)
                * Math.pow(oneMinusT, mN - mI);
    }
}


Writing the "n choose i" shows a useful case of recursion.


public class Combinatorics {

    public static int factorial(int i) {
        assert(i >= 0);
        if (i == 0 || i == 1)
            return 1;
        else
            return i * factorial(i - 1);
    }

    public static int binomialCoefficient(int n, int k) {
        return factorial(n) / factorial(k) / factorial(n - k);
    }
}


Encapsulation

A BezierCurve encapulasates this so we can change to a recursive implementation of the drawing without messing with our clients. It also handles caching between drawings so we don't need to recalculate every time we draw.