10.1.2 Finding corners

Recall that our final goal is to fit splines, i.e., continuous curves, to the discrete bitmap image. To that end, Limn looks for corners in each pixel outline (see the previous section)---points where the outline makes such a sharp turn that a single curve cannot possibly fit well. Two corners mark the endpoints of a curve.

We call the result a curve list, i.e., a list of curves on the pixel outline: the first curve begins at that first corner and continues through the second corner; and so on, until the last, which begins with the last corner found and continues through the first corner. (Each pixel outline is cyclic by definition; again, see the previous section.)

The corner-finding algorithm described below works fairly well in practice, but you will probably need to adjust the parameters it uses. Finding good corners is perhaps the most important part of the entire fitting algorithm: missing a corner usually leads to a sharp point in the original image being rounded off to almost nothing; finding an extraneous corner usually leads to an extremely ugly blob.

Here is Limn's basic strategy for guessing if a given point p is a corner: compute the total displacement (in both x and y) for some number n of points before p; do the same for n points after p; find the angle a between those two vectors; if that angle is less than some threshold, p is a corner.

The number n of points to consider is 4 by default; you can specify a different number with the `-corner-surround' option. If the resolution of the input font is not 300dpi, `-corner-surround' should almost certainly be changed proportionately. The threshold is 100 degrees by default; you can change this with the `-corner-threshold' option. You can see the angles at the chosen corners via `-log'.

However, when Limn finds a point p whose angle is below `corner-threshold', it won't necessarily take p as the corner. Instead, it continues looking for another `corner-surround' points; if it finds another point q whose angle is less than that of p, q will become the corner. (And then Limn looks for another `corner-surround' points beyond q, and so on.)

This continued searching prevents having two corners near each other, which is usually wrong, if the angles at the two would-be corners are approximately the same. On the other hand, sometimes there are extremely sharp turns in the outline within `corner-surround' pixels; in that case, one does want nearby corners after all.

So Limn has one more option, `-corner-always-threshold'. If the angle at a point is below this value (60 degrees by default), then that point is considered a corner, regardless of how close it is to other corners. The search for another corner within `corner-surround' pixels continues, however.