Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Do anyone know any algorithm which would calculate automatically kerning of characters based on glyph shapes when user types text?

I don't mean trivial calculation of advance widths or similar, I mean analyzing the shape of glyphs to estimate the visually optimal distance between characters. For example if we lay out three characters sequentially in a line, the middle character should SEEM to be in the center of the line despite of the character's shapes. An example enlightens the kerning-on-the-fly functionality:

An example of kerning-on-the-fly can be seen from below snapshot: enter image description here

In the above image a seems to be too right. It should be shifted a certain amount towards T so that it seems to be in the middle of T and g. The algorithm should examine the shapes of T and a (and possibly other letters also) and decide how much a have to be shifted to the left. This certain amount is the thing that the algorithm should calculate - WITHOUT EXAMINING THE POSSIBLE KERNING PAIRS OF THE FONT.

I'm thinking of coding a javascript (+svg+html) program that uses hand drawn fonts and many of them lacks kerning pairs. The textfields will be editable and can include text of multiple fonts. I think that kerning-on-the-fly could be one way to ensure mean text flow in this case.

EDIT: One starting point to this could be to use svg font, so it's easy to get path values. In svg font the path is defined this way:

<glyph glyph-name="T" unicode="T" horiz-adv-x="1251" d="M531 0v1293h
-483v173h1162v-173h-485v-1293h-194z"/>

<glyph glyph-name="a" unicode="a" horiz-adv-x="1139" d="M828 131q-100 -85
-192.5 -120t-198.5 -35q-175 0 -269 85.5t-94 218.5q0 78 35.5 142.5t93
103.5t129.5 59q53 14 160 27q218 26 321 62q1 37 1 47q0 110 -51 155q-69 61
-205 61q-127 0 -187.5 -44.5t-89.5 -157.5l-176 24q24 113 79 182.5t159
107t241 37.5 q136 0 221 -32t125 -80.5t56 -122.5q9 -46 9 -166v-240q0
-251 11.5 -317.5t45.5 -127.5h-188q-28 56 -36 131zM813 533q-98 -40 -294
-68q-111 -16 -157 -36t-71 -58.5t-25 -85.5q0 -72 54.5 -120t159.5 -48q104
0 185 45.5t119 124.5q29 61 29 180v66z"/>

The algorithm (or javascript code) should examine those paths some way and determine the optimal distance between them.

share|improve this question

closed as off topic by joriki, Jyrki Lahtonen, Dirk, Henning Makholm, Thomas Oct 13 '12 at 14:15

Questions on Mathematics Stack Exchange are expected to relate to math within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
I voted to close as off-topic. I'm not sure where this belongs; you might try stackoverflow.com. Mathematics it is not. –  joriki Oct 13 '12 at 11:36
1  
Was closed on stackoverflow.com/questions/12654826/kerning-on-the-fly. So if this is not mathematics (to calculate distances between curves and lines) then I have no idea where this belongs. –  Timo Oct 13 '12 at 11:42
1  
You haven't asked a question about how to calculate specific distances between specific curves and specific lines. If you would it would certainly be on topic. What you asked us for is an extremely vaguely specified algorithm whose quality so far could only be judged by aesthetic standards; there's not even a hint of quantification of concepts such as "should seem to be" in the question. –  joriki Oct 13 '12 at 11:46
    
This actually is kind of a mathematical question, it just wasn't worded that way. It sounds as if what the OP wants is an algorithm with takes to shapes $S_1$,$S_2$ and finds a (horizontal) translates $T_x$ such that the distance between $S_1$ and $T_x(S_2)$ appears to the viewer to be some pre-choosen $d$. This tricky part is, of course, to mathematically express the idea of "apparent distance". –  fgp Oct 13 '12 at 11:46
    
@joriki It's OK to ask what mathematical definition people can come up with though, no? –  fgp Oct 13 '12 at 11:50

1 Answer 1

Here's an idea for how to find the kerning automatically.

For each glyph, find the convex hull of the glyph, i.e. the smallest convex shape with encloses the glyph (Convex means that if two points $a$,$b$ lie inside the shape, then the line connecting $a$ and $b$ also lies inside the shape).

Then define the distance between two glyphs $g_1$,$g_2$ the geometric distance between their convex hulls $H(g_1),H(g_2)$, i.e. $d(g_1,g_2) = \text{min }\{\||a-b||:a \in H(g_1), b \in H(g_2)\}$.

The kerning is then obtained by moving $g_2$ to the right until $d(g_1,g_2) = d$, where $d$ is some percentage of the font size or so.

share|improve this answer
    
The trouble is that this won't actually produce typographically pleasing kerning. If you look at well-kerned sans-serif text, you will most certainly find that the convex-hull distances for "db" is larger than for "AA" or "rv" -- and serifs only make it more complex because a serif is not as visually prominent as a main stroke extending to the same horizontal position. –  Henning Makholm Oct 13 '12 at 12:35
    
@HenningMakholm True of course. But it might still work better than doing no adjustment at all. Fonts with manually adjusted kerning tables are probably impossible to beat anyway. That's doesn't mean that there might not be equally simply algorithms which performs way better than my convex-hull suggestion, though. In fact, there probably is ;-) –  fgp Oct 13 '12 at 12:46
    
This is a good example of one possible basic algorithm, sort of starting point. I believe that all kerning-on-the-fly implementations have one basic algorithm and several sub algorithms for fine tuning. –  Timo Oct 13 '12 at 13:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.