Typography
Most fonts are represented these days digitally, as collections of spline curves, together with extra information representing kerning (intercharacter spacing) and "hints" for low-resolution rasterization. Although there does not seem to be a direct connection with the computational geometry community, there are a number of problems that could be addressed here: how to automatically choose spline curves to match a given drawing, how to kern and hint automatically or semi-automatically instead of by eye, and how to use geometric font characteristics to perform intelligent font substitution. There are also interesting computational issues connected with text layout (e.g. Knuth's line breaking algorithm in TeX) but these seem less geometrical.
- The comp.fonts
Home Page
- Font
Wizard Algorithm. Howard Trickey of Bell Labs describes his
software for producing three-dimensional renderings of letterforms,
including a straight skeleton like algorithm for achieving a beveled
effect.
- A formal approach to lettershape description for type design.
P. Ghosh and C. Bigelow describe character shapes in terms of their
medial axes.
- John Hobby's paper "Polygonal approximations that minimize the number of
inflections" (from SODA 1993) describes a form of outline
simplification with applications including optical character
recognition, and includes references to similar work.
Hobby has also worked on other typographic algorithms including
automatic
generation of low-resolution hinting information from font outlines.
- The Panose
typeface-matching system condenses various geometric characteristics
of characters into a short numerical vector in order to measure the
similarity between different fonts.
- US
Patent 5115479 covers the compression of bitmap data by using spline
curves to represent the image outlines. Isn't that what standard font
formats already did?
- Usenet messages by Chuck Bigelow and others
discussing algorithms for automatic kerning.
- Using the
Voronoi Tessellation for Grouping Words and Multi-part Symbols in
Documents, M. Burge and G. Monagan.