Flowing Text

and the things it makes way for

A short piece about typesetting · measured once, broken live

2 col · 3 col

pausereset187 runs · measured once in 67 ms · reflow 1.00 ms

The objects move on their own · drag to throw · scroll to resize

01

02

03

04

05

Flowing Text

I. The line that got in the way

When a block of text meets an object there are only three options: jump over it, push it to the edge, or go around it. The first two are easy. The third has always been hard — hard enough that for most of the history of printing it was a craft you paid extra for.

Runarounds already appear in medieval manuscripts. An illuminated initial takes a bite out of the top-left of the text block, and the scribe shortens the next three or four lines in turn so the writing retreats along the letter’s contour. There was no algorithm, only an eye and a whole day: misjudge one line and the page starts over.

It is worth noticing that those initials were not "illustrations". They were part of the page, and text making way for them was simply the order of things. The runaround began as a hierarchy, not an effect.

What turned it into a luxury was metal type. Every line is a bar of lead, and to make the third line eight characters narrower than the second you must pack exactly eight characters’ worth of spacing material into its end — from a set of fixed thicknesses. Setting a paragraph around a circular photograph means approximating a curve with a pile of rectangles, one line at a time, by hand.

II. Line breaking is a shortest-path problem

Set the runaround aside and look at the more basic question: given a width, where should a paragraph break?

The naive answer is greedy: pack words left to right, and wrap when the next one will not fit. Typewriters and early word processors all worked this way. Its flaw is that it only looks at the present — a line packed tight may leave the next one with three words in it, stretched like a rubber band.

The better idea is to judge the paragraph as a whole. Give every line a badness score for how loose or tight it is, then minimise the total across the paragraph. Now a line can afford to give up a word, if doing so makes the three lines after it comfortable.

Once stated that way it becomes a standard shortest-path problem: every legal breakpoint is a node, every span from one break to the next is an edge, and the edge weight is that line’s badness. Optimal breaking is the shortest route through that graph.

That translation is the crucial step. It means the optimum can be found by dynamic programming in something close to linear time, instead of trying every combination — a count that explodes exponentially with paragraph length.

How badness is defined is a question of taste rather than of algorithms. The usual penalties are for lines too loose or too tight, for several hyphenated line-ends in a row, and for a last line holding a single word. Change the penalties and you change the house style.

III. Why it stayed expensive

If the algorithm is that clear, why is text runaround in a browser still half-finished? The answer is not in the breaking. It is in the measuring.

To know whether a line fits you must know how wide the words are. And width is not the sum of the characters: Latin text has kerning pairs, some letter combinations fuse into ligatures, Arabic letterforms change with their neighbours, and the same passage at a different size is not a proportional scaling of the first.

So the real cost is this: every time you ask "how wide is this run of text", you run a full text-shaping pass. And the number of times shortest-path wants to ask is quadratic in the number of candidate breakpoints.

The fix is to separate measuring from breaking. Walk the paragraph once, ask the width of every grapheme, ask only once, and cache it. After that, every breaking calculation is addition over an array of numbers — "shape the text repeatedly" becomes "add numbers repeatedly".

That split changes the order of magnitude. A reflow used to mean re-shaping a whole paragraph; now it means re-summing one. The first is milliseconds, sometimes tens of them. The second is microseconds.

Only now does the runaround arrive. What an obstacle does is turn each line’s usable width from a constant into an array that varies by line: line one gets the full measure, line two loses sixty pixels on the left, line three is bitten from both sides. The breaking algorithm needs no change at all — each line simply looks up how much room it has.

Projecting an obstacle down into "an interval per line" is the cheapest abstraction in the whole business. A ball, a fish, a tower, a cloud: to the line breaker they are identical — a list of left and right bounds. The complexity of the shape never reaches the typesetting logic.

The projection does need care, of course. A concave obstacle can cut one line into two disconnected intervals, and then a "line" is no longer a rectangle. Most implementations are conservative here: take the widest run and leave the rest empty.

IV. When the obstacles move

In a static layout all of this happens once. It gets interesting when the obstacles move — drag a ball across a paragraph and the text must re-break on every frame of the drag.

This is where the measure-once boundary decides everything. Grapheme widths have not changed at all while the object moved; only the intervals and the shortest path need recomputing. Adding numbers sixty times a second is cheap. Shaping text sixty times a second is not.

There is a constraint that is easy to overlook: the reflow has to be stable. If nudging an object one pixel to the right rearranges the whole paragraph, what the reader sees is a flicker. Shortest-path is far better than greedy here — its solution varies continuously with its input, instead of cascading to the end of the paragraph because one line came up a pixel short.

The text itself should not be sacrificed either. The common failure of a runaround is to turn the words into an image, or to drop every character into an absolutely positioned box — at which point it can no longer be selected, copied, read aloud or searched. The honest approach decides only where the breaks go and leaves the painting to the browser.

Which returns us to the three options. Jumping over is the least work, pushing aside is the safest, going around is the most trouble — and it earns its keep by admitting that a page holds more than text: there are other things here, taking up room, each with a shape of its own.

Try grabbing an object and throwing it. It will knock its way through the sentences in front of it, and every word will still be exactly where it was — just on a different line.

Lines are broken live in the browser and painted by it — the text stays selectable and copyable.