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.

Fractals

Been messing around with fractals lately. Pickover's book has been my starting point for the time being.