10.1.5.3 Finding the spline

At last, after all the preprocessing steps described in the previous sections, we can actually fit a spline to the bitmap. Subject to the tangent constraints (see the previous section), Limn finds the spline which minimizes the error---the overall distance to the pixel coordinates.

More precisely, Limn uses a least-squares error metric to measure the "goodness" of the fit. This metric minimizes the sum of the squares of the distance between each point on the bitmap curve and its corresponding point on the fitted spline. (It is appropriate to square the distance because it is equally bad for the fitted spline to diverge from the curve in a positive or negative direction.)

The correspondence between the fitted spline and the bitmap curve is defined by the t value that is associated with each point (see section 10.1.5.1 Initializing t).

For a given set of t values and given endpoints on the spline, the control points which minimize the least-squares metric are unique. The formula which determines them is derived in Schneider's thesis (see the reference in `limn/README'); Limn implements that formula.

Once we have the control points, we can ask how well the resulting spline actually does fit the bitmap curve. Limn can do two things to improve the fit: change the t values (reparameterization); or break the curve into two pieces and then try to fit each piece separately (subdivision).

The following two sections describe these operations in more detail.