GSoC Idea: Computational geometry for glyph outlines

Computational geometry for glyph outlines

Lars H: Modern font technologies (TrueType/OpenType, SVG, Postscript Type 1) describe glyph graphics by parametrizing the outlines. There are however at least one older font technology (MetaFont) and certainly many scripts (e.g. Chinese/Japanese/Korean) that rather view glyphs as composed from a number of intersecting pen- or brush strokes. A naive approach to generating glyph outlines would be to first parametrize the outline of each stroke in isolation and then compute the outlines of their union, but this has turned out to be difficult; the equation systems one has to solve are highly nonlinear, and often ill-conditioned, resulting in numerical instability. An alternative approach is to start with a 2D analogue of interval arithmetic, and first describe the individual strokes using inner and outer bounding polygons. From computational geometry with these it is possible to compute the outline topology and also get a good approximation of which part of which stroke determines which section of the combined outline, thus avoiding most of the ill-conditioned problems.

A good first step towards realizing the above program would be to create a package (in Tcl, possibly later with some C acceleration if necessary) for computational geometry with polygons in the plane (probably through translation to the dual problem of arithmetic with circulations on geometric graphs) that also admits tagging vertices with information about "what gave rise to them". Such a package would be useful also for other things (polygon intersection being a trivial example).

Benefit for student: Learn about computational geometry, some graph theory.

Benefit for Tcl: Get a code library capable of computing with polygons.