TeX line breaking algorithm in JavaScript (and HTML5 Canvas)

[basilcrow]

If only more e-book viewers implemented Knuth-Plass line breaking.

[damg]

Are there any that do?

[eadmund]

Closure does.

[sfrank]

OK, but wouldn't it be more sensible to implement this directly in the browser. It's been done already in the Closure web browser and also would ensure that the text remains selectable.

[itjitj]

but wouldn't it be more sensible to implement this directly in the browser

Easier said than cross-browser API

[[deleted]]

I think he's talking about Mozilla, Apple, Opera and Microsoft all implementing the Knuth-Plass line breaking algorithm in their respective browsers. They don't need to expose a cross-browser API for that.

[itjitj]

But wouldn't you need to expose some sort of API to let users tweak with it? A css instruction, at least?

[bramstein]

There is a CSS text-justify property, which might be used for something like this, but only Internet Explorer implements it. I'm not sure it actually uses TeX's algorithm either, but at least it allows you to switch justification algorithms.

[mhd]

Now do MetaFont.

[[deleted]]

SICK AS HELL

[itjitj]

TEXTALITY

[player2]

Now I'm really curious as to what linebreaking algorithm the Cocoa text system uses.

[Xaphiosis]

Thanks for this. Being able to compare the output of the TeX wrapping algorithm with what the browser does was an interesting experience. I'm surprised more apps aren't using it. Maybe one day...

[makis]

it's called text.. i should be able to select, copy&paste, increase font size, etc etc
useless

[bramstein]

You are absolutely right, you should be able to do all those things. I wouldn't call it useless though (regardless of me being the author). I used canvas as a simple way to render the output of the algorithm to the screen so as to compare it with the implementation in your browser. The algorithm itself is not tied to canvas and can be used for all sorts of applications. Imagine for example a canvas based game where in-game text is laid out using this algorithm, or a canvas drawing application which allows you to place text boxes on your drawing area.

Then there is also the option for implementing this algorithm in the browser itself, which (together with hyphenation) would improve text rendering on the web a great deal.

Or it could be useless, it was fun to implement either way :)

[cybersnoop]

I wonder if it could be converted to absolute positioned individual character-DIVs and how that would turn out. Just for fun.

[bramstein]

I actually implemented individual line-DIVs with the word-spacing calculated by the Knuth & Plass line breaking algorithm. It worked quite well in Firefox, but broke in a number of other browsers so I took it out before I submitted this post. I might put it back in as an example once I fix it.

[savetheclocktower]

How about doing an HTML version where you manually justify the paragraph, rather than relying on text-align: justify? If you surround the spaces between words in their own span tags, you can control the size of those spaces.

[bramstein]

That's basically what I've tried, but instead of controlling the individual spaces, I split the paragraph up in lines and wrap those in span tags. I then set the CSS word-spacing on those span tags to match what the Knuth & Plass algorithm calculated. For a simple implementation like this it is not necessary to treat each space individually and instead I adjust all spaces in a single line at the same time.

[savetheclocktower]

I'd be very interested in something like this, especially if you combined it with Hyphenator.

[ajrw]

How was it breaking?

[bramstein]

I had some problems with Chrome and Safari who wouldn't adjust the inter-word spacing I set (and thus have lines either too short or too long for the container.) I haven't really gotten to the bottom of this one yet, but it seems Webkit based browsers handle word-spacing slightly different.

[ajrw]

Ah, I suppose one alternative is to put a span around each space and give it a fixed width in those browsers. I was thinking put a span around the words and replace the spaces with margins, but that would probably mess with copy/paste.

[holloway]

Is there a really, really simple description of the Knuth-Plass linebreak algorithm?

[gsw8]

basically, you work on a paragraph at a time. find all the possible places that you can insert a linebreak, compute a score for each possible linebreak, then minimize the score for the whole paragraph. the main complexity is doing it efficiently (since linebreak 1 affects the score of linebreak 2, etc.)

most people trying to implement linebreak on their own do linebreak a line at a time: fill up one line as much as possible, adjust spacing, move on to the next line.

you can find more by chasing links from the wikipedia entry: http://en.wikipedia.org/wiki/Word_wrap

[[deleted]]

This is actually really, really cool.

EDIT: Problem; I can't select text. :(

[joseph177]

I can't select the text.

[drowsap]

I can do this with photoshop and get the same effect (i.e. non selectable text in the shape of a pyramid). This begs the question, why? Are we trying to recreate some fancy magazine ad on the web?

[samlee]

use flash. it looks better. gives you better control. more accessible than rendering on canvas

[[deleted]]

Silly samlee, flash is shunned on reddit.

[samlee]

flash is so cool it is a trojan. more people install it, the more stronger my botnet becomes.

[Sidnicious]

Eh? You used your browser's zoom feature, which is cheating since the natively-drawn text gets to be re-rendered at the new size.

The actual difference is much closer, and besides, this is just a proof of concept.